[發明專利]一種面向K均值聚類算法的質心以及質心個數初始化方法

在審

• 申請號: 201811245231.3
• 申請日: 2018-10-24
• 公開（公告）號: CN109472300A
• 公開（公告）日: 2019-03-15
• 發明（設計）人: 徐小龍;徐浩嚴
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 董建林

本發明提供了一種面向K均值聚類算法的質心以及質心個數初始化方法，包括：將數據離散后，計算每一維度數據的信息熵；根據信息熵排序選出兩個混亂程度最低的數據，通過降維找出特征最小的方向作為X軸重新建立坐標系，生成新的兩維數據；通過Y軸數據繪制密度曲線，將已有數據分為若干簇；Y軸數據代替原來兩個信息熵較低的數據繼續進行計算，直到所有維度數據都參與運算；最終得到若干簇，通過原數據計算質心。本發明無需提供K值，對于未知簇個數的數據可以得到準確的K值，并且初始化質心后可以減少迭代次數，快速收斂，同時提高K均值算法的穩定性，滿足了對于簇的個數不明確以及隨機質心對結果影響較大的數據集的需求。

技術領域

本發明涉及一種數據聚類方法，屬于機器學習領域，主要用于實現初始化K均值聚類的K值以及質心，具體為一種面向K均值聚類算法的質心以及質心個數初始化方法。

背景技術

K均值算法(Lloyod,1982)是簡單而又有效的統計聚類算法，使機器能夠將具有相同屬性的樣本歸置到一塊兒。與分類不同，對于一個分類器，通常需要告訴它“這個樣本被分成哪些類”這樣一些標簽，在最理想情況下，一個分類器會從所得到的訓練集中進行“學習”，我們將這種提供訓練的過程稱為“監督學習”。但是在聚類下，我們并不關心某一類是什么，我們的目的是想將相似的樣本歸置在一起，這樣，一個聚類算法通常只要知道該如何計算樣本間的相似度并將相似樣本歸并到一起就可以操作了，因此聚類通常并不需要使用訓練數據進行學習，這在機器學習中被稱作“無監督學習”。K均值算法就是這種用于統計的無監督聚類技術。

K均值算法操作簡單、運算速度較快，能夠有效處理中小型數據集。但同時K均值算法也有不足之處，包含以下幾點：

(1)聚類結果不確定

K均值算法初始聚類中心是隨機選擇的，初始中心點選取的好壞會導致最終聚類效果。選取不同初始聚類中心，會使得最終聚類得到的類簇發生變化。除此之外，K均值算法一般采用準則函數為目標函數，準則函數中只存在一個全局最小值和N個極小值，這使得算法運算過程中，會陷入局部極小值，導致最終得到的不是全局最優解。

(2)聚類個數不確定

K均值算法中K表示聚簇個數，K的取值決定聚類結果。K值的選取需要根據實際的需求來確定，但通常情況下我們并不知道需將數據集聚為多少個類簇最合適，所以針對K值的選取依然有待解決。

(3)數據量大、算法時間復雜度較高

K均值算法的計算過程是一個不斷迭代的過程，為尋找合適的聚類中心，需要不斷的計算和調整才能對數據對象進行有效的聚類。這個過程中反復進行大量的對象間距離的計算，所以K均值聚類過程會消耗大量時間，降低聚類運算效率。

為了解決K值初始化問題，目前采用的方式是手肘法與輪廓系數法。這兩種方法都需要對數據進行多次聚類得到每次的聚類結果，再通過不同的評估標準來選取最優的K值。這兩種方法需要進行多次不同K值的K均值聚類，這使得算法開銷較大。

為了解決K值初始化問題，目前采用的方式是進行基于密度的聚類，根據密度的到簇，在求得質心作為K均值的初始質心。從層次聚類中提取K個簇，并用這些簇的質心作為初始質心。該方法通常很有效，但僅對下列情況有效，樣本相對較小，例如數百到數千(層次聚類開銷較大)，K相對于樣本大小較小。

本發明針對目前初始化K值與質心存在的問題，給出了一種開銷較小的初始化方法。

發明內容

針對現有技術的不足，本發明提供一種面向K均值聚類算法的質心以及質心個數初始化方法。相比傳統K均值聚類算法，本發明的算法無需提供K值，對于未知簇個數的數據可以得到準確的K值，滿足了對于簇的個數不明確以及隨機質心對結果影響較大的數據集的需求。

本發明采用的技術方案如下：