人在江湖

聚類分析被稱之為unsupervised分析，一個(gè)跟它相似的概念是分類(classification)模型，不同的是，分類模型預(yù)先知道一共有幾個(gè)類別，每個(gè)類別的定義是什么，所以叫做supervised。聚類分析預(yù)先不知道目標(biāo)分成哪幾類。往往在實(shí)際中，先用cluster分成一些類，然后有了這些類之后，可以再可以做classification分析，就是所謂的two steps analytisis.

聚類分析的算法主要基于“距離”的計(jì)算。聚類之后的結(jié)果要盡量保證每個(gè)segment內(nèi)部的對(duì)象之間距離要短， segment之間的距離要長。這篇博客的內(nèi)容總結(jié)自Han Jiawei的書，這本書可以在這篇博客里找到： 分享讀書筆記Data Mining Concepts and Techniques 

關(guān)于距離：

如果有n個(gè)對(duì)象，每個(gè)對(duì)象有p個(gè)屬性，那么可以得到這樣一個(gè)矩陣：

距離通常是用另一個(gè)變形后的矩陣來做的：

其中d(2,1)表示第二個(gè)對(duì)象和第一個(gè)對(duì)象之間的距離。

對(duì)于連續(xù)型變量(interval)的，通常要對(duì)數(shù)據(jù)預(yù)先做標(biāo)準(zhǔn)化“standardiz”，方式如下：

1. 算mean absolute deviation.

2. 得出標(biāo)準(zhǔn)度量(不知道怎么翻譯，standardized measurement)

3.最后結(jié)果：

對(duì)于二值型(binary)的, 有兩種，一種是均衡型的（symmetric），另一種是非均衡型的(asymmetric),均衡指的是yes or no兩種狀態(tài)權(quán)重一樣。比如如果你沒有性別歧視的話，性別是均衡的二值變量。如果通過一系列癥狀診斷一個(gè)人是否生病了，yes比no的權(quán)重要大的多。

兩種形式都通過下面這個(gè)2x2的表來算距離：

對(duì)于均衡型的，

對(duì)于非均衡型的

對(duì)于類別型（categorical）的變量，比較簡單

where m is the number of matches (i.e., the number of variables for which i and  j are
in the same state), and p is the total number of variables.

對(duì)于順序型（ordinal）的變量，要先把順序map成[0.0，1.0]之間的數(shù)，然后按interval的方式來算。直接上截圖，因?yàn)樘鄶?shù)學(xué)符號(hào)了

書上對(duì)每種計(jì)算基本都有例子。

關(guān)于聚類方法：

有partitioning, hierarchical, density-based, grid-based, model-based, clustering High-Dimensional, Constraint-Based.

Partitioning方法：

代表方法是K-means:

它的大致算法是，選定K值（最后要分成多少組）后，任選K個(gè)object作為cluster的中心，然后對(duì)每個(gè)其他的對(duì)象計(jì)算離哪個(gè)中心最近，就歸到哪個(gè)cluster里，最后從每個(gè)cluster中找到新的中心，然后這樣重復(fù)計(jì)算，直到聚類沒有變化為止。

Hierarchical方法：

分agglomerative和Divisive兩種，前者是自底向上的，就是一個(gè)一個(gè)object merge出一個(gè)segment,后者相反，自頂向下的。 上面說的K-means方法有時(shí)候和hierarchical聯(lián)在一起用，因?yàn)镵-means需要k作為參數(shù)，這個(gè)參數(shù)還挺重要的，極大影響了聚類的結(jié)果，可以先用hierarchical看看大致分幾類合理，然后再用K-means。

Density-based方法：

基于距離的算法segment都是類球形的，density-based克服了這個(gè)問題。他的理念基本上是，一個(gè)對(duì)象為中心畫個(gè)圓，看看圈近來的對(duì)象過沒過threshold.

Grid-Based:

它是從上往下分層，底層grid粒度更細(xì)。它的特點(diǎn)是是scalability比較好。沒細(xì)看理論，但是看圖能感覺個(gè)大概。

Constraint-Based:

有的時(shí)候用戶清楚應(yīng)用的需求，想要指引聚類的過程，比如每個(gè)cluster size的range, 不同對(duì)象不用的權(quán)重等等。這就用到constraint-based聚類分析。這個(gè)也沒細(xì)看，還有另外的clustering high-dimensional data, model based clustering都沒怎么看，也許以后再寫一篇“再訪聚類分析”。下一篇會(huì)關(guān)于決策樹。