[發明專利]基于特征權重的全局K-均值聚類方法

無效

• 申請號: 201110208617.9
• 申請日: 2011-07-22
• 公開（公告）號: CN102254020A
• 公開（公告）日: 2011-11-23
• 發明（設計）人: 于昕;焦李成;惠轉妮;劉芳;曹宇;吳建設;王達;王爽;李陽陽
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 張問芬;王品華

技術領域

本發明屬于數據統計領域，涉及一種聚類方法。具體地說是提出了一種基于特征權重的全局K-均值聚類方法，用于解決聚類中常見的K-均值類方法的聚類結果不穩定的問題，在提高了方法的聚類準確度的同時得到了很穩定的聚類結果。

背景技術

聚類就是將一組數據劃分到各個類中的一個過程，從而使得類內距離最小化，類間距離最大化，即同一類中的數據盡可能的相似，而不同類中的數據盡可能的不同。聚類在數據挖掘，統計學，機器學習，空間數據庫技術，生物學以及市場營銷中起著很重要的作用。

近些年，在聚類的很多應用領域中數據變得越來越復雜。一個目標經常會用很多個屬性特征來描述，而對于聚類而言，有些屬性起著比較重要的作用，而另外一些屬性則只有很小的作用，甚至不影響對目標的聚類。目前很多(基于距離的)聚類方法對于這些復雜的多維數據的聚類不是很有效。這是因為K-均值的方法采用的是單純的歐式距離度量方法，即計算每個對象到各個聚類中心的距離，離哪個聚類中心的距離最短則屬于哪一類，很明顯這種計算方法將目標的每個屬性對聚類的重要性簡單的視為相等的，而實際上是各不相同的，所以特別當處理的是多維復雜數據的時候，這種傳統的K-均值方法就不是很有效了。

為了解決這個問題，目前主要有兩種技術：1.特征轉移技術；2.特征權重或者特征選擇技術。一般來說，特征轉移技術對于存在大量屬性對于聚類無關的這種情況并不適應。特征權重技術意即不同屬性對于聚類的重要性和不同目標對于每一類所起的作用都是不同的。它主要涉及兩個方向：有監督的方法和無監督的方法。在早期，提出了很多有監督特征權重方法的方法。近些年來，很多無監督的特征權重方法被提了出來。因為這些方法很多都是基于K-均值的處理過程，所以基本都是K-均值類方法。不同的是，在K-均值的每次迭代中，都引入了計算屬性權重值的步驟來優化權值和建立類別。

我們主要研究了無監督的特征權重技術，以其中一種經典的LAW-K-均值(局部屬性權值K-均值)方法作為代表進行研究。LAW-K-均值方法是在K-均值基礎上的一種局部屬性權重方法。為了確定目標屬于哪一類，該方法采用權重差異測試方法來對每一類的重要屬性組。之后又有一些學者對該方法進行了一些改進。H.Friguiand和O.Nasraoui引入了每一個目標屬于每一類的程度以及每一類的每一個屬性對于聚類的作用。Liping?Jing，，Michael?K.Ng，等人提出了一種熵權重K-均值方法，該方法采用屬性權重的熵來表示屬性對于識別每一類所起的作用。Tao?ying?Li和Yan?Chen通過對目標函數的修改而拓展了熵屬性權重方法。

下面深入地介紹兩種主要的相關方法。

1.LAW-K-均值

通過以上的介紹和分析，我們可以看出，LAW-K-均值方法是一種基于K-均值的方法，通過在該方法中引入局部屬性權重，使得方法的性能有了一定的提高，但是二者都是隨機的選擇初始的聚類中心，所以聚類結果的好壞依賴于初始聚類中心的選擇，所以依然存在K-均值類方法本身所固有的缺陷，即因為對初始聚類中心敏感而導致其聚類結果不是很穩定。而且，LAW-K-均值方法中屬性權重的確定也取決于初始點的選擇，這就使得該方法的聚類結果更易受到初始聚類中心的影響而變得更加的不穩定。所以我們要想使聚類的效果既保持很高的準確度，同時又很穩定，就要試圖使聚類中心的選擇不再是隨機確定的，而是根據一定的數學原理推導出來的合理的初始中心的選擇方法。

2.全局K-均值

2002年A.Likas等人提出了全局K-均值方法。該方法與K-均值方法的不同之處在于初始聚類中心點的選擇，但都采用K-均值進行聚類中心的更新。全局K-均值采用一種確定性地方法而不是隨機選取來產生初始聚類中心，所以全局K-均值方法不依賴于任何的初始參數值。Global開始只確定一個聚類中心，通過選取所有點的中心作為第一個初始的聚類中心，再通過K-均值更新，直到不再變好而停止更新，然后再選出第二個聚類中心，選取所有點中對應的聚類錯誤最小的那個點作為第二個聚類中心，再采用K-均值進行更新，直到找到K個聚類中心方法就會結束。這種方法因為其初始中心選取的改變使得方法非常穩定，因為所有初始點的選擇都是根據同樣的原理，所以都是確定性的操作，得到的聚類結果有所改善的同時也非常的穩定。