0. 引子
傳說(shuō)：“聚類是人類最原始的精神活動(dòng)，用于處理他們每天接收到的大量信息”。為方便廣大同學(xué)學(xué)習(xí)使用，將我學(xué)習(xí)聚類時(shí)的筆記整理發(fā)布共享。
1. 聚類定義
“聚類是把相似的對(duì)象通過(guò)靜態(tài)分類的方法分成不同的組別或者更多的子集（subset）,這樣讓在同一個(gè)子集中的成員對(duì)象都有相似的一些屬性。” ——wikipedia
“聚類分析指將物理或抽象對(duì)象的集合分組成為由類似的對(duì)象組成的多個(gè)類的分析過(guò)程。它是一種重要的人類行為。聚類是將數(shù)據(jù)分類到不同的類或者簇這樣的一個(gè)過(guò)程，所以同一個(gè)簇中的對(duì)象有很大的相似性，而不同簇間的對(duì)象有很大的相異性。” ——百度百科
說(shuō)白了，聚類（clustering）是完全可以按字面意思來(lái)理解的——將相同、相似、相近、相關(guān)的對(duì)象實(shí)例聚成一類的過(guò)程。簡(jiǎn)單理解，如果一個(gè)數(shù)據(jù)集合包含N個(gè)實(shí)例，根據(jù)某種準(zhǔn)則可以將這N個(gè)實(shí)例劃分為m個(gè)類別，每個(gè)類別中的實(shí)例都是相關(guān)的，而不同類別之間是區(qū)別的也就是不相關(guān)的，這個(gè)過(guò)程就叫聚類了。
形式化一點(diǎn)，令
，其中的x都是向量，一個(gè)X的m聚類R將X分割為m個(gè)集合C1, C2,…,Cm，使其滿足下面三個(gè)條件：
（1）
（2）
（3）
滿足上述條件的同時(shí)，在聚類Ci中的向量彼此相似，而與其他類中的向量不相似。
但是這種定義也只是定義了確定性的聚類，也叫做硬聚類(hard clustering)，每個(gè)實(shí)例x都確定的屬于某個(gè)聚類。而不確定性聚類，也需要定義，這就引出了模糊聚類(fuzzy clustering)的概念了。模糊聚類中，每個(gè)實(shí)例向量x以一定的隸屬度屬于某個(gè)聚類。同上面的設(shè)置，X的模糊聚類是將X分成m個(gè)類，由m個(gè)函數(shù)uj表示，其中滿足：
（1）
（2）
（3）
其中這個(gè)隸屬度函數(shù)
越接近1，說(shuō)明xi越可能屬于Ci，反之如果越接近0，則說(shuō)明越不可能屬于Ci。
2. 聚類過(guò)程
當(dāng)我們知道聚類是什么時(shí)，我們下一步想知道的應(yīng)該是怎么進(jìn)行聚類。這一點(diǎn)，教材上做了詳細(xì)介紹，補(bǔ)充一點(diǎn)自己理解：
1）特征選擇(feature selection)：就像其他分類任務(wù)一樣，特征往往是一切活動(dòng)的基礎(chǔ)，如何選取特征來(lái)盡可能的表達(dá)需要分類的信息是一個(gè)重要問(wèn)題。表達(dá)性強(qiáng)的特征將很影響聚類效果。這點(diǎn)在以后的實(shí)驗(yàn)中我會(huì)展示。
2）近鄰測(cè)度(proximity measure)：當(dāng)選定了實(shí)例向量的特征表達(dá)后，如何判斷兩個(gè)實(shí)例向量相似呢？這個(gè)問(wèn)題是非常關(guān)鍵的一個(gè)問(wèn)題，在聚類過(guò)程中也有著決定性的意義，因?yàn)榫垲惐举|(zhì)在區(qū)分相似與不相似，而近鄰測(cè)度就是對(duì)這種相似性的一種定義。
3）聚類準(zhǔn)則(clustering criterion)：定義了相似性還不夠，結(jié)合近鄰測(cè)度，如何判斷相似才是關(guān)鍵。直觀理解聚類準(zhǔn)則這個(gè)概念就是何時(shí)聚類，何時(shí)不聚類的聚類條件。當(dāng)我們使用聚類算法進(jìn)行計(jì)算時(shí)，如何聚類是算法關(guān)心的，而聚與否需要一個(gè)標(biāo)準(zhǔn)，聚類準(zhǔn)則就是這個(gè)標(biāo)準(zhǔn)。（話說(shuō)標(biāo)準(zhǔn)這東西一拿出來(lái)，夠嚇人了吧^_^）
4）聚類算法(clustering algorithm)：這個(gè)東西不用細(xì)說(shuō)了吧，整個(gè)學(xué)習(xí)的重中之重，核心的東西這里不講，以后會(huì)細(xì)說(shuō)，簡(jiǎn)單開(kāi)個(gè)頭——利用近鄰測(cè)度和聚類準(zhǔn)則開(kāi)始聚類的過(guò)程。
5）結(jié)果驗(yàn)證(validation of the results)：其實(shí)對(duì)于PR的作者提出這個(gè)過(guò)程也放到聚類任務(wù)流程中，我覺(jué)得有點(diǎn)冗余，因?yàn)閷?duì)于驗(yàn)證算法的正確性這事應(yīng)該放到算法層面吧，可以把4）和5）結(jié)合至一層。因?yàn)樗惴ㄕ_和有窮的驗(yàn)證本身就是算法的特性嘛。（誰(shuí)設(shè)計(jì)了一個(gè)算法不得證明啊）
6）(interpretation of the results)：中文版的PR上翻譯為結(jié)果判定，而我感覺(jué)字面意思就是結(jié)果解釋。（聚類最終會(huì)將數(shù)據(jù)集分成若干個(gè)類，做事前要有原則，做事后要有解釋，這個(gè)就是解釋了。自圓其說(shuō)可能是比較好的了^_^）
整個(gè)聚類任務(wù)詳細(xì)的東西會(huì)在以后詳細(xì)介紹，這里先細(xì)說(shuō)一下聚類準(zhǔn)則（雖然我感覺(jué)在上面我說(shuō)的已經(jīng)夠細(xì)了）。舉例吧，比如，有這樣一個(gè)數(shù)據(jù)集X，包含了四名同學(xué)的基本信息和數(shù)學(xué)成績(jī)。
|
姓名
|
年級(jí)
|
班級(jí)
|
數(shù)學(xué)成績(jī)
|
|
張三
|
1
|
2
|
99
|
|
李四
|
2
|
2
|
95
|
|
張飛
|
3
|
1
|
59
|
|
趙云
|
2
|
1
|
90
|
聚類準(zhǔn)則就是一個(gè)分類標(biāo)準(zhǔn)，對(duì)于示例中這樣一個(gè)數(shù)據(jù)集合，如何聚類呢。當(dāng)然聚類的可能情況有很多。比如，如果我們按照年級(jí)是否為大于1來(lái)分類，那么數(shù)據(jù)集X分為兩類：{張三}，{李四，張飛，趙云}；如果按照班級(jí)不同來(lái)分，分為兩類：{張三，李四}，{張飛，趙云}；如果按照成績(jī)是否及格來(lái)分（假設(shè)及格為60分），分兩類：{張三，李四，趙云}，{張飛}。當(dāng)然聚類準(zhǔn)則的設(shè)計(jì)往往是復(fù)雜的，就看你想怎么劃分了。按照對(duì)分類思想的幾何理解，數(shù)據(jù)集相當(dāng)于樣本空間，數(shù)據(jù)實(shí)例的特征數(shù)（本例共有4個(gè)特征[姓名，年級(jí)，班級(jí)，數(shù)學(xué)成績(jī)]）相當(dāng)于空間維度，而實(shí)例向量對(duì)應(yīng)到空間中的一個(gè)點(diǎn)。那么聚類準(zhǔn)則就應(yīng)該是那些神奇的超平面（對(duì)應(yīng)有數(shù)學(xué)函數(shù)表達(dá)式，我個(gè)人認(rèn)為這些函數(shù)就等同于聚類準(zhǔn)則），這些超平面將數(shù)據(jù)“完美的”分離開(kāi)了。
3. 聚類特征類型
聚類時(shí)用到的特征如何區(qū)分呢，有什么類型要求？聚類的特征按照域劃分，可以分為連續(xù)的特征和離散特征。其中連續(xù)特征對(duì)應(yīng)的定義域是數(shù)據(jù)空間R的連續(xù)子空間，而離散特征對(duì)應(yīng)的是離散子集，另外如果離散特征只包含兩個(gè)特征值，那么這個(gè)離散特征又叫二值特征。
根據(jù)特征取值的相對(duì)意義又可以將特征分為以下四種：標(biāo)量的(Nominal)，順序的(Ordinal)，區(qū)間尺度的(Interval-scaled)以及比率尺度的(Ratio-scaled)。其中，標(biāo)量特征用于編碼一類特征的可能狀態(tài)，比如人的性別，編碼為男和女；天氣狀況編碼為陰、晴和雨等。順序特征同標(biāo)量特征類似，同樣是一系列狀態(tài)的編碼，只是對(duì)這些編碼稍加約束，即編碼順序是有意義的，比如對(duì)一道菜，它的特征有{很難吃，難吃，一般，好吃，美味}幾個(gè)值來(lái)定義狀態(tài)，但是這些狀態(tài)是有順序意義的。這類特征我認(rèn)為就是標(biāo)量特征的一個(gè)特定子集，或者是一個(gè)加約束的標(biāo)量特征。區(qū)間尺度特征表示該特征數(shù)值之間的區(qū)間有意義而數(shù)值的比率無(wú)意義，經(jīng)典例子就是溫度，A地的溫度（20℃）比B地（15℃）高5度，這里的區(qū)間差值是有意義的，但你不能說(shuō)A地比B地?zé)?/span>1/3，這是無(wú)意義的。比率特征與此相反，其比率是有意義的，經(jīng)典例子是重量，C重100g，D重50g，那么C比D重2倍，這是有意義的。（當(dāng)然說(shuō)C比D重50g也是可以的，因此可以認(rèn)為區(qū)間尺度是比率尺度的一個(gè)真子集）。
在常見(jiàn)應(yīng)用中，包括我們平日關(guān)心的編程實(shí)現(xiàn)中，一般只定義nominal特征和numeric特征，其中nominal可以用string來(lái)表示，而numeric可以用number來(lái)表示。（weka中的attribute的特征類型就是這么定義的）
4. 聚類分析的應(yīng)用
說(shuō)了這么多基本概念，最實(shí)際的話題莫過(guò)于應(yīng)用了。就像為聚類做廣告一樣，到底我們可以在哪里應(yīng)用它呢。就像引言里我提到的傳說(shuō)一樣，分類作為人類識(shí)別對(duì)象的一個(gè)基本活動(dòng)大概與人類的意識(shí)共同存在著，也可以說(shuō)人類智能認(rèn)識(shí)的本質(zhì)活動(dòng)之一就是分類。而研究者對(duì)分類的研究又將分類劃分為有監(jiān)督與無(wú)監(jiān)督，其中聚類就是無(wú)監(jiān)督分類的最常用方法也是絕對(duì)代表性方法。設(shè)想一下，對(duì)于一組數(shù)據(jù)，或者一堆信息，計(jì)算機(jī)可以自動(dòng)地將其分為若干類，那這對(duì)于輔助人類智能來(lái)說(shuō)絕對(duì)是必要的也是有意義的。所以聚類的一個(gè)核心應(yīng)用就是數(shù)據(jù)挖掘與模式識(shí)別。另外各個(gè)科學(xué)領(lǐng)域只要涉及到分類的任務(wù)，大家無(wú)不聯(lián)想到聚類~~~（話說(shuō)我第一次正式地解除聚類，還是在23教學(xué)樓聽(tīng)一個(gè)貌似是自動(dòng)化的教授講的信息化課程）。而學(xué)者比較權(quán)威的分類將聚類的應(yīng)用分為四個(gè)基本的方向：1）數(shù)據(jù)去冗，即將海量數(shù)據(jù)中的冗余信息去除。2）假說(shuō)生成，為了推導(dǎo)出數(shù)據(jù)的某些性質(zhì)，我們可以對(duì)數(shù)據(jù)進(jìn)行聚類分析。3）假說(shuō)檢驗(yàn)，其實(shí)就是通過(guò)聚類分析來(lái)驗(yàn)證某個(gè)決策的風(fēng)險(xiǎn)程度。4）基于分組的預(yù)測(cè)，同所有預(yù)測(cè)任務(wù)一樣，將已有的數(shù)據(jù)都聚類分類后，新的未來(lái)數(shù)據(jù)可以用同樣的規(guī)則進(jìn)行識(shí)別預(yù)測(cè)其所屬分類。
聚類的應(yīng)用非常廣泛，如果按科目枚舉，我是懶得羅列了。只要知道了其原理和目標(biāo)，其應(yīng)用領(lǐng)域也就自然理解了。
5. 小結(jié)
聚類的基本概念就是這么些了，關(guān)于聚類的學(xué)習(xí)和研究已經(jīng)歷經(jīng)幾十年，可以慶幸的一點(diǎn)是這里的學(xué)習(xí)我們可以站在很多巨人的肩膀上，而如何去改進(jìn)創(chuàng)新擴(kuò)展應(yīng)用，那就是我們未來(lái)的目的，“工欲善其事，必先利其器”，這里聚類就是我們的“器”了。
6. 參考文獻(xiàn)及推薦閱讀
[1]Pattern Recognition Third Edition, Sergios Theodoridis, Konstantinos Koutroumbas
[2] http://baike.baidu.com/view/903740.htm?fr=ala0_1_1
[3] http://zh.wikipedia.org/zh-cn/%E6%95%B0%E6%8D%AE%E8%81%9A%E7%B1%BB
[4]數(shù)據(jù)挖掘概念與技術(shù)(Data mining concepts and techniques) Jiawei Han, Micheline Kamber著范明, 孟小峰譯
[5]模式識(shí)別第三版, Sergios Theodoridis, Konstantinos Koutroumbas著, 李晶皎, 王愛(ài)俠, 張廣源等譯
[6]數(shù)據(jù)挖掘?qū)д?/span>(Introduction to data mining) Pang-Ning Tan, Michael Steinbach, Vipin Kumar著范明, 范宏建等譯
[7]數(shù)據(jù)挖掘?qū)嵱脵C(jī)器學(xué)習(xí)技術(shù) (Data mining practical machine learning tools and techniques) Ian H.Witten, Eibe Frank著董琳等譯
文章轉(zhuǎn)載請(qǐng)標(biāo)明~~~