[發明專利]一種基于多點張力模型的快速聚類方法

在審

• 申請號: 201710364512.X
• 申請日: 2017-05-22
• 公開（公告）號: CN107194425A
• 公開（公告）日: 2017-09-22
• 發明（設計）人: 屈洪春;呂強;蔡林沁;唐曉銘;王平
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N3/00
• 代理公司: 北京同恒源知識產權代理有限公司11275
• 代理人: 廖曦

技術領域

本發明屬于聚類分析技術領域，涉及一種基于多點張力模型的快速聚類方法。

背景技術

聚類分析是一種重要的無監督學習方法，在數據的內在結構識別方面起到了不可替代的作用。聚類是根據數據對象相似度，把未知分類的數據集分割成不同的類或簇，使同一簇內的數據對象具有最大相似性，不同簇間的數據對象具有最小相似性。聚類分析在機器學習、模式識別、數據挖掘、圖像處理等領域已經得到了廣泛研究和應用。

K-means算法是最經典的聚類算法之一，其簡單、高效，具有良好的局部搜索能力，得到了廣泛應用及研究。但存在過于依賴初始聚類中心、容易陷入局部最優等缺陷。近年來，群體智能算法以其良好的全局尋優能力得到越來越多的關注，并成功運用到聚類分析領域。許多學者針對初始聚類中心的選取進行不同的改進，在一定程度上改善了聚類效果，提高了算法聚類結果的質量，但仍可能陷入局部最優。

發明內容

有鑒于此，本發明的目的在于利用人工蜂群算法模型，提供一種基于多點張力模型的快速聚類方法，利用當前全局最優解和次優解，并結合物理學的張力模型，使可能會陷入局部最優的解移動到更加合理的位置，避免算法陷入局部最優。該聚類方法在全局搜索階段，引入丟棄算子使算法跳出局部最優。在局部搜索階段，結合遺傳算法中的交叉算子和變異算子提高了算法收斂速度和解的多樣性。該聚類方法適用不同規模、多種類型的數據集，具有較強的伸縮性和健壯性。

為達到上述目的，本發明提供如下技術方案：

一種基于多點張力模型的快速聚類方法，包括以下步驟：

步驟一：初始階段，從UCI數據集庫中選取某個數據集，設定控制參數的值后，選取一定數量的蜜源，一個蜜源代表一個解，蜜源的質量代表解的適應度；將蜜源隨機分布在空間中，蜜源的位置即為聚類中心位置；

步驟二：引領蜂先在蜜源鄰域搜索新的解，搜索方式按照公式V_i＝X_i+R_i(X_i-X_h)進行，其中i,h∈{1,2,…,N}，N表示初始解的數量，V_i是新的蜜源，X_i是舊蜜源，R_i是[-1.1]內的隨機數；如果V_i的適應度比X_i高，則替代X_i，否則X_i保持不變；

步驟三：當所有引領蜂完成搜索行為后，評估所有解的適應度，跟隨蜂按照概率值P_i選擇新的蜜源，P_i根據公式計算，其中i∈{1,2,…,N}，N表示初始解的數量，f_i表示第i個解的適應度；P_i與隨機數r比較，若P_i＜r，則跟隨蜂在蜜源鄰域結合變異算子搜索新的解，搜索方式按照公式X_i'＝X_i+α₁(X_best-X_i)+β₁(X_p-X_q)進行，其中X_i'表示X_i更新后的解，X_best為當前最好的解，p,q∈[1,N]之間的隨機整數，α₁,β₁服從均勻分布；

步驟四：引入交叉算子增加解的多樣性，使算法更容易跳出局部最優，其中i,k＝1,2,…,N，C_r是交叉率，設C_r＝0.15；

步驟五：若某個解X_s經過Limit次迭代后沒有找到更合適的解來替代它，則該X_s將被丟棄；重新評估所有解的適應度；引入丟棄算子并結合物理學的張力模型使算法跳出局部最優，使陷入局部最優的解X_s移動到更加合理的位置；選擇當前最好的解X_g和次好解X_b，找到X_g和X_b的中間位置X_c＝(X_g+X_b)/2；對X_c進行反射拓展得到新的解X_r的位置X_r＝X_c+α₂(X_c-X_s)，其中α₂是反射系數，設α₂為1；