一種基於最大‑最小信息素的k‑means數據處理方法與流程

2023-09-20 07:33:20

本發明涉及數據挖掘及模式識別
技術領域：
，尤其涉及一種基於最大-最小信息素的k-means數據處理方法。
背景技術：
：k-means算法是基於劃分的經典聚類算法，最早由MacQueen提出，其優點是簡單、易懂，算法思路清晰，數據收斂快速。處理密集型數據時，具有相對可伸縮性和高效性，聚類效果好。但是它的缺點也很明顯，算法對初始中心點的選擇和k值的確定以及孤立點比較敏感，並且容易陷入局部最優解。蟻群聚類算法是一種全局搜索仿生優化算法，最早由Deneubourg提出,根據聚類中心的信息素量把周圍數據聚集到一起，從而實現聚類。其優點是不需要提前劃分原始數據樣本，採用隨機搜索，算法靈活，可以避免局部最優。但仍存在一些缺點，算法收斂性差，運行時間較長。SaraSaatchi等人結合蟻群算法和k-means算法，提出一種基於信息素的k-means聚類算法，通過蟻群的全局搜索降低k-means算法陷入局部最優的可能性。但該算法採取傳統蟻群算法的信息素更新策略，收斂速度相對較慢。針對上述缺點，研究人員引入了精英適值保留機制提高了蟻群聚類算法的聚類效果；引入變異算子消除孤立點樣本的影響；並且通過MMAS(最大最小螞蟻系統)更改路徑信息素量，大大提高了全局搜索能力，有效地避免了過早收斂。但是在數據集比較大，維數比較高的時候，算法的時間消耗很大。基於信息素的k-means聚類算法進行幾次全局更新後，某些路徑(i,j)信息素τij可能快速趨於0，降低了螞蟻的搜索能力。技術實現要素：本發明要解決的技術問題在於針對現有技術中運算時間消耗大，且容易陷入局部最優解的缺陷，提供一種改善了收斂速度和總偏離誤差的基於最大-最小信息素的k-means數據處理方法。本發明解決其技術問題所採用的技術方案是：本發明提供一種基於最大-最小信息素的k-means數據處理方法，包括以下步驟:S1、獲取待處理的原始數據集，初始化蟻群參數，在原始數據集中標記隨機分配的聚類中心；S2、根據蟻群信息素計算原始數據集中未標記的數據到聚類中心的螞蟻轉移概率，根據計算結果對所有未標記的數據進行重新聚類，並計算各個數據到新的聚類中心的偏離誤差，選取偏離誤差最小的解作為精英螞蟻最優解；S3、設置最大信息素和最小信息素，根據精英螞蟻最優解更新全局的信息素，將信息素的大小限制在最大信息素和最小信息素的範圍內，並根據更新後的信息素進行聚類；S4、若滿足結束條件或達到最大迭代次數，輸出最優聚類結果；否則轉入步驟S2繼續執行。進一步地，本發明的步驟S3中設置最大和最小信息素的方法具體為：最大信息素τmax為：τmax=11-ρ1lk]]>最小信息素τmin為：τmin=τmax(1-Pbestn)(avg-1)Pbestn]]>其中，ρ為信息素揮發係數，k為聚類數目，l為螞蟻k獲取的路徑長度，n為螞蟻的數量，Pbest為發現最優解的概率，avg為可選路徑數。檢驗各路徑信息素，若大於τmax，則令其等於τmax；若小於最小值τmin，則令其等於τmin。進一步地，本發明的步驟S2中計算螞蟻轉移概率的方法具體為：螞蟻經過路徑(i,j)釋放信息素，求出未經標識數據對象Xi到的歐式距離dij並計算螞蟻轉移概率Pij，其中：t時刻，螞蟻經過路徑(i,j)釋放信息素的量τij(t)為：τij(t)=1dij≤R0dij>R]]>螞蟻轉移概率Pij為：Pij=τijΣj=1kτij]]>其中，R為聚類半徑初始值，dij為Xi到的歐式距離，待處理的原始數據集X＝{XXi＝(xi1,xi2,...,xin),i＝1,2,...,n}，隨機聚類中心進一步地，本發明的步驟S2中進行重新聚類的方法具體為：Pij與給定的轉移概率閾值q進行比較，若大於q,則標識Xi分配到處。進一步地，本發明的步驟S2中選取精英螞蟻最優解的具體方法為：根據聚類結果求出每一類聚類中心，計算原始數據集Xi到其對應聚類中心總的偏離誤差F，採取精英保留機制根據F值升序排序，選取最優解作為精英螞蟻的解，其中：總的偏離誤差F為：F=Σj=1kΣi=1mdist(Xi,Ci)]]>dist為歐式距離：distij=(Σk=1p(xik-xjk)2)12]]>其中，p為數據的屬性個數，m為蟻群規模。進一步地，本發明的步驟S2中還包括根據偏離誤差進行重新聚類的方法，具體為：根據設置的局部搜索閾值pls的大小對最優解的數據對象進行重新聚類，計算新聚類結果下總的偏離誤差Ft,若Ft小於F則保存，否則捨棄。進一步地，本發明的步驟S2中精英螞蟻最優解對應的路徑為當前迭代的最優螞蟻路徑，或全局最優螞蟻路徑。進一步地，本發明的步驟S3中更新全局信息素的方法具體為：路徑(i,j)信息素殘留量為：τij(t+n)＝(1-ρ)τij(t)+Δτbestij(t)若螞蟻經過路徑(i,j)，則否則其中，lbest為螞蟻遍歷一周最佳路徑長度，Q為一常量。本發明提供一種基於最大-最小信息素的k-means數據處理系統，包括：數據獲取單元，用於獲取待處理的原始數據集，初始化蟻群參數，在原始數據集中標記隨機分配的聚類中心；最優解計算單元，用於根據蟻群信息素計算原始數據集中未標記的數據到聚類中心的螞蟻轉移概率，根據計算結果對所有未標記的數據進行重新聚類，並計算各個數據到新的聚類中心的偏離誤差，選取偏離誤差最小的解作為精英螞蟻最優解；信息素更新單元，用於設置最大信息素和最小信息素，根據精英螞蟻最優解更新全局的信息素，將信息素的大小限制在最大信息素和最小信息素的範圍內，並根據更新後的信息素進行聚類；聚類結果輸出單元，用於判斷是否滿足結束條件或達到最大迭代次數，若滿足，則輸出最優聚類結果；否則轉入最優解計算單元繼續執行。本發明產生的有益效果是：本發明的基於最大-最小信息素的k-means數據處理方法，通過在基於信息素的k-means聚類算法中引入最大和最小信息素，在更新信息素時對各個路徑的信息素進行限定，能夠有效的避免信息素快速趨於0的情況發生，提高了全局的搜索能力，有效的避免了過早收斂；並且算法在聚類總偏離誤差上要優於現有算法，在時間消耗上也要少於現有算法。附圖說明下面將結合附圖及實施例對本發明作進一步說明，附圖中：圖1是本發明實施例的基於最大-最小信息素的k-means數據處理方法的流程圖；圖2是本發明實施例的基於最大-最小信息素的k-means數據處理方法的具體實施例的流程圖；圖3是本發明實施例的基於最大-最小信息素的k-means數據處理系統的框圖。具體實施方式為了使本發明的目的、技術方案及優點更加清楚明白，以下結合附圖及實施例，對本發明進行進一步詳細說明。應當理解，此處所描述的具體實施例僅用以解釋本發明，並不用於限定本發明。如圖1所示，本發明實施例的基於最大-最小信息素的k-means數據處理方法，包括以下步驟:S1、獲取待處理的原始數據集，初始化蟻群參數，在原始數據集中標記隨機分配的聚類中心；S2、根據蟻群信息素計算原始數據集中未標記的數據到聚類中心的螞蟻轉移概率，根據計算結果對所有未標記的數據進行重新聚類，並計算各個數據到新的聚類中心的偏離誤差，選取偏離誤差最小的解作為精英螞蟻最優解；S3、設置最大信息素和最小信息素，根據精英螞蟻最優解更新全局的信息素，將信息素的大小限制在最大信息素和最小信息素的範圍內，並根據更新後的信息素進行聚類；步驟S3中設置最大和最小信息素的方法具體為：最大信息素τmax為：τmax=11-ρ1lk]]>最小信息素τmin為：τmin=τmax(1-Pbestn)(avg-1)Pbestn]]>其中，ρ為信息素揮發係數，k為聚類數目；檢驗各路徑信息素，若大於τmax，則令其等於τmax；若小於最小值τmin，則令其等於τmin；S4、若滿足結束條件或達到最大迭代次數，輸出最優聚類結果；否則轉入步驟S2繼續執行。如圖2所示，在本發明的另一個具體實施例中，算法的具體步驟為：(1)初始化蟻群參數，給定待處理的原始數據集X,為其隨機分配的聚類中心。初始化信息素矩陣，聚類數目k，聚類半徑R,蟻群規模m，信息強度Q，信息素揮發係數ρ,轉移概率閾值q，局部搜索閾值pls和最大迭代次數t_max。待處理的原始數據集X＝{XXi＝(xi1,xi2,...,xin),i＝1,2,...,n}，隨機聚類中心(2)螞蟻經過路徑(i,j)釋放信息素，求出未經標識數據對象Xi到的歐式距離dij並計算螞蟻轉移概率Pij。t時刻，螞蟻經過路徑(i,j)釋放信息素的量τij(t)為：τij(t)=1dij≤R0dij>R]]>其中，R為聚類半徑初始值，dij為Xi到的歐式距離。數據轉移概率Pij為：Pij=τijΣj=1kτij]]>(3)Pij與給定的q進行比較，若大於q,則標識Xi分配到處,否則，轉到步驟(2)。(4)根據聚類結果求出每一類聚類中心，計算Xi到其對應總的偏離誤差F，採取精英保留機制根據F值升序排序，選取最優解作為精英螞蟻的解。總的偏離誤差F為：F=Σj=1kΣi=1mdist(Xi,Ci)]]>dist為歐式距離，如下所示：distij=(Σk=1p(xik-xjk)2)12]]>式中，p為數據的屬性個數。(5)根據pls的大小對最優解的數據對象進行重新聚類，計算新聚類結果下總的偏離誤差Ft,若Ft小於F則保存，否則捨棄。(6)利用精英螞蟻的最優解更新全局信息素。基於MMAS算法，利用最優路徑進行全局信息素的更新。路徑(i,j)信息素殘留量：τij(t+n)＝(1-ρ)τij(t)+Δτbestij(t)若螞蟻經過路徑(i,j)，則否則其中，lbest為螞蟻遍歷一周最佳路徑長度，Q為一常量。(7)根據MMAS(最大-最小螞蟻系統)，將各條路徑信息素量限制為[τmin,τmax]。最大信息素τmax為：τmax=11-ρ1lk]]>最小信息素τmin為：τmin=τmax(1-Pbestn)(avg-1)Pbestn]]>其中，螞蟻路徑可以是當前迭代的最優螞蟻路徑，也可以是全局最優螞蟻路徑。信息素更新完成後，檢驗各路徑信息素。若大於τmax，則令其等於τmax；若小於最小值τmin，則令其等於τmin。(8)滿足結束條件或迭代次數，輸出最優解，否則轉到步驟(2)繼續運行。為了驗證算法效果，利用UCI資料庫中的iris數據集和seed數據集進行實驗，iris數據集包括3種不同種類的植物，共有150條數據，每條數據有4種屬性；seed數據集包括3種小麥品種籽粒，共有210條數據，每種小麥品種籽粒70粒，每一粒小麥品種有7種屬性。實驗運行環境為MATLAB2015b,實驗參數ρ＝0.99，Q＝100，q＝0.98，迭代次數Nc＝100，螞蟻數量n＝50，記錄50次數據值(最優、平均值、最差值)。通過實驗比較傳統的k-means聚類算法(K)和基於信息素的k-means聚類算法(PK)以及基於最大-最小信息素的k-means聚類算法(CPK)的聚類總偏離誤差和時間消耗。如下表所示，對比三種算法在兩種不同的數據集上運行的結果得出，本算法的聚類總偏離誤差和基於信息素的k-means算法聚類總偏離誤差近似相同，且都低於傳統的k-means算法偏離誤差。表明所提出的基於最大-最小信息素的k-means聚類算法的聚類效果優於前兩種算法。對比基於信息素的k-means聚類算法和所提出的基於最大-最小信息素的k-means聚類算法的時間消耗，在MATLAB平臺中進行50次實驗，分別求取運行時間平均值，可得到下表。可以看出對於不同的數據集，所提出的基於最大-最小信息素的k-means聚類算法的時間消耗都要低於基於信息素的k-means聚類算法，表明此發明所提出的算法在時間消耗上要優於基於信息素的k-means聚類算法。本發明所要解決的技術問題是：數據集比較大，維數比較高的時候，算法的時間消耗很大。基於信息素的k-means聚類算法進行幾次全局更新後，某些路徑(i,j)信息素τij可能快速趨於0，降低了螞蟻的搜索能力。針對上述問題，提出一種基於最大-最小信息素的k-means聚類算法。所提出的基於最大-最小信息素的k-means聚類算法在聚類總偏離誤差F要優於傳統的k-means聚類算法。且在聚類總偏離誤差F和時間消耗上要優於基於信息素的k-means聚類算法。所採用的信息素更改方法避免了算法運行時因信息素量差異過大而失去對搜索空間的進一步探索。如圖3所示，本發明實施例的基於最大-最小信息素的k-means數據處理系統，用於實現本發明實施例的基於最大-最小信息素的k-means數據處理方法，包括：數據獲取單元，用於獲取待處理的原始數據集，初始化蟻群參數，在原始數據集中標記隨機分配的聚類中心；最優解計算單元，用於根據蟻群信息素計算原始數據集中未標記的數據到聚類中心的螞蟻轉移概率，根據計算結果對所有未標記的數據進行重新聚類，並計算各個數據到新的聚類中心的偏離誤差，選取偏離誤差最小的解作為精英螞蟻最優解；信息素更新單元，用於設置最大信息素和最小信息素，根據精英螞蟻最優解更新全局的信息素，將信息素的大小限制在最大信息素和最小信息素的範圍內，並根據更新後的信息素進行聚類；聚類結果輸出單元，用於判斷是否滿足結束條件或達到最大迭代次數，若滿足，則輸出最優聚類結果；否則轉入最優解計算單元繼續執行。應當理解的是，對本領域普通技術人員來說，可以根據上述說明加以改進或變換，而所有這些改進和變換都應屬於本發明所附權利要求的保護範圍。當前第1頁1&nbsp2&nbsp3&nbsp