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

在審

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

技術領域

本發明提出一種自適應核k-means方法，設計了適用于核空間的有效性指標，將k-means方法中的聚類數和核參數作為青蛙的位置信息，將有效性指標作為適應度，利用混合蛙跳算法進行局部和全局優化，找到青蛙的最優位置，無需人為設定參數，自適應地得到有效的聚類結果。

背景技術

作為數據挖掘的重要研究課題，聚類分析是識別數據內在結構的重要方法。聚類的目標是滿足屬于同一類的數據具有較高的相似度，而屬于不同類的數據具有較低的相似度。k-means聚類算法是使用最廣泛的聚類算法之一。該算法介意在較短的時間內處理大量的數據集且有較好的結果。但是它只能處理呈超球形分布的數據集，對于具有復雜結構的數不能得到合理的結果。

最近幾年，為了處理輸入空間中呈非線性分布的數據集，提出了基于核的聚類方法。通過將輸入空間的數據間接映射到高維特征空間，核聚類方法能夠發現輸入空間中非線性可分的簇。特征空間中計算線性劃分的結果等價于輸入空間中非線性劃分的結果。實驗結果表明核聚類方法通常優于對應的經典聚類算法。在所有的基于核聚類的算法中，核k-means由于其簡潔性及高效性引起了廣大學者的關注。

在核k-means中，核矩陣的結構是影響算法結果的關鍵因素。核參數很大程度上會影響聚類算法的泛化能力和學習能力，所以選擇一個合適的核參數使得核空間的數據線性可分是非常重要的。此外，核k-means需要先驗知識，比如聚類數。實際中，缺乏豐富的聚類分析經驗的用戶，很難準確地設定數據集的聚類數目，這限制了聚類算法的應用。為了處理這些問題，提出一種混合蛙跳算法的自適應核k-means方法與系統。

倒立擺控制系統是一個不穩定、復雜的、非線性系統，是檢驗控制理論和方法的理想模型和進行控制理論教學及開展各種控制實驗的理想實驗平臺。對倒立擺系統的研究能有效的反映控制中的許多典型問題如非線性問題、魯棒性問題、鎮定問題、隨動問題以及跟蹤問題等。對倒立擺的控制通常用來檢驗新的控制方法是否有較強的處理非線性和不穩定性問題的能力。同時，倒立擺的控制方法在軍工、航天、機器人和一般工業過程領域中都有著廣泛的用途。目前，國內外對于倒立擺系統的研究主要是采用倒立擺系統的數學模型，使用更為先進的控制算法對倒立擺進行控制，檢驗算法的有效性，對算法進行理論驗證，并作為實驗教學平臺進行使用。

發明內容

本發明的目的是設計一種自適應的核k-means方法，對于不同結構的數據集，自動確定核參數和聚類數目，最終得到有效的聚類結果。

為了實現上述目的，本發明采用以下技術方案：

設計了有效性指標核類間類內比KBWP，將KBWP看作適應度函數，利用混合蛙跳算法進行優化得到最佳核參數和聚類數，最后得到核k-means聚類的結果。

具體的步驟如下：

步驟1：導入數據集，隨機初始化青蛙種群X_i，i＝1,2,...,F，青蛙的位置信息表示優化參數；

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

步驟3：根據計算得到新的聚類中心，更新每個類Φ是映射函數；

步驟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；