[發明專利]一種兩階段混合粒子群優化聚類方法

有效

• 申請號: 201210109141.8
• 申請日: 2012-04-13
• 公開（公告）號: CN102663100A
• 公開（公告）日: 2012-09-12
• 發明（設計）人: 劉志鏡;王縱虎;王韋樺;陳東輝;屈鑒銘;賀文驊;王靜;姚勇;熊靜;唐國良;袁通;劉慧
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 田文英;王品華

技術領域

本發明屬于計算機技術領域，更進一步涉及數據挖掘技術領域一種兩階段混合粒子群優化聚類方法，本發明可以廣泛應用于數據壓縮、信息檢索、字符識別、圖像分割與文本聚類等，同時可在生物學、市場營銷和異常數據檢測等方面有廣泛的應用。

背景技術

聚類分析是數據挖掘中一種數據劃分或分組處理的重要手段和方法。它無需任何先驗知識，通過一定的相似性度量準則，把相似的樣本歸為一個類簇，聚類的目的是使同一類簇內樣本相似度較大，不同類簇之間樣本相似度較小。在生物學方面，聚類分析可以用來對生物的基因進行聚類，從而獲得對生物種群中一些固有結構的認識，還能用于植物和動物的分類；在商業數據分析方面，聚類技術被用來從客戶信息庫中發現不同的客戶群的特征，能幫助市場銷售人員準確掌握市場變化情況，及時調整銷售策略；在圖像處理方面，聚類可以直接用于進行初步圖像分割；另外，聚類也能用于對網絡上的大量文檔進行分類；聚類分析也可以作為分類算法或者其他算法的預處理步驟，經聚類得到未標記樣本的類別信息，然后利用這些標記樣本作為訓練樣本創建分類器。

聚類算法大體上可以分為劃分方法、層次方法、基于密度的方法、基于網格的方法和基于模型的方法，其中劃分方法和層次方法最為常用。層次方法是對給定的數據集合進行層次的分解。根據層次分解如何形成，層次方法又可以分為凝聚的和分裂的兩種。層次方法具有兩個基本優點：簇的數目不需要事先確定，它與初始條件是相互獨立的。層次方法的缺陷在于：它是一種靜態的聚類方法，已做的合并或分裂操作不能被撤銷，簇之間也不能交換數據對象，在某步沒有選擇好合并或分裂點的情況下，可能會導致低質量的聚類結果。如凝聚層次聚類算法在后期的后并中由于前期錯誤累積等原因容易將非同類子簇錯誤合并到一起。由于進行合并或分裂操作需要搜索和估算大量的對象或簇，使得層次方法的可伸縮性較差，同時由于缺乏關于全局狀態或簇的規模等信息，該方法可能對有重疊的簇的劃分失效。劃分方法則通過迭代重定位策略優化特定的目標函數，嘗試確定數據集的一個劃分。劃分方法主要有K均值和K中心點兩種類型。K均值算法對處理大數據集是相對可伸縮的和高效的，K中心點算法能在一定程度上消除K均值算法對孤立點的敏感性。劃分方法一般要求事先給定簇的個數，并且對初始值和噪聲數據敏感。由于劃分方法基于對象間的距離和對某種標準的優化進行聚類，這種方法只能發現球狀簇而不能發現任意形狀的簇，同時算法極易陷入局部最優。通過以上分析可以看出，層次方法和劃分方法的優缺點交錯對應，還沒有一種方法能同時具有它們的優點。

粒子群優化(particle?swarm?optimization，PSO)算法是一種基于群體智能的全局尋優算法，由于該算法收斂速度快，需要設定的參數少，且編程實現簡單，多數情況下比遺傳算法更快地收斂于最優解，而且可以避免完全隨機尋優的退化現象。最近，研究人員結合PSO的優點，提出了多種行之有效的粒子群優化聚類算法，大大降低了聚類結果對初始聚類中心的敏感性。

陶新民、徐晶等人在“一種改進的粒子群和K均值混合聚類算法”中提出了一種改進的粒子群優化和K均值混合聚類算法(《電子與信息學報》，2010年1期，32(1))。該算法在運行過程中通過引入小概率隨機變異操作增強種群的多樣性，提高了混合聚類算法全局搜索能力，并根據群體適應度方差來確定K均值算法操作時機，增強算法局部精確搜索能力的同時縮短了收斂時間。

中科院半導體研究所申請的專利“一種基于特征分析的粒子群聚類方法”(申請公布號：CN?101894294A，申請號：200910084161.2)公開了一種基于特征分析的粒子群聚類方法。該方法主要將原空間的數據點集的聚類轉換為對特征空間的新點集通過粒子群方法進行聚類，克服了需手動挑選合適特征的麻煩，對變換到特征空間的點作出進一步處理，比如尺度變換、歸一化處理等操作，有利于后續優化方法的應用。但其仍然存在的缺點是，核函數類型及其參數值需要人為選擇，矩陣特征變換需要額外消耗時間。

上述已有的粒子群優化聚類算法在粒子編碼時都直接對m個聚類中心的d維樣本向量進行編碼，當樣本維數較大時，計算量較大，且在進化過程中d維樣本的值在一定范圍內變化時可能會取到不符合樣本實際情況的數值而出現空簇。由于各維的取值范圍可能變化較大，造成粒子群搜索空間過大，在有限次迭代搜索時會影響算法的收斂速度和聚類效果。

發明內容

本發明針對上述現有技術的缺點與不足，提出了一種兩階段混合粒子群優化聚類方法。