[發(fā)明專利]一種改進的譜聚類及并行化方法

在審

• 申請?zhí)枺?/td>: 201810344423.3
• 申請日: 2018-04-17
• 公開（公告）號: CN108520284A
• 公開（公告）日: 2018-09-11
• 發(fā)明（設計）人: 強保華;孫顥寧;王玉峰;謝武;韋二龍;史喜娜;趙興朝
• 申請（專利權）人: 桂林電子科技大學;中國電子科技集團公司第五十四研究所
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N3/00
• 代理公司: 廣州市一新專利商標事務所有限公司 44220
• 代理人: 滕杰鋒

本發(fā)明公開了一種基于群智能算法的改進譜聚類方法，通過選取拉普拉斯矩陣的前2k個最大特征值對應的特征向量作為聚類的源數(shù)據(jù)，然后通過群智能算法選取優(yōu)質的初始化中心點進行聚類操作，提高了聚類的最高準確率和多次聚類結果的穩(wěn)定性。本發(fā)明引入了布谷鳥搜索算法尋找初始化中心點，將布谷鳥搜索算法過程中的適應度函數(shù)采用誤差平方和函數(shù)，應用于譜聚類中，將搜索得到的最小的誤差平方和的數(shù)據(jù)點作為初始化中心點。本發(fā)明將布谷鳥搜索算法中的萊維飛行策略引入粒子群算法，在粒子群算法收斂速度變緩情況下，使用萊維飛行策略產(chǎn)生頻繁較小步長和和偶爾較大步長，在不同步長下引入不同側重的速度更新公式。

技術領域

本發(fā)明屬于機器學習中的非監(jiān)督學習方法，涉及聚類方法與群智能算法。

背景技術

聚類的目的是對數(shù)據(jù)進行劃分，將相似的數(shù)據(jù)劃分到同一類簇，把不相似的數(shù)據(jù)劃分到不同類簇中。隨著信息技術的發(fā)展帶來了數(shù)據(jù)的多樣性，使許多數(shù)據(jù)的維度具有不相關性，傳統(tǒng)的聚類算法很難處理這些維度不相關的數(shù)據(jù)。譜聚類是一種新型的聚類算法，能夠在任意形狀的樣本空間聚類并可以收斂到全局最優(yōu)解，并且已被廣泛應用于計算機視覺、文本挖掘和生物信息挖掘等領域。現(xiàn)階段，針對譜聚類的研究主要包括相似矩陣的構造、特征向量的選取、類簇數(shù)目的確定及算法的應用等問題。在這些研究領域中，特征向量的選取對類簇劃分具有至關重要的作用。經(jīng)典的NJW算法采用前k(k為類簇數(shù)目)個最大特征值對應的特征向量進行聚類操作。Sun等提出基于主分量分析(PCA)提取的特征選擇，即不再采用特征值較大的幾個特征向量，而是采用遺傳算法搜索PCA空間，找到能夠反映目標概念信息的特征向量子集作為主成分方向。Zhao等提出基于熵排序的特征向量選擇算法，先計算出特征向量的熵，將熵值排序并選擇出其中較好的特征向量，文獻中指出，存在比最大的k個特征向量更好的特征向量組，選出的特征向量個數(shù)并不一定是k個。Rebagliati等提出特征值的差值可以幫助確定特征向量數(shù)量的選擇，較大的特征值對應的特征向量有利于聚類。文獻《Machine-learning research:Four current directions》中分析，適用于全體數(shù)據(jù)的一組特征向量不一定存在，即使存在也不一定能根據(jù)提供的少量先驗信息得出。

發(fā)明內容

本發(fā)明提供了一種基于群智能算法的改進譜聚類方法，通過選取拉普拉斯矩陣的前2k個最大特征值對應的特征向量作為聚類的源數(shù)據(jù)，然后通過群智能算法選取優(yōu)質的初始化中心點進行聚類操作，提高了聚類的最高準確率和多次聚類結果的穩(wěn)定性，在保證多次聚類結果穩(wěn)定性的前提下提高聚類準確率。

為了保持結果的穩(wěn)定性，需要選擇較優(yōu)的初始化中心點，本發(fā)明引入了布谷鳥搜索(Cuckoo Search，CS)算法尋找初始化中心點。將布谷鳥搜索算法過程中的適應度函數(shù)采用誤差平方和函數(shù)，應用于譜聚類中，將搜索得到的最小的誤差平方和的數(shù)據(jù)點作為初始化中心點，可以降低因隨機選取中心點而產(chǎn)生的準確率不穩(wěn)定性。

為了使其尋優(yōu)過程收斂速度更快，本發(fā)明還提供了將布谷鳥搜索算法中的萊維飛行策略引入粒子群算法的步驟，在粒子群算法收斂速度變緩情況下，使用萊維飛行策略產(chǎn)生頻繁較小步長和和偶爾較大步長，在不同步長下引入不同側重的速度更新公式，當小步長時減弱全局最優(yōu)解的影響，當大步長時減弱當前粒子歷史最優(yōu)解的影響。將該改進算法用于尋優(yōu)，可以得到較小收斂值并加快收斂速度。

附圖說明

圖1為基于特征擴展和布谷鳥搜索算法的譜聚類算法流程圖。

圖2為融合布谷鳥搜索的粒子群算法流程圖。

圖3為并行化構建拉普拉斯矩陣DAG圖。

圖4為并行化K-means算法DAG圖。

圖5為改進譜聚類算法與其他聚類算法對比結果。

圖6為融合布谷鳥搜索的粒子群算法與其他改進算法對比。

圖7為并行化構建拉普拉斯矩陣單機與集群時間對比。