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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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