兩元矩陣聚類算法研究.pdf

1、聚類是人們認(rèn)識和理解世界的最基本方式之一，廣泛應(yīng)用于分子生物學(xué)、金融、市場、電子商務(wù)等眾多領(lǐng)域的數(shù)據(jù)分析。
　　 聚類的目標(biāo)是根據(jù)一個對象群體的屬性數(shù)據(jù)，基于相似性函數(shù)，尋找多個對象分組，使得同一組內(nèi)的對象相似度高，而不同組的對象相似度低。同組內(nèi)具有共同特征的對象稱為一個簇(cluster)。在計算對象相似性時，若將對象的全部屬性用于比較，即是人們通常所指的聚類，或稱為單向聚類;在一些應(yīng)用場合中，我們期望使用部分屬性而不是全部屬

2、性衡量對象的相似性，這種利用部分屬性來比較對象特征的聚類計算則稱為雙向聚類。雙向聚類結(jié)果中，同組內(nèi)具有共同特征的對象稱為一個雙向簇(bicluster)。
　　 聚類數(shù)據(jù)通常表示為實數(shù)矩陣，行對應(yīng)于對象，列對應(yīng)于屬性。對于單向聚類計算，恰當(dāng)?shù)刂嘏判蛐谢蛄泻?，簇在聚類矩陣中對?yīng)于條狀子矩陣;而對于雙向聚類計算，恰當(dāng)?shù)刂嘏判蛐泻土泻?，雙向簇在聚類矩陣中對應(yīng)于塊狀子矩陣。
　　 在眾多應(yīng)用領(lǐng)域中，聚類實數(shù)矩陣可簡化為元素均為0

3、/1的兩元矩陣。例如，在文本挖掘技術(shù)中，矩陣的行表示文檔，列表示關(guān)鍵詞。若文檔i中包含關(guān)鍵詞j，則矩陣的元素(i,j)值為1，否則為0。若一個子矩陣的元素均為1，則這個矩陣中的文檔含有相同關(guān)鍵詞，這些文檔可能屬于同一領(lǐng)域。此外，有時為便于分析或計算，也會將實數(shù)矩陣轉(zhuǎn)化為兩元矩陣。
　　 由于兩元矩陣的重要性和普遍性，兩元矩陣聚類分析算法廣泛應(yīng)用于市場購物籃分析、文本挖掘技術(shù)、基因表達(dá)譜分析、電子商務(wù)數(shù)據(jù)分析、社區(qū)發(fā)現(xiàn)等領(lǐng)域。本文

4、主要研究兩元矩陣上的兩個聚類問題:帶缺失值的兩元指紋向量聚類問題、兩元矩陣的k-子矩陣劃分問題。
　　 1.帶缺失值的兩元指紋向量聚類問題
　　 帶缺失值的兩元指紋向量聚類問題源自于計算生物學(xué)中的基因表達(dá)譜聚類分析。
　　 基因是控制生命體性狀的基本遺傳單位，它是基因組序列上的一個片段。了解基因的功能，對于我們研究生命奧秘至關(guān)重要。然而，在已測序的基因中，功能尚且未知的超過40％。如何快速、準(zhǔn)確推斷基因功能是目前

5、分子生物學(xué)亟待解決的問題。
　　 序列相似性比對是發(fā)現(xiàn)基因功能的一個重要方法，但遺憾的是在基因的一個功能家族中，基因序列相似性是很弱的，此外，還有一些基因，其功能是相同的，但沒有任何序列相似性，故不能完全依靠序列比對推斷基因功能。另外一種用來推斷基因功能的重要方法是DNA微陣列技術(shù)，此項技術(shù)是近年來發(fā)展起來的分子生物學(xué)革命性技術(shù)之一。DNA微陣列實驗產(chǎn)生的數(shù)據(jù)稱為基因表達(dá)譜。由于基因表達(dá)譜分析算法的重要性和極具挑戰(zhàn)性，使其成為當(dāng)

6、前分子生物學(xué)中研究的熱點問題。
　　 基因表達(dá)譜可表示為一個m×n實數(shù)矩陣A=[aij]m*n'行表示基因，列表示實驗條件。矩陣A的元素aij表示基因i在條件j下的表達(dá)水平?；虮磉_(dá)譜中存在較多數(shù)據(jù)未能真實反應(yīng)基因的表達(dá)水平，稱之為缺失數(shù)據(jù)（missing values）。在基因表達(dá)譜中，缺失數(shù)據(jù)可能會多達(dá)10％甚至更高，至少有一個缺失數(shù)據(jù)的基因占到90％以上。如何處理這些缺失值是分析基因表達(dá)譜的一個重要問題。
　　 聚

7、類是分析基因表達(dá)譜的重要方法。在大多數(shù)基因表達(dá)譜聚類算法中，或是沒有考慮缺失值，或是簡單地替之以隨機(jī)數(shù)。Figueroa、Borneman等人將基因表達(dá)譜轉(zhuǎn)換為0-1-N向量集，稱為兩元指紋向量集，提出了帶缺失值的指紋向量聚類計算問題，稱為帶缺失值的兩元聚類問題（the binary clustering with missingvalues problem，簡記為BCMV）。在聚類的同時，此算法考慮了如何通過計算確定缺失值的數(shù)值。記B

8、CMV(p)為含有常量參數(shù)p的BCMV問題，p表示指紋向量中缺失值個數(shù)均不超過p。Figueroa等給出了BCMV(1)的多項式時間精確算法;證明了BCMV(3)是NP-難的;給出了求解BCMV問題的啟發(fā)式算法—貪心圖劃分算法(GCP)及其散列表實現(xiàn)法。BCMV(2)的復(fù)雜性則一直沒有確定。本文討論了BCMV(2)問題的復(fù)雜性，以三元素嚴(yán)格覆蓋問題作為歸約問題，證明其為NP-難的。此外，本文基于Figueroa等給出的GCP算法，給出了

9、一種改進(jìn)實現(xiàn)方式:鏈表法。理論證明鏈表法的時間、空間復(fù)雜度均低于散列表法，求解速度快于散列表法。實踐表明，求解相同實例時，鏈表法計算耗時平均為散列表法的20％;當(dāng)計算缺失值位數(shù)超過6的實例時，鏈表法計算耗時幾乎總不超過散列表法的11％。此外，本文提出了求解BCMV問題的基于線性規(guī)劃舍入法的算法（theBCMV algorithm based on LP-rounding，簡記為BLP），其近似比為O(logn)。 BLP算法的速度略快于

10、GCP鏈表法。本文使用閔可夫斯基測度和雅可比相似度系數(shù)比較了BLP算法與GCP算法的聚類質(zhì)量，比較結(jié)果表明，BLP算法略優(yōu)于GCP算法。
　　 2.兩元矩陣的k-子矩陣劃分問題
　　 以矩陣A=[aij]m*n表示m個對象、且每個對象有n個屬性的數(shù)據(jù)集，其中aij表示第i個對象的第j個屬性值。雙向聚類的最簡單求解目標(biāo)是尋找矩陣行（對象）的一個子集，及列（屬性）的一個子集，使得此行子集中的對象在此列子集中的屬性下是高度相似

11、的。這樣的對象子集及屬性子集下的數(shù)據(jù)稱為雙向簇。如果雙向聚類問題的實例是兩元矩陣，則雙向聚類的目標(biāo)是在矩陣中尋找元素值全為“1”的子矩陣（雙向簇）。
　　 在許多應(yīng)用，雙向聚類的目標(biāo)是同時尋找多個子矩陣（雙向簇）。實際上，Madeira和Oliveira等人已經(jīng)討論了這個問題，并總結(jié)出了8種雙向簇解格式:行與列排他式、行排他式、列排他式、無重疊棋盤式、樹結(jié)構(gòu)無重疊式、任意重疊式等。本文所研究的兩元矩陣的k-子矩陣劃分問題屬于行列

12、排他式解格式的雙向聚類問題。兩元矩陣的子矩陣劃分問題(the submatrix partition of binary matrices problem，簡記為SPBM)是雙向聚類的一種計算模型。SPBM要求在兩元矩陣中尋找多個行、列排他，且元素均為1的子矩陣，且使得矩陣的每一行（列）出現(xiàn)且僅出現(xiàn)在一個子矩陣中。記k-SPBM為含有常量參數(shù)k的SPBM問題，k表示要求尋找的子矩陣為常數(shù)k個。
　　 本文中，我們討論了k-SPB

13、M的復(fù)雜性。證明中用到了單調(diào)三取一可滿足問題(MO3)和二分圖的二分團(tuán)k劃分問題(the partition of a bipartite into k bicliquesproblem，簡記為k-PBB)，其中k是一個正整數(shù)常量。MO3是由Schaefer證明的一個著名Np-完全問題;k≥3時，k-PBB的復(fù)雜性尚且是未知的。本文首先證明了MO3問題的一個變體形式是NP-完全的。然后，以此變體形式的MO3問題為歸約問題，證明了3-PB

14、B是NP-完全的，進(jìn)而證明了k-PBB(k＞3）亦是NP-完全的。最后，以k-PBB（k≥3）為歸約問題，證明了k-SPBM（k≥3）是NP-完全的。
　　 此外，本文還給了一個求解k-SPBM算法的指數(shù)精確算法。
　　 本文的進(jìn)一步研究工作主要包括二個方面:
　　 1.真實世界的數(shù)據(jù)大多是有噪聲的數(shù)據(jù)，如分子生物學(xué)領(lǐng)域的基因表達(dá)譜、物聯(lián)網(wǎng)領(lǐng)域的傳感器數(shù)據(jù)、金融領(lǐng)域的股票數(shù)據(jù)等。因此，設(shè)計可以處理噪聲數(shù)據(jù)的方法是

15、十分必要的。目前，對于聚類分析，用于處理噪聲數(shù)據(jù)的方法大體可分三類:圖方法、貝葉斯法、概率法。準(zhǔn)二分團(tuán)法(quasi-biclique)是圖方法中的主要方法。初步猜想準(zhǔn)二分團(tuán)問題的兩個變體形式:最多邊準(zhǔn)二分團(tuán)、準(zhǔn)二分團(tuán)劃分問題均是NP-難的，下一步將嘗試證明這類未解決問題的復(fù)雜性，并設(shè)計求解算法。
　　 2.盡管不存在比較聚類算法性能的“黃金標(biāo)準(zhǔn)”，但是如何針對不同數(shù)據(jù)，選擇恰當(dāng)?shù)木垲愃惴ǎ咳绾伪容^某些算法的性能？仍是非常重要的