聚類(lèi)

聚類(lèi)clustering，無(wú)監(jiān)督學(xué)習(xí)unsupervised learning分類(lèi)也。 聚類(lèi)有不少經(jīng)典的方法，我們先從基本概念，本質(zhì)屬性開(kāi)始討論，慢慢把這些方法掌握，應(yīng)用到實(shí)際問(wèn)題中。

1、基本概念。

? 既然要把給出的特征向量分成不同的類(lèi)里，我們首先應(yīng)該想到的是，什么是類(lèi)(cluster或者group)？ 在研究過(guò)程中大家不斷的給出一些定義， 但是都比較模糊和寬泛，很難找到一個(gè)大家都容易接受的定義，最近的一個(gè)，差不多大家都比較認(rèn)同的定義是這樣描述的。

"continuous regions of this space containing a relatively high density of points, separated from other high density regions by regions of relatively low density of points"

this space 是指特征向量空間，每個(gè)特征向量被看成空間中的一個(gè)點(diǎn)。

什么是聚類(lèi)呢？?

我們需要聚類(lèi)的數(shù)據(jù)集是：X = {x_1, ..., x_N}， 表示有N個(gè)特征向量需要聚類(lèi)。

定義X的m聚類(lèi)，就是將X分成m組向量，每一組類(lèi)用C表示，C_1, ..., C_m

其中 C_i != 空集； C的并是X； 任意兩個(gè)類(lèi)的交集是空集。在同一個(gè)類(lèi)中的特征向量是相似的（similar），不同類(lèi)中的特征向量不相似（dissimilar），量化這兩個(gè)詞有點(diǎn)困難，可能需要根據(jù)你的實(shí)際情況來(lái)定義相似性和不相似性。?

大約有三種不同的類(lèi)別，如下圖

圖1， Compact Cluster

圖 2， Elongated clusters

圖3、 Spherical and ellipsoidal clusters

這三種不同的cluster類(lèi)型，對(duì)相似度的量化有所差異。

前面描述的這種聚類(lèi)方式一般稱(chēng)之為硬聚類(lèi)（hard 或者 crisp）

還有一種方式是軟聚類(lèi)，就是說(shuō)每個(gè)特征屬于某個(gè)類(lèi)有一個(gè)隸屬度來(lái)表述它，比如x屬于C_1的隸屬度為0.2， 屬于C_2的隸屬度為0.8 ，對(duì)于兩類(lèi)的情況，這樣是合理的。

2、 關(guān)于proximity measure

之前寫(xiě)這篇博文的時(shí)候，不想寫(xiě)這部分，現(xiàn)在覺(jué)得還是寫(xiě)寫(xiě)的好啊，保證知識(shí)的完整性，多多思考還是好的。

我們可以用 相似度(similarity)或不相似度(dissimilarity) 來(lái)量化兩個(gè)特征向量、特征向量與一組特征向量以及兩組特征向量之間的proximity。

多數(shù)人認(rèn)為兩個(gè)向量的proximity測(cè)度是最基礎(chǔ)的，proximity就翻譯成近鄰吧。

什么是相似度？定義兩個(gè)向量之間的相似度，它是一個(gè)函數(shù)，滿(mǎn)足如下規(guī)則：

? ?* 相似度函數(shù)與特征向量的輸入順序無(wú)關(guān)。 s(v1, v2) = s(v2, v1)

? ?* 任意的同一個(gè)特征向量的相似度取得最大值。 s(v,v) 取得相似度函數(shù)的值域中的最大值。并且當(dāng)且僅當(dāng)輸入向量相同的時(shí)候，才能取得這個(gè)最大值。

? ?* 還有一個(gè)不等式需要滿(mǎn)足： s(x,y) s(y,z) <= [s(x,y)+s(y,z)]s(x,z), for all x,y,z in X

什么是不相似度？ 也用函數(shù)定義，也滿(mǎn)足一下規(guī)則：

? ?* 當(dāng)且僅當(dāng)兩個(gè)輸入向量相同時(shí)，不相似度函數(shù)取到最小值，就是說(shuō)只有這個(gè)時(shí)候，兩個(gè)向量才最不不相似，就是最相似。

? ?* 不相似度函數(shù)的值與輸入順序無(wú)關(guān)。

? ?* 滿(mǎn)足三角不等式。 d(x,z) <= d(x,y) + d(y,z) , 對(duì)任意 x，y，z in X都成立。

常用的，或者現(xiàn)在大家用過(guò)的相似度與不相似度函數(shù)，大家可以參考 《Pattern Recognition》第四版 影印版 604頁(yè)。

在書(shū)中根據(jù)特征向量的類(lèi)型，分了幾種情況。 向量的分量為可連續(xù)實(shí)數(shù)時(shí)、向量的分量為整數(shù)時(shí)、混合類(lèi)型情況，還有模糊測(cè)度，數(shù)據(jù)缺失情況下的測(cè)度。

關(guān)于特征向量與一組特征向量之間的測(cè)度，可以由兩個(gè)方向我們選擇。一種是，集合中的每個(gè)向量都參與與給定的另一個(gè)向量之間測(cè)度，去個(gè)最大的或者最小的，等等。

一種是找一個(gè)類(lèi)的代表，用給定的向量與這個(gè)代表之間做測(cè)量，來(lái)表示類(lèi)與給定向量之間的近鄰測(cè)度。

相似的，兩組特征向量之間也可以采用這兩個(gè)方向。?

這就給了我們一些選擇的余地，根據(jù)我們的需要作出相應(yīng)的認(rèn)為選擇。

對(duì)某個(gè)類(lèi)選一個(gè)代表出來(lái)也是可以研究下的，不過(guò)現(xiàn)在能想到的，大家都差不多想到了，我們只有在實(shí)際用的時(shí)候給出一個(gè)合適的測(cè)度，來(lái)對(duì)我們后面?zhèn)€聚類(lèi)工作更適合就好了。

向compact類(lèi)型的類(lèi)，我們可以考慮均值矢量，均值中心，中值中心等。 像線(xiàn)性或者其它形狀的類(lèi)，我們也許可以找一些跟形狀類(lèi)似的代表。