大數(shù)據(jù)分析之—基于模型的復(fù)雜數(shù)據(jù)多維聚類分析

隨著現(xiàn)實(shí)和虛擬世界的數(shù)據(jù)產(chǎn)生速度越來(lái)越迅猛，人們開(kāi)始關(guān)注如何從這些數(shù)據(jù)中獲取信息，知識(shí)，以及對(duì)于決策的支持。這樣的任務(wù)通常被稱作大數(shù)據(jù)分析（BigData Analytics）。大數(shù)據(jù)分析的難點(diǎn)很多，比如，由于海量數(shù)據(jù)而帶來(lái)的分析效率瓶頸，使用戶不能及時(shí)得到分析結(jié)果；由于數(shù)據(jù)源太多而帶來(lái)的非結(jié)構(gòu)化問(wèn)題，使傳統(tǒng)的數(shù)據(jù)分析工具不能直接利用。

本文討論大數(shù)據(jù)內(nèi)部關(guān)系的復(fù)雜性，以及復(fù)雜數(shù)據(jù)所帶來(lái)的對(duì)于聚類分析的挑戰(zhàn)。聚類分析的目標(biāo)是依據(jù)數(shù)據(jù)本身的分布特征（無(wú)監(jiān)督），把整個(gè)數(shù)據(jù)（空間）劃分成不同的類?；镜臏?zhǔn)則是同類的數(shù)據(jù)應(yīng)該具有某種的相似性，而異類的數(shù)據(jù)應(yīng)該具有某種差異性?，F(xiàn)有工作假設(shè)在這些數(shù)據(jù)中存在單一的聚類劃分的方法，而聚類目標(biāo)就是找到這樣的一種劃分。然而，我們?cè)诖髷?shù)據(jù)中所面對(duì)的復(fù)雜數(shù)據(jù)是多側(cè)面的，比如在網(wǎng)頁(yè)數(shù)據(jù)中既有關(guān)于內(nèi)容的文本屬性，也有指向這個(gè)網(wǎng)頁(yè)的鏈接屬性。多側(cè)面數(shù)據(jù)本身就存在著多種有意義的劃分，強(qiáng)制地將數(shù)據(jù)按照單一的方法聚類，得不到有效的、明確清晰的、可詮釋的結(jié)果。針對(duì)這個(gè)問(wèn)題，多維聚類方法針對(duì)數(shù)據(jù)的不同側(cè)面，得到數(shù)據(jù)聚類的多種方法，最后讓使用者決定需要的聚類劃分。

高維復(fù)雜數(shù)據(jù)的聚類分析是本文作者在香港科技大學(xué)跟隨Nevin Zhang教授攻讀博士期間的主要工作。研究論文Model-based multidimensional clustering ofcategorical data發(fā)表在今年《ArtificialIntelligence》雜志的第176期?！禔rtificialIntelligence》從1970年開(kāi)始出版，是人工智能領(lǐng)域老牌頂級(jí)期刊。因?yàn)榘鏅?quán)原因，可能網(wǎng)上下載不到免費(fèi)的全文，感興趣的同學(xué)可以聯(lián)系tao.chen2@emc.com。關(guān)于文中所用的隱樹(shù)模型的介紹以及免費(fèi)軟件參見(jiàn)隱樹(shù)模型項(xiàng)目主頁(yè)。

（二）多維聚類的概念

假設(shè)我們需要對(duì)圖中的所有圖片進(jìn)行聚類，可能的聚類方法不止一種：按照?qǐng)D片的內(nèi)容，我們可以把左邊的圖片標(biāo)注成袋鼠，而右邊的標(biāo)注成樹(shù)；而按照?qǐng)D片風(fēng)格屬性，我們可以把上面的圖片稱為色彩圖，而下面的稱為線條圖。簡(jiǎn)而言之，關(guān)注數(shù)據(jù)的不同側(cè)面，有可能得到不同的聚類結(jié)果。同時(shí)這些聚類結(jié)果也都是有意義，可以解釋的。

生活中多維聚類的例子很多，比如對(duì)于人群的劃分，可以按照男女等人口統(tǒng)計(jì)學(xué)信息劃分，也可以按照對(duì)于某個(gè)事件的看法劃分。那么從機(jī)器學(xué)習(xí)的角度如何公式化這樣的問(wèn)題，之后又怎么利用概率統(tǒng)計(jì)的方法去解決這樣的問(wèn)題呢？下面我們先給出問(wèn)題的定義。

如圖所示，在聚類分析這樣的無(wú)監(jiān)督學(xué)習(xí)中，輸入是一個(gè)數(shù)據(jù)表。表的每一行表示一個(gè)數(shù)據(jù)點(diǎn)，而每一列表示描述這個(gè)點(diǎn)的一維屬性。大數(shù)據(jù)的一個(gè)重要特征就是維度很高（包含很多列），從而帶來(lái)的維度災(zāi)難（curseof dimensionality）。在聚類分析中，表現(xiàn)為：這些維度可能自然地分成一些組，每組包含一些屬性，反應(yīng)了數(shù)據(jù)某一側(cè)面（facet）的特征。用戶可以根據(jù)其中一個(gè)側(cè)面的屬性，對(duì)這個(gè)數(shù)據(jù)進(jìn)行聚類。比如在右表的數(shù)據(jù)中，一個(gè)學(xué)生的數(shù)據(jù)包含了數(shù)學(xué)成績(jī)，理綜成績(jī)，文綜成績(jī)，和語(yǔ)文成績(jī)這些屬性。我們可以關(guān)注學(xué)生的數(shù)學(xué)和理綜成績(jī)，按照理科成績(jī)（分析能力）對(duì)學(xué)生進(jìn)行聚類；同時(shí)也可以關(guān)注學(xué)生的文綜和語(yǔ)文成績(jī)，按照文科成績(jī)（語(yǔ)言能力）對(duì)學(xué)生進(jìn)行聚類。

所以多維聚類的問(wèn)題定義為：

如何發(fā)現(xiàn)數(shù)據(jù)中包含的多個(gè)側(cè)面，即屬性的自然分組，針對(duì)這些不同側(cè)面進(jìn)行聚類，從而得到多種聚類方法。

（三）多維聚類分析的工具和原理

貝葉斯網(wǎng)絡(luò)是一種表示和處理隨機(jī)變量之間復(fù)雜關(guān)系的工具。它是通過(guò)在隨機(jī)變量之間加箭頭而得到的有向無(wú)圈圖。箭頭表示直接概率依賴關(guān)系，具體依賴情況由條件概率分布所定量刻畫(huà)。出于對(duì)計(jì)算復(fù)雜度的考慮，人們會(huì)對(duì)貝葉斯網(wǎng)絡(luò)進(jìn)行一些限制，在實(shí)際中使用一些特殊的網(wǎng)絡(luò)結(jié)構(gòu)。隱樹(shù)模型（latent tree model）是一類特殊的貝葉斯網(wǎng)，也稱為多層隱類模型（hierarchical latent class model）, 是一種樹(shù)狀貝葉斯網(wǎng)， 其中葉節(jié)點(diǎn)代表觀察到的變量，也稱為顯變量，其它節(jié)點(diǎn)代表數(shù)據(jù)中沒(méi)有觀察到的變量，也稱為隱變量。

圖中給出了隱樹(shù)模型的一個(gè)例子。其中，學(xué)生的“數(shù)學(xué)成績(jī)”、“理綜成績(jī)”、“語(yǔ)文成績(jī)”和“文綜成績(jī)”是顯變量，而“智力”、“分析能力”和“語(yǔ)言能力”則是隱變量。從“分析能力”到“數(shù)學(xué)成績(jī)”有一個(gè)箭頭， 表示“數(shù)學(xué)成績(jī)”直接依賴“分析能力”，具體依賴情況由右圖中的條件概率表所定量所刻畫(huà)。表中的內(nèi)容是說(shuō)，分析能力低的學(xué)生在數(shù)學(xué)科有0.5的概率不及格、0.4的概率及格、0.1的概率得良，而得優(yōu)的概率則是0； 等等。模型中的其它箭頭代表其它變量之間直接依賴關(guān)系，每個(gè)箭頭都有相應(yīng)的條件概率分布。

在隱樹(shù)模型中，一個(gè)隱變量對(duì)應(yīng)一種數(shù)據(jù)聚類的方法。隱樹(shù)模型允許模型中有多個(gè)隱變量，所以自然地可以多維同時(shí)聚類。在例子模型中，可以按照分析能力或者語(yǔ)言能力對(duì)學(xué)生聚類，也可以按照智力對(duì)學(xué)生聚類。在隱樹(shù)模型中，聚類分析可以通過(guò)計(jì)算給定學(xué)生成績(jī)的后驗(yàn)概率進(jìn)行判斷。所以，利用隱樹(shù)模型進(jìn)行多維聚類分析的技術(shù)重點(diǎn)就在如何通過(guò)觀測(cè)數(shù)據(jù)學(xué)習(xí)一個(gè)最優(yōu)的模型。抽象地說(shuō)，就是找到能夠最好地解釋數(shù)據(jù)的一個(gè)生成隱樹(shù)模型（Generative Latent tree model）。

（四）隱樹(shù)模型的學(xué)習(xí)

隱樹(shù)模型的學(xué)習(xí)是一個(gè)對(duì)模型逐步優(yōu)化的過(guò)程，優(yōu)化的目標(biāo)函數(shù)是一個(gè)稱為貝葉斯信息準(zhǔn)則(Bayes information criterion， 簡(jiǎn)稱BIC) 的函數(shù)：

BIC(m|D) = max θ log P(D|m, θ) – d(m)logN/2

BIC準(zhǔn)則要求模型與數(shù)據(jù)盡量緊密地?cái)M合，但其復(fù)雜不能過(guò)高。所以式中第一項(xiàng)表示擬合程度，而第二項(xiàng)是對(duì)于模型復(fù)雜度的一個(gè)懲罰項(xiàng)。我們的優(yōu)化過(guò)程是一個(gè)基于搜索的爬山算法（Hill-Climbing）。以只包含一個(gè)隱變量的簡(jiǎn)單的隱樹(shù)模型作為搜索的起始模型，在搜索的過(guò)程中，逐步引入新的隱變量、增加隱變量的取值個(gè)數(shù)、或者調(diào)整變量之間的連接。這是一個(gè)逐步修改模型的過(guò)程，在這個(gè)過(guò)程中，模型與數(shù)據(jù)的擬合程度不斷改進(jìn)，從而B(niǎo)IC分逐步增加。當(dāng)模型就變得太復(fù)雜時(shí)，BIC會(huì)不升反降，于是搜索過(guò)程停止。

隱樹(shù)模型的學(xué)習(xí)是一個(gè)非常耗時(shí)的過(guò)程，主要原因在于對(duì)于BIC分?jǐn)?shù)的計(jì)算。BIC函數(shù)的第一項(xiàng)叫做最大似然函數(shù)，在模型包含缺失值或者隱變量時(shí)，計(jì)算最大似然函數(shù)需要調(diào)用EM（Expectation-Maximization）算法。盡管我們已經(jīng)對(duì)于限制了模型結(jié)構(gòu)為簡(jiǎn)單的樹(shù)狀結(jié)構(gòu)，但是在這樣的模型上進(jìn)行EM的計(jì)算依然是非常困難。圍繞隱樹(shù)模型的很多工作都是在研究如何對(duì)模型學(xué)習(xí)進(jìn)行加速的，這兒就不贅述了。

（五）基于隱樹(shù)模型的多維聚類分析實(shí)例

我們以一個(gè)真實(shí)的數(shù)據(jù)分析實(shí)例來(lái)展現(xiàn)多維聚類分析。數(shù)據(jù)來(lái)自某地區(qū)的關(guān)于貪污的社會(huì)調(diào)查問(wèn)卷。通過(guò)一些數(shù)據(jù)預(yù)處理，我們的數(shù)據(jù)（如圖所示）包含了1200份的問(wèn)卷，以及31個(gè)問(wèn)題。比如說(shuō)C_City表示被訪問(wèn)者對(duì)于該地區(qū)的貪污普遍性的看法，可以有4個(gè)選項(xiàng)，分別是非常普遍，普遍，不普遍，以及非常不普遍。C_Gov和C_Bus分別表示受訪者對(duì)于該地區(qū)政府部門(mén)或商業(yè)部門(mén)的貪污普遍性的看法，同樣也有四個(gè)選項(xiàng)。Tolerance_C_Gov和Tolerance_C_Bus則分別表示受訪者對(duì)于該地區(qū)的政府部門(mén)以及商業(yè)部門(mén)的貪污的容忍程度，可以選擇完全不能容忍，不能容忍，能容忍，完全能容忍。數(shù)據(jù)表里面的-1表示受訪者對(duì)該問(wèn)題的回答缺失。

利用隱樹(shù)的學(xué)習(xí)算法，我們從這個(gè)數(shù)據(jù)得到了一個(gè)如圖所示的模型。葉節(jié)點(diǎn)對(duì)應(yīng)問(wèn)卷問(wèn)題，即顯變量。中間結(jié)點(diǎn)，Y0-Y8是從數(shù)據(jù)中發(fā)現(xiàn)的隱變量，括號(hào)里面的數(shù)字表示這個(gè)變量所取的狀態(tài)個(gè)數(shù)。我們發(fā)現(xiàn)這些隱變量都有一定的意義，比如，Y2和問(wèn)卷中的Sex，Age，Income，Education這些問(wèn)題緊密連接，說(shuō)明Y2應(yīng)該是表示受訪人的人口統(tǒng)計(jì)信息。Y3和問(wèn)卷中的Tolerance_C_Gov和Tolerance_C_Bus緊密聯(lián)系，說(shuō)明Y3是反映受訪者總體對(duì)于貪污的看法。

模型中的每個(gè)隱變量表示數(shù)據(jù)聚類的一種方式。比如，變量Y2有4個(gè)值，說(shuō)明Y2提示數(shù)據(jù)可以分成四個(gè)類。這種聚類主要基于Sex，Age，Income，Education這些人口統(tǒng)計(jì)信息相關(guān)變量的，所以可以說(shuō)當(dāng)我們關(guān)注人群的人口統(tǒng)計(jì)信息這個(gè)側(cè)面時(shí)，我們可以根據(jù)Y2把人群分成四類。具體地研究這四類的類條件概率（Class-Conditional ProbabilityDistribution）特性，我們進(jìn)一步發(fā)現(xiàn)它們分別代表：低收入的年輕人群，低收入的女性人群，受過(guò)高等教育的高收入人群，以及只接受初等教育的一般收入人群。同時(shí)，我們看到Y(jié)3有3個(gè)取值，這說(shuō)明從人群對(duì)于貪污總體看法這個(gè)側(cè)面出發(fā)，可以把人群分成三類，分別是對(duì)于貪污完全不能容忍的人群，對(duì)于貪污比較不能容忍的人群，對(duì)于貪污可以容忍的人群。同樣地，我們的聚類也可以基于其他隱變量所代表的側(cè)面。這樣從模型中我們得到了9種聚類的方法，達(dá)到了多維同時(shí)聚類的效果。

除了聚類，對(duì)于這個(gè)數(shù)據(jù)的分析還告訴我們一些隱藏很深的關(guān)系。比如在模型中變量Y2和Y3有連線，這表明一個(gè)人的背景信息和他對(duì)于貪污的容忍程度應(yīng)該有一定的關(guān)聯(lián)關(guān)系。具體地說(shuō)，在Y2所表示的4類人中，你覺(jué)得哪一類是最能容忍貪污，而哪一類是最不能容忍貪污的呢？在模型中，通過(guò)對(duì)這兩個(gè)變量的條件概率的分析，我們得到了一個(gè)答案，有興趣的同學(xué)可以去論文中驗(yàn)證一下自己的猜測(cè)。

（六）相關(guān)學(xué)術(shù)工作

隱樹(shù)模型在密度估計(jì)，近似推理及隱結(jié)構(gòu)發(fā)現(xiàn)等方面都有具體的應(yīng)用。在多維聚類分析的應(yīng)用上，我們分析過(guò)市場(chǎng)學(xué)數(shù)據(jù)（COILChallenge 2000），某地區(qū)的社會(huì)調(diào)查數(shù)據(jù)（ICAC），NBA籃球運(yùn)動(dòng)員比賽統(tǒng)計(jì)數(shù)據(jù)。最近，隨著算法的提速，隱樹(shù)模型開(kāi)始被嘗試用于文本分析，比如對(duì)于網(wǎng)頁(yè)數(shù)據(jù)，博客數(shù)據(jù)等的話題分析。隱樹(shù)模型最開(kāi)始的提出是為了對(duì)中醫(yī)的證候分析提供統(tǒng)計(jì)解釋，有興趣的同學(xué)可以參考隱結(jié)構(gòu)模型與中醫(yī)證研究。

最近兩年，多維聚類分析引起了很多機(jī)器學(xué)習(xí)研究人員的興趣。從2010年開(kāi)始的MultiClust Workshop已經(jīng)舉辦了兩屆，其中第一屆是和KDD2010一起舉辦，第二屆是和ECML/PKDD2011一起舉辦。而第三屆也會(huì)與SDM2012一起舉辦。具體參考文獻(xiàn)這兒也不羅列了。

多維聚類分析和基于多視圖的學(xué)習(xí)不應(yīng)該混淆。多視圖學(xué)習(xí)假設(shè)數(shù)據(jù)的多個(gè)視圖已知，要求視圖之間存在充分性（Sufficiency）和冗余性（Redundancy），通過(guò)協(xié)同訓(xùn)練等技術(shù)，主要提高半監(jiān)督學(xué)習(xí)，主動(dòng)學(xué)習(xí)的性能。多視圖學(xué)習(xí)中針對(duì)聚類這樣的無(wú)監(jiān)督任務(wù)的研究很少，而且它的目標(biāo)也是如何提高單一的聚類劃分的質(zhì)量，而不是找到多種劃分方法。多視圖學(xué)習(xí)也極少涉及如何發(fā)現(xiàn)多個(gè)視圖，而不是假設(shè)他們已知。這方面南京大學(xué)周志華教授在今年的中國(guó)機(jī)器學(xué)習(xí)及其應(yīng)用研討會(huì)上提到一些初步研究。實(shí)際中，可以考慮先用多維聚類分析找到數(shù)據(jù)的多個(gè)側(cè)面（視圖），然后再應(yīng)用多視圖學(xué)習(xí)的方法。

（七）總結(jié)

對(duì)于一個(gè)復(fù)雜數(shù)據(jù)，比如文本，視頻，圖像，或者生物實(shí)驗(yàn)數(shù)據(jù)，人們可以從不同的角度去詮釋這樣的數(shù)據(jù)。數(shù)據(jù)分析家們已經(jīng)有了這樣的共識(shí)，那就是以前的單維聚類方法不再適合大數(shù)據(jù)的多樣性特征。多維聚類分析通過(guò)對(duì)單維聚類問(wèn)題的擴(kuò)展，為復(fù)雜數(shù)據(jù)提供了一種新的探索性分析的方式。我們通過(guò)找到數(shù)據(jù)的不同側(cè)面，按照這些側(cè)面進(jìn)行分別聚類，然后把各種聚類結(jié)果全部以一種簡(jiǎn)單的方式呈現(xiàn)給領(lǐng)域?qū)＜?，由專家決定他認(rèn)為最合適的聚類方法。這樣的工作流程清晰定義數(shù)據(jù)科學(xué)家和領(lǐng)域?qū)＜业穆毮?，通過(guò)兩者的合作，提高數(shù)據(jù)的聚類結(jié)果，并且提升數(shù)據(jù)的可解釋性。