[發明專利]基于熵排序的半監督譜聚類確定聚類數的方法

無效

• 申請號: 201010278767.2
• 申請日: 2010-09-09
• 公開（公告）號: CN101968852A
• 公開（公告）日: 2011-02-09
• 發明（設計）人: 張向榮;焦李成;楊杰;侯彪;王爽;公茂果;劉若辰;李陽陽
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱紅星

1.一種基于熵排序的半監督譜聚類確定聚類數的方法，包括如下步驟：

(1)輸入數據集X＝{x₁，x₂，...，x_n}∈R^d，x_i表示數據集中的任意點，i∈(1，n)，n為數據個數，d表示數據維數；

(2)分別計算數據集X中各個點的尺度參數σ_i和數據集的親和度矩陣A；

(3)由人工加入的類標簽提取成對約束信息，并用這些成對約束信息對親和度矩陣加以修正其中must-link限制兩個樣本點必須屬于同一類；cannot-link限制兩個樣本點不能處于同一類；

(4)用修正后的親和度矩陣構造拉普拉斯矩陣：L＝D^-1/2AD^1/2，其中D為對角矩陣，對角線上的任意元素

(5)對拉普拉斯矩陣進行特征分解，并按照特征值的大小將對應特征向量從大到小排列；

(6)用熵排序方法對特征向量按其重要度進行重排序：

(6a)依次移出特征向量的每一列，計算其余列熵值，將求得的熵值規定為該列特征向量對應的熵值；

(6b)將特征向量按照其對應的熵值從大到小進行一次“重排列”，得到特征向量重要度由高到低的排序，記為VR；

(7)初始化聚類數k＝2，取VR的前k列并歸一化；

(8)自適應確定聚類數：

(8a)把取得的VR前k列看成n個k維的點，將其投射到k維坐標系；

(8b)用每個坐標軸的正負方向分別表示一個聚類，根據每個點距坐標系各個半軸的距離將輸入數據點劃分為2k類；

(8c)除去2k類中沒有點的類或者點數少于輸入數據點數百分之一的聚類，將保留下來的聚類數記為c；

(9)比較k和c，如果二者不同，令k＝c，返回步驟(8)，如果相同，此時所得的k就是最佳聚類數，記為km；

(10)將輸入數據點劃分至km類，并按輸入點的坐標對輸入數據點進行標記，得到聚類結果。

2.根據權利要求1所述的確定聚類數的方法，其中步驟(2)所述的分別計算數據集X中各個點的尺度參數σ_i和數據集的親和度矩陣A，用以下公式計算：

σi=1mΣd=1m||xi-xd||]]>

其中，σ_i表示數據點中任意點的尺度參數，x_d是數據級X中任意點x_i距其余各點的第d個近鄰，選擇d＝7；

A_ij＝exp(-‖x_i-x_j‖²/σ_iσ_j)，i，j∈(1，n)

其中，A_ij表示親和度矩陣A的任意元素，σ_i，σ_j分別表示數據集中任意點x_i和x_j對應的尺度參數，‖x_i-x_j‖表示點x_i和x_j的歐氏距離。

3.根據權利要求1所述的確定聚類數的方法，其中步驟(6a)所述的計算其余列熵值E，由下式計算：

E=-ΣVi∈V[p(Vi)logp(Vi)+(1-p(Vi))log(1-p(Vi))]]]>

其中V表示拉普拉斯矩陣的特征向量，V_i表示該特征向量中的任意列，p(V_i)表示V_i列的概率，由于實際中該概率不容易得到，具體操作中用特征向量V_i列與其他任意列的親和度S_ij代替，即

S_ij＝exp(-‖V_i-V_j‖²/σ_iσ_j)

E=-ΣVi∈VΣVj∈VEi=-ΣVi∈VΣVj∈V[SijlogSij+(1-Sij)log(1-Sij)]]]>

其中，σ_i，σ_j分別表示特征向量任意列V_i和V_j對應的尺度參數，‖V_i-V_j‖表示特征向量V_i和V_j列的歐氏距離。