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

在審

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

1.一種基于多點張力模型的快速聚類方法，其特征在于：該方法包括以下步驟：

步驟一：初始階段，從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；

步驟六：當f_Xr＞f_Xg，再次進行拓展操作：X_e＝X_c+γ(X_r-X_c)，其中X_e為拓展點，γ是拓展系數，設γ為2；如果f_Xe＞f_Xg，則用X_e替代X_s，否則X_r將替代X_s；

當f_Xr＜f_Xs，將進行壓縮操作：X_t＝X_c+β₂(X_s-X_c)，其中X_t為X_s壓縮后的點，β₂為壓縮系數，設β₂為0.5，如果f_Xt＞f_Xs，則用X_t替代X_s，否則X_s保持不變；

當f_Xs＜f_Xr＜f_Xg，將進行收縮操作：X_w＝X_c-β₃(X_s-X_c)，其中X_w為收縮后的點，β₃為收縮系數，設β₃為0.5，如果f_Xw＞f_Xs，則X_w將替代X_s，否則用X_r替代X_s；

步驟七：不斷進行迭代，當滿足終止條件，算法終止。