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

李志偉

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

關(guān)鍵詞：譜聚類 特征向量選擇 熵排列

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2016）07-0043-01

1 簡介

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

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

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

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

假設(shè)K類數(shù)據(jù)集合，通過特征分解可以得到X的標(biāo)準(zhǔn)化的親合矩陣L的特征向量。那么，基于熵的特征向量排序方法如下：

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

（1）

其中，表示樣本的概率。實(shí)際應(yīng)用中我們不可能獲得每個(gè)樣本的概率。此時(shí)，我們將通過相似度替代概率來計(jì)算熵。

（2）

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

（3）

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

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

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

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

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

3 結(jié)語

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

參考文獻(xiàn)

[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.