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

在審

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

1.一種改進的譜聚類及并行化方法，所述方法包括：

選取拉普拉斯矩陣L的前2k個最大特征值對應的特征向量作為聚類的源數據，k為類簇數目；

采用布谷鳥搜索算法尋找初始化中心點；

所述采用布谷鳥搜索算法尋找初始化中心點包括如下步驟：

(1)給定原始數據X＝[x₁,x₂,x₃,…,x_n]∈R^d和聚類數目k；

(2)根據下面公式計算拉普拉斯矩陣L：

A_ij＝exp(-|d_ij|²/2σ²)，i≠j，A_ii＝0；

(3)計算拉普拉斯矩陣L的前2k個最大特征值的特征向量的規范化矩陣Y；

(4)在矩陣Y中隨機地初始化n個鳥巢的位置

(5)分別以n個鳥巢的位置作為聚類中心點進行聚類劃分，計算每個鳥巢的適應度值F，并保留相對較小F值的鳥巢位置：F_best＝min{F₁,F₂,…,F_n}；

(6)按照布谷鳥搜索算法中的萊維飛行策略對鳥巢位置進行更新；

(7)將更新位置后的鳥巢再次進行聚類劃分，計算每個鳥巢的適應度，然后根據適應度對比新舊兩代鳥巢，并對比上一代最小F值，保留相對較小F值鳥巢位置；

(8)用隨機數r∈[0,1]與發現概率P_a比較，若r＜P_a，保留鳥巢位置；若r＞P_a，則通過公式更新鳥巢位置，保留更新前后F值較小的鳥巢位置；

(9)如果未達到最大迭代次數或設定的停止條件則返回步驟(5)繼續執行；否則保留最小適應度值的解且進入下面步驟操作；

(10)對獲得的最優鳥巢位置進行K-means聚類，最后輸出聚類中心點和聚類結果。

2.根據權利要求1所述的方法，其中所述布谷鳥搜索算法中的萊維飛行策略引入粒子群算法，所述粒子群算法包括如下步驟：

(1)初始化，設置粒子群的大小，隨機初始化其位置x_i＝(x_i1，x_i2，…，x_iD)，設置初始速度v_i＝(v_i1，v_i2，…，v_iD)；

(2)計算每個粒子的適應度值F，保留每個粒子經歷的歷史最好位置p_i＝(p_i1，p_i2，…，p_iD)和群體內經歷的最好位置p_g＝(p_g1，p_g2，…，p_gD)；

(3)粒子根據如下的公式來更新自己的速度和位置：

其中，c₁、c₂為學習因子或加速系數；r₁、r₂是該區間內均勻分布的偽隨機數，取值范圍是[0,1]；

(4)在迭代過程中判斷最近10次迭代過程中適應度值F的下降速度，當下降速度低于閾值時，引入萊維飛行策略，令step＝Lévy(λ)，用step來實現頻繁的小步長和偶爾的大步長策略；小步長時，減弱全局最優解的影響，公式如下：大步長時，減弱當前粒子歷史最優解的影響，公式如下：

其中：表示全局影響因子；表示局部影響因子；

(5)如果未達到最大迭代次數或設定的停止條件則返回步驟(2)繼續執行；否則保留最小適應度值F的位置。