基于流形學習的自適應反饋聚類中心確定方法

李天龍+吳晟+吳興蛟+周海河+曹敏+王昕

引言

現如今，數據存在于我們生活的每一個角落，在大數據快速發展的今天，數據挖掘成了進行數據分析的有效途徑，同時也是獲取數據信息的關鍵。

在海量數據下進行研究要求對于數據規律的探索，數據的聚類就顯得尤為重要，目前對于聚類算法的研究大致歸納為五大類，分別基于分割、層次、密度、網格和模型。上述的許多聚類算法都在實際中得到了較好地運用，同時也取得了一些效果，但是這些方法都存在一個共同的不足就是需要人工調參。這種方式將給自動化生產編程帶來一定限制。

正是由于存在上述問題，尋找一種能反饋調節聚類參數的算法就有其必要。

本文在對譜聚類算法進行探究以后，提出一種基于目標條件的反饋聚類。這種聚類方式對于大多數線性流形聚類參數選擇具有一定適應性。

1相關理論

流形學習聚類隨著高維大數據問題被提出，經過幾年的研究與探索，人們提出了大量的流形學習的理論與算法。比較典型的算法有ISOMAP、LLE、拉普拉斯算子特征映射（Laplacian eigenmaps）、最大方差展開（MVU）、局部切空間分析（LTSA）等。聚類，顧名思義就是根據樣本間相似度，將數據分成不同組。其中譜聚類是流形聚類中具有代表性的一種聚類方式。

譜聚類主要由以下四個步驟步組成：

Step1，構建相似度矩陣，即計算每個數據點與其余數據點的相關系數。

Step2，計算拉普拉斯矩陣，并將其進行歸一化；

Step3，生成最大的k個特征值和對應的特征向量；

Step4，采用k-means方法對特征向量進行聚類。

2模型建立

提出的反饋聚類算法主要基于譜聚類實現，聚類數目首先隨意指定，在一次聚類結束后將聚類結果代入目標中驗證，如果未達到目標閾值則調整聚類數，進行新的聚類，直到所得聚類結果滿足聚類目標。得到結果后經過多次迭代后計算聚類數的加權平均以后得到的聚類數。反饋聚類流程圖如圖1。

2.1數據集設置

譜聚類的前提是構造相似矩陣，這就要求將不同構型或者不同維數的數據進行處理。一般根據特征值或者矩陣實際運用得到新的n階方陣。

2.2構造相似度矩陣

基于譜聚類的方法是建立在譜圖理論基礎上，其基本思想是將樣本看作頂點，樣本間的相似度看作帶權的邊，從而將聚類問題轉為圖分割問題，即找到一種圖分割的方法使得連接不同組的邊的權重盡可能低，組內的邊的權重盡可能高。與傳統的聚類算法相比，其具有能在任意形狀的樣本空間上聚類且收斂于全局最優解的優點。可根據公式1構造聚類相似矩陣。

2.3反饋譜聚類

建立如下譜聚類模型：

Step1：輸入一個MN的矩陣w，即w中一共包含N個數據點；

Step5：計算矩陣L的歸一化矩陣E的k個最大特征值及對應的特征向量，形成一個N K的特征矩陣，記為Q；

Step6：對特征矩陣Q做k-means聚類，得到一個N維向量c，c中分別對應相似度矩陣w中每一行所代表的對象的所屬類別，即最終的聚類結果。

Step7：驗證聚類結果包含目標最大子集數是否大于閾值，大于閾值則得到結果，否則調整聚類數執行Step6。

Step8：多次迭代算法得到聚類列表ListC。

2.4計算加權平均

得到列表ListC以后，針對列表中的數求加權平均數成為新的聚類數。如公式5。

3實例驗證

3.1數據集設置

實驗數據取自2016年研究生數學建模B題數據。

先從數據清洗，缺失值處理以及數據變換方面進行預處理。

數據清洗，主要通過數據統計查看有無存在ATCG四種堿基以外的其他構成。尋找到除了ATCG以外，數據還存在I和D，后來根據官方文件修正為T和C。

缺失值處理，使用函數查看數據有無空值，最后發現無缺失現象。不必進行插值以及增補。

數據變換，由于數據直接使用ATCG字符難以計算距離，所以對其進行編碼形成編碼文件。

首先將文件gene info導入后根據每一條基因對應的位點構建合適的堿基對矩陣，構建相似矩陣。

附件gene info文件夾中有300個dat文件。每個dat文件數據表示每個基因的位點信息，每個dat文件表示一個基因。和附件文件genotype.dat中的位點信息相結合進行數據挖掘和分析。附件所給出的數據格式不能滿足數據挖掘的要求，所以進行數據預處理。

將附件給出的300個文件合并導入EXCEL文件中，并對基因從上到下依次編號。局部結果如表1所示。

數據的初級預處理得到如表2所示的數據格式，表的第一列為300個基因編號，其余列為基因的位點信息。由于基因含的位點數目不同，所以在基因信息和位點信息合并時需要對缺省基因進行補缺省值得處理，采用補0。把基因位點對應表和genotype.dat導入MATLAB進行數據的第二步數據預處理，把兩個數據相互融合。以編號為l的基因為例，融合后得到如表所示的數據形式。

300個基因的數據格式如基因1位點信息格式。經過兩步數據的預處理，數據的各項要求滿足數據挖掘的信息。

3.2模型求解

硬件環境：2.6 GHz CPU，8G內存。

軟件環境：Windows7，matlabR201 3a。

根據反饋聚類操作流程，如圖2，在1000"9446高維矩陣下，設定參數最大子集閾值為4，迭代次數為100。使用MATLAB實現流行聚類算法，本文采用譜聚類方法對數據進行100次聚類分析，每次聚類會產生一種聚類分組，從基因組中選取滿足致病基因覆蓋點大于等于4的基因組作為候選組。執行完成算法后會產生100組候選數據。使用統計學方法統計100個候選組基因出現次數最多的基因。并計算中位數以及加權平均數描繪其實時曲線，進行對照。

4實驗結果與分析

迭代一百次以后，統計聚類次數，得到各次聚類曲線圖，分別計算聚類集合中位數以及聚類集合加權平均數，如圖3所示。

觀察曲線可以初步得知加權平均數更能體現統計規律。

分別將得到的中位數以及加權平均數進行聚類。得到聚類后數據與統計數據對比，對比圖4，圖5中包含統計值的數量。

最后對比得出，使用加權平均分類數得到的聚類集合更能體現統計數據。

5結論

通過反饋譜聚類方法迭代后的中位數以及加權平均數來確定聚類數，改善了流形聚類中聚類數難以確定的難題，通過不斷的適應目標從而調整聚類數，然后再通過不斷迭代后的加權平均數來得到最后的聚類值。再和得到的中位數進行聚類效果的比較，這種方式下得到的結果是：使用加權平均數獲得的聚類數更加鍥合要求。endprint