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

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

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

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

（二）多維聚類的概念

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

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

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

所以多維聚類的問題定義為：

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

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

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

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

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

（四）隱樹模型的學習

隱樹模型的學習是一個對模型逐步優(yōu)化的過程，優(yōu)化的目標函數(shù)是一個稱為貝葉斯信息準則(Bayes information criterion， 簡稱BIC) 的函數(shù)：

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

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

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

（五）基于隱樹模型的多維聚類分析實例

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

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

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

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

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

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

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

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

（七）總結(jié)

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