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

無效

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

1.一種基于特征權重的全局K-均值聚類方法，其特征在于：首先將數據聚為一類，其最優聚類中心為所有數據的質心，接著通過計算求出目標函數最小的數據點并將該數據點作為下一類的初始聚類中心，再利用帶有特征權重的“K-均值方法”迭代更新得到聚為兩類的最佳聚類中心，采用同樣的方法依次增加聚類中心數進行聚類，直到聚為設定的K類為止，從而完成將所有數據點聚為K類的整個過程，其具體實現步驟如下：

(1)輸入多維數據x_ij，1≤i≤N，1≤j≤D和聚類個數K，其中N表示數據的個數，D表示數據的特征屬性個數，x_ij表示第j個屬性的第i個數據點；

(2)初始化聚類個數k＝1

初始化第k類的特征權重值為D和d表示樣本的特征屬性個數，當k＝1時，即只聚為一類時，其最優的聚類中心就是所有數據的質心，把所有數據點的質心作為第一類的初始聚類中心，即

(3)進行k+1類聚類

1)找到第k+1類的初始最優聚類中心：

①前k類的聚類中心(Z₁，…，Z_k)和特征權值[λ₁，λ₂，…，λ_k]已求出，將(Z₁，…，Z_k)作為前k類的最優初始中心；

②將所有數據點依次作為第k+1個初始中心，且初始化第k+1類的特征權重值為

③以(Z₁，…，Z_k，X_i)作為聚類中心，X_i∈X，對所有數據進行N次聚類操作：

第一步：每次計算出每個數據點和每個聚類中心之間的特征權重歐式距離，通過公式(1)將數據點的特征權重歐式距離進行比較，然后把數據點劃分到距離最小的那一類：

whi=1ifΣj=1Dλk,jβ(zk,j-xi,j)2≤Σj=1Dλh,jβ(zh,j-xi,j)21≤h≤k+10otherwise---(1)]]>

式(1)中參數β＝1.8，w_hi表示第i個數據是否屬于h類，z_h，j表示第h類聚類中心的第j個屬性的值，λ_k，j第k個類別第j個屬性的權重值，k表示類別，h表示小于類別k的變量；

第二步：將聚類中心(Z₁，…，Z_k，X_i)，w_hi和[λ₁，λ₂，…，λ_k+1]代入以下目標函數：

J(W,Z,Λ)=Σh=1k+1Σi=1NwhiΣj=1Dλhjβ||zhj-xij||2---(2)]]>

(2)式中，W＝[w_i，j]是一個K×N的整數矩陣，Z＝[Z₁，Z₂，…，Z_k]是代表聚類中心的矩陣，Λ＝[λ_l，i]是一個K×D的特征權值的實數矩陣，將得到的值代入之后得出J(Z₁，…，Z_k，X_i)；

④選出第k+1初始最優中心，把每個J(Z₁，…，Z_k，X_i)進行比較，找出最小的J(Z₁，…，Z_k，X_i)，則相應的X_i是k+1類的初始最優聚類中心，即Z_k+1；

2)對得到的聚類中心(Z₁，…，Z_k，Z_k+1)進行優化更新：

①將所有數據點進行聚類，計算出每個數據點和每個聚類中心之間的特征權重歐式距離；通過(1)式將數據點的特征權重歐式距離進行比較，然后把數據點劃分到距離最小的那一類：

②將更新得到的w_hi帶入下面的式子，更新聚類中心z_hj：

zhj=Σi=1NωhixijΣi=1Nωhi,]]>1≤h≤k+1???????????(3)

③再將更新得到的w_hi和z_hj代入下式更新每一個數據的特征權重值λ_hj：

λhj=1Σt=1D[Σi=1Nωhi(zhj-xij)2Σi=1Nωhi(zht-xit)2]1/(β-1)]]>1≤h≤k+1????????????????????(4)

④將更新得到的w_hi，z_hj和λ_hj代入到以下目標函數進行計算：

JT(W,Z,Λ)=Σh=1k+1Σi=1NwhiΣj=1Dλhjβ||zhj-zij||2]]>

其中，W＝[w_i，j]是一個K×N的整數矩陣，Z＝[Z₁，Z₂，…，Z_k]是代表聚類中心的矩陣，Λ＝[λ_l，i]是一個K×D的特征權值的實數矩陣，將得到的值代入之后得出J^T，其中T代表運行更新次數，J^T則代表第T次運行得到的目標函數值；

⑤目標函數值如果滿足|J^T-J^T-1|≤10e-4，則執行步驟(3)進行k+1聚類，否則，返回步驟2)歩，對聚類中心進行更新優化直到滿足上述條件；

(4)判斷是否滿足終止條件

即判斷k+1＞K是否成立，成立則方法結束，否則返回第(3)步進行k+1類聚類。

2.根據權利要求1所述的基于特征權重的全局K-均值聚類方法，其特征在于，所述步驟1)找出的下一個類的最優初始中心，是所有數據點中使目標函數J達到最小值的數據點，將該數據點作為下一個類的初始聚類中心，從而使得聚集程度最優。