[發明專利]混合蛙跳算法的自適應核k?means方法與系統

在審

• 申請號: 201710201837.6
• 申請日: 2017-03-30
• 公開（公告）號: CN106991442A
• 公開（公告）日: 2017-07-28
• 發明（設計）人: 丁世飛;樊淑炎;王小玉
• 申請（專利權）人: 中國礦業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.混合蛙跳算法的自適應核k-means方法與系統，其特征是：根據數據的結構特征，設計了一種適用于核空間的聚類有效性指標KBWP(Kernel Between-Within Proportion)，將該指標作為適應度，利用混合蛙跳算法同時優化聚類數和核參數，聚類過程中無需人工介入，最終得到適于當前數據的聚類結果，該方法具體如下：

步驟1：導入數據集，隨機初始化青蛙種群X_i，i＝1,2,...,F，青蛙的位置信息表示優化參數，使用核k-means進行聚類并計算KBWP；

步驟2：隨機選取k個初始聚類中心，將其他數據點劃分到距離其最近的聚類中心所屬的類，得到k個初始類{c₁,c₂,…,c_k}；

步驟3：根據計算得到新的聚類中心，更新每個類c_i＝(x∈D|i＝argmin_{j＝1,2,...,k}||Φ(x)-m_j||)，Φ是映射函數；

步驟4：重復步驟3，直到每個類不再發生改變，一次核k-means方法結束；

步驟5：根據計算類內距離，表示第i個類中第q個數據點且q≠j，表示第i個類中第j個數據點，n_i表示第i個類中的數據點個數，w(i,j)表示第i個類中第j個數據點的類內距離；

步驟6：根據計算類間距離，c和j表示聚類標簽，表示第c類中的第p個數據點，n_k表示第k個類中的數據點個數，b(i,j)表示第i個類中第j個數據點的最小類間距離；

步驟7：根據計算KBWP指標值，根據

計算AVG_KBWP；

步驟8：基于KBWP的值，所有青蛙進行降序排序，被劃分成m個子群，每個子群包含p只青蛙，F＝m×p，其中，第一只青蛙進入第一個子群，第二只青蛙進入第二個子群，第m只進入第m個子群，第m+1只進入第一個子群；

步驟9：在每個子群內，確定X_w，X_b和X_g。X_w和X_b分別代表最壞和最好位置的青蛙，具有全局最優適應度的青蛙被定義為X_g；

步驟10：按照跳躍規則進行子群進化，最壞的青蛙X_w跳向最好的青蛙X_b；如果跳躍產生更優的解，代替最壞的青蛙；否則，最壞的青蛙被刪除，按照約束條件S＝rand(X_g-X_w)隨機產生新的青蛙來代替它；

步驟11：局部搜索達到預定義的迭代次數后，將所有青蛙按照適應度值進行降序排序，記錄具有全局最優適應度的青蛙X_g，按照步驟2重新劃分子群，并進行局部優化；

步驟12：當全局最優青蛙的適應度的相對改變小于預定義的值或迭代次數達到預定義的值，優化聚類數和核參數結束，輸出聚類結果。

2.根據權利要求1所述的混合蛙跳算法的自適應核k-means方法與系統，其特征在于：SFLA結合了兩個搜索方法的技巧，粒子群優化的局部搜索技巧和混合復雜進化的信息混合技巧，這種組合的策略能使混合蛙跳算法搜索到次優的解，避免局部最值，利用混合蛙跳算法優化核k-means，不僅節省時間，且聚類效果結果較佳。

3.根據權利要求1所述的混合蛙跳算法的自適應核k-means方法與系統，其特征在于：混合蛙跳算法中包含五個參數，種群大小F，子群數量m，子群內更新次數N，種群進化最大次數G，最大移動步數D_max；經過實踐確定F＝600，m＝20，N＝25，G＝200,D_max通常在5和10之間。

4.根據權利要求1所述的混合蛙跳算法的自適應核k-means方法與系統，其特征在于：在步驟3中，Φ(x)是非線性轉換，核函數通過Φ(x)可將n維空間中的任意隨機向量X映射到高維空間，核函數可以表示為κ(x_i,x_j)＝＜Φ(x_i),Φ(x_j)＞。

5.根據權利要求1所述的混合蛙跳算法的自適應核k-means方法與系統，其特征在于：該方法是自適應地，不需要為核k-means方法提前設置聚類數和核參數，而是根據不同數據的結構特征自適應地得到合適的參數，不僅可以處理具有不同結構的數據集聚類問題，還可以得到較好的效果。