譜聚類中基于熵排序的特征向量選擇方法

李志偉

摘要：Ng-Jordan-Weiss（NJW）是使用最廣泛的譜聚類算法之一。對于一個K類問題，該算法使用數據集標準化的親合矩陣的最大的K個特征向量來劃分數據。已經證明，K-way劃分的譜放松解決方法在于對這K個最大的特征向量子空間的劃分。然而，從大量實驗表明，前K個最大的特征向量并不總能檢測得出真實的模式識別問題的數據結構。所以，譜聚類中特征向量的選取變得很有必要。

關鍵詞：譜聚類 特征向量選擇 熵排列

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1007-9416（2016）07-0043-01

1 簡介

聚類方法一直是模式識別和人工智能研究的重要焦點之一。聚類的目的在于將數據劃分成預期的結果。比如，數據的聚類就是將相似的樣本劃分為一類，不相似的樣本歸到不同類中。在過去的幾十年里，許多聚類算法得到了快速發展，這主要包括基于層次的聚類（如單鏈接、多鏈接等）和基于劃分的聚類（如K-means、高斯融合模型、密度估計和模式選擇等）。當數據集變的十分龐大，很多維數對應的屬性對于聚類而言就經常變得不相關。為了克服這一問題，子空間學習算法被提出，用于將原始高維空間中的樣本映射到低維空間中，得到一種更能夠很好反應出原始數據樣本的新屬性。子空間學習應用已經應用到了很多研究領域，比如：費希爾線性降維分析擴展、流型學習、譜分析、核機器、張量機等領域。

譜分析方法已經成功用于解決大數據聚類和圖像分割問題。近年來，由于譜聚類對于數據聚類具有高性能且具有使用簡單的優點，吸引了越來越多的研究者的興趣。這種方法已經成功應用于并行計算、VLSI設計、圖像分割、語音分離等方面。譜聚類方法使用數據標準化的親合矩陣的特征向量來劃分數據。而NJW方法是最廣泛使用的譜聚類算法之一。對于K個聚類問題，該方法使用數據集標準化的親合矩陣的K個最大的特征向量劃分數據。盡管標準割的譜放松解決方法在于對子空間中的特征向量的劃分。但不能保證這K個最大的特征向量總能檢測得出數據的結構。

基于熵排列的特征向量選擇方法是根據特征向量對聚類的重要性對它們按序排列，然后從排列列表中得到合適的特征向量組合。在排列列表中選擇特征向量時，有兩種策略。其一，直接從排列列表中選擇前K個特征向量。盡管這種方法使用了K個最重要的特征向量，但仍不是總能很好地檢測出數據的結構。所以，這種方法的性能比NJW方法優越不多。由于譜聚類中選擇的特征向量應該是一個組合優化問題，所以另外一種選擇策略，即在排列列表中選擇前Km（Km>K）特征向量的最優特征向量組合。基于在許多情況下，對于一個數據樣本的抽樣能夠保留原始聚類的信息這種假設，這種策略先對原始數據集描繪出一種訓練數據集，在排列列表的前Km（KM>K）特征向量中提取對應的訓練數據，并使用一種特征向量組合評價標準找出合適的特征向量組合，這種策略稱為間接特征向量選擇策略。

2 基于熵排序的特征向量選擇

假設K類數據集合，通過特征分解可以得到X的標準化的親合矩陣L的特征向量。那么，基于熵的特征向量排序方法如下：

根據信息熵理論，Dash等人提出一種使用熵排序來反應數據的特征。設表示X的標準化的親合矩陣L的所有的n個特征向量。將V視作包含具有n個特征的n個樣本的數據集，V的第i行表示第i個樣本數據，表示數據點的第j個特征。從熵理論得知，V的熵被定義為：

（1）

其中，表示樣本的概率。實際應用中我們不可能獲得每個樣本的概率。此時，我們將通過相似度替代概率來計算熵。

（2）

其中，為樣本和樣本之間的相似性。，為樣本和樣本之間的距離，計算公式如下：

（3）

其中，和分別表示第k個特征向量的最大值和最小值，所以表示第k個特征向量的最大區間。

根據對的定義，若和相距越近，則它們之間的相似性就越高；反之，相似性就越低。但若較低或較高時，熵就越小；反之，則大。因此，若除去特征向量要比除去更能導致樣本的無序，且熵滿足，則要比的對譜聚類更重要。為了得到特征向量的排序，每個特征向量都要被移除并計算對應的熵。用表示排序后（降序）的特征向量。并將樣本集合作為實例，若5個特征向量的熵滿足時，則熵的排列列表為。所以，在這5個特征向量中第4個特征向量是最重要的。

在得到特征向量排序列表后，其中一個簡單的特征向量選擇方法就是直接選擇列表中的前K個特征向量參與譜聚類。與NJW方法中的選取最大的K個特征向量有所不同，這K個特征向量而是通過熵排列得到的對聚類有重要作用的K個向量，稱這種特征向量選取為直接選擇策略。

另外一種選擇策略是根據特征向量排序列表尋找合適的向量組合。眾所周知，一個數據集的所有的數據點可看作是隨即抽取的。所以，隨即抽樣的數據多數情況下都保留著原始聚類的信息。而實際應用中，獲取某個數據的真實標記信息是可能的。因此，本文首先描述原始數據集的帶有真實標記信息的訓練數據，然后在排序列表中抽取對應訓練數據集的前Km（Km>K）個特征向量，并借助特征向量組合評價指標在所有可能的向量組合中找出最佳的向量組合。我們認為這個最佳的特征向量在子空間中映射到的訓練集合中的數據點能夠反應得出原始數據的潛在數據結構。

排列列表中的前Km（）個特征向量被認為是對聚類最重要的特征向量。所以，我們的目的就在于在這Km個特征向量中獲取K個最佳的特征向量組合。當K不大時（如），對數據聚類至關重要的這Km個特征向量就會更少，所以，在Km=10個特征向量中能夠足夠找出一個較好的特征向量組合。

3 結語

本文介紹的熵排列的特征向量選取方法是一種簡單的特征排列方法，也可以選擇一種多套特征向量排列方法用于特征向量的排序。本文旨在通過熵排序的特征向量選取方法，獲取能夠表征信息的最優特征。在將來的工作中將進一步在這個方向上研究。

參考文獻

[1]Zhao F，Jiao L C，Liu H Q，et al. Spectral clustering with eigenvector selection based on entropy ranking[J]. Neurocomputing，2010，73（10）：1704-1717.