[發明專利]一種基于并行計算技術的K-means單屬性聚類算法處理機

無效

• 申請號: 201010133323.X
• 申請日: 2010-03-26
• 公開（公告）號: CN101819563A
• 公開（公告）日: 2010-09-01
• 發明（設計）人: 白樹仁;廖玉芳;謝健;趙福華;馬億旿;杜東升
• 申請（專利權）人: 湖南省氣候中心;湖南大學
• 主分類號: G06F15/16
• 分類號: G06F15/16
• 代理公司: 北京匯信合知識產權代理有限公司 11335
• 代理人: 王維新

技術領域

本發明涉及聚類算法領域，尤其是一種基于并行計算技術的K-means單屬性聚類算法處理機。

背景技術

K-means聚類算法是一個經典的聚類算法，大量應用于數據挖掘中。

盡管K-means聚類算法是個非常高效的聚類算法，但對大規模海量數據進行聚類時，仍然存在著計算時間長，不能及時提供計算結果的問題。

為了解決這個問題，有大量的研究者從并行計算方面著手，希望利用超級計算機的多處理器機制，來解決上述問題。但是，由于K-means聚類算法十分經典，其算法并不適合進行并行處理，導致很多并行處理效率低下，其在多個CPU的情況下，加速比只能維持在1.2-1.8左右。

聚類分析是發現數據在相似性方面的聯系，即數據的聚集模式。它是一種重要的人類行為，目前已經廣泛地應用于統計學、機器學習、空間數據庫、生物學和市場研究等領域，它正在蓬勃發展，且已經成為數據挖掘研究領域中一個非常活躍的研究課題。聚類挖掘方法有：劃分方法、層次方法、基于密度的方法、基于網格的方法、基于模型的方法。其中，基于劃分方法的K-means方法是由Mac?Queen最早提出并且最廣泛使用的。目前，世界上有很多人在進行K-means聚類算法的研究。

K-means算法比較簡單，首先隨機選取k個初始質心，其中k是想要劃分的簇的個數(聚類個數)，每個點指派到最近的質心，指派到一個質心的所有點的集合構成一個簇，接下來根據指派到簇的點，更新每個簇的質心，重復指派和更新過程，直到簇不發生變化或者質心不發生變化。當結果簇是密集的且簇與簇之間的區別明顯時，K-means方法的效果較好，對于較大數據集該算法具有較高的效率和相對的可伸縮性。

雖然K-means方法具有上述優點，但在應用中越來越多的研究者發現該算法存在一些缺陷，主要有：必須事先給出簇的數目，增加了用戶的負擔；并且聚類結果隨初始質心的不同而不一樣，有時甚至出現無解的情況；不適用于有分類屬性的數據；不適用于結果簇差別很大的數據集；對噪聲點和孤立點很敏感；后期收斂速度較慢；通常以局部最優結束；只能發現球狀簇。

許多文獻提出了針對K-means算法的改進方法，歸納起來主要有：結合遺傳算法的改進，結合免疫算法的改進，結合群智能的改進，結合模擬退火的改進。如Manish?Sarkar等人把進化算法思想引入聚類算法中提出了基于進化編程的聚類算法；Mali采用了聚類中心的浮點編碼方式，設計了浮點數交叉和變異算法，提高了遺傳聚類算法的搜索效率；Forgy提出了隨機選點的方法，也可以憑借經驗選取有代表性的點作為初始聚類中心；P.S.Bradley和UsamaM.Fayyad提出了基于取樣的方法來確定初始聚類中心；Babu?GP等人根據遺傳算法的原理提出以K均值算子來代替遺傳算法中的交叉算子，提出了一種混合遺傳聚類算法；劉靜，鐘偉才等提出的免疫進化聚類算法；行小帥等提出的基于免疫規劃的K-means聚類算法；劉靖明，韓麗川等提出了基于粒子群的K均值聚類算法。

近年來，David?Arthur和Sergei?Vassilvitskii提出K-means++算法。該算法依次迭代選取新的質心點，使得新選取的質心點比已選取的質心點更接近聚類中心，直到K個質心點全部選取為止，然后再用傳統的K-means算法進行計算。但是，該算法需要較多的迭代次數，才可以取得近似最優解。

雖然，現在科研人員提出了幾種并行化方案，但是其大多效率比較低下，難以取得讓人滿意的加速比。此外，現有技術的缺點可以是成本高，效率低，耗時間等類似問題。

發明內容

本發明的目的是，針對現有技術的上述不足，提供一種基于并行計算技術的K-means單屬性聚類算法處理機，解決了上述技術存在的不足，以串行計算的方式對K-means聚類算法進行根本改進，提高其計算效率，并在該串行算法的基礎上，進一步實現了并行化處理，是一種成本低，效率高，數據處理速度快的新技術。

為了達到上述設計目的，本發明采用的技術方案如下：