無(wú)為

一， 什么是聚類(lèi)？

聚類(lèi)： - 將一個(gè)對(duì)象的集合分割成幾個(gè)類(lèi)，每個(gè)類(lèi)內(nèi)的對(duì)象之間是相似的，但與其他類(lèi)的對(duì)象是不相似的。

評(píng)判聚類(lèi)好壞的標(biāo)準(zhǔn)： 1 ，能夠適用于大數(shù)據(jù)量。 2 ，能應(yīng)付不同的數(shù)據(jù)類(lèi)型。 3 ，能夠發(fā)現(xiàn)不同類(lèi)型的聚類(lèi)。 4 ，使對(duì)專(zhuān)業(yè)知識(shí)的要求降到最低。 5 ，能應(yīng)付臟數(shù)據(jù)。 6 ，對(duì)于數(shù)據(jù)不同的順序不敏感。 7 ，能應(yīng)付很多類(lèi)型的數(shù)據(jù)。 8 ，模型可解釋?zhuān)墒褂谩?/span>

二， 聚類(lèi)所基于的數(shù)據(jù)類(lèi)型。

聚類(lèi)算法通常基于“數(shù)據(jù)矩陣”和“ Dissimilarity 矩陣”。

怎么樣計(jì)算不同對(duì)象之間的距離？

1 ，數(shù)值連續(xù)的變量（體重，身高等）：度量單位的選取對(duì)于聚類(lèi)的結(jié)果的很重要的。例如將身高的單位從米變?yōu)槌撸瑢Ⅲw重的單位從公斤變?yōu)榘鯇?duì)聚類(lèi)的結(jié)果產(chǎn)生很大的影響。為了避免出現(xiàn)這種情況，我們必須將數(shù)據(jù)標(biāo)準(zhǔn)化：將數(shù)據(jù)中的單位“去掉”。

A, 計(jì)算絕對(duì)背離度。 B, 計(jì)算標(biāo)準(zhǔn)量度。

下面我們考慮怎樣來(lái)計(jì)算兩個(gè)對(duì)象之間的差異。 1 ，歐幾里得距離。 2 ，曼哈頓距離。這兩種算法有共同之處： d(i,j)>=0,d(i,i)=0, d(i,j)=d(j,i),d(i,j)=<d(i,h)+d(h,j) 。 3 ， Minkowski 距離。這是上述兩種算法的通式。并且對(duì)于不同的變量，我們可以給它賦于不同的 weight.

2 ，二元數(shù)據(jù)變量：如果還是用上面的方法來(lái)計(jì)算的話，肯定會(huì)出現(xiàn)錯(cuò)誤。這兒分

兩種情況，對(duì)稱(chēng)的與非對(duì)稱(chēng)的。

3 ， Nominal 變量： ( 例如紅，黃，綠，藍(lán) ….)

4 ， ordinal 變量（例如科長(zhǎng)，處長(zhǎng)，局長(zhǎng) …. ）

5 ， ratio-scaled 變量：

6, 以上幾種混合的變量（多數(shù)情況是這樣的）：

三， 分割的的方法。

1， K 均值算法：給定類(lèi)的個(gè)數(shù) K ，將 n 個(gè)對(duì)象分到 K 個(gè)類(lèi)中去，使得類(lèi)內(nèi)對(duì)象之間的相似性最大，而類(lèi)之間的相似性最小。

缺點(diǎn)：產(chǎn)生類(lèi)的大小相差不會(huì)很大，對(duì)于臟數(shù)據(jù)很敏感。

??? ??? 改進(jìn)的算法： k—medoids 方法。這兒選取一個(gè)對(duì)象叫做 mediod 來(lái)代替上面的中心

?????? 的作用，這樣的一個(gè) medoid 就標(biāo)識(shí)了這個(gè)類(lèi)。步驟：

1， 任意選取 K 個(gè)對(duì)象作為 medoids （ O1,O2,…Oi…Ok ）。

以下是循環(huán)的：

2， 將余下的對(duì)象分到各個(gè)類(lèi)中去（根據(jù)與 medoid 最相近的原則）；

3， 對(duì)于每個(gè)類(lèi)（ Oi ）中，順序選取一個(gè) Or ，計(jì)算用 Or 代替 Oi 后的消耗— E （ Or ）。選擇 E 最小的那個(gè) Or 來(lái)代替 Oi 。這樣 K 個(gè) medoids 就改變了，下面就再轉(zhuǎn)到 2 。

4， 這樣循環(huán)直到 K 個(gè) medoids 固定下來(lái)。

這種算法對(duì)于臟數(shù)據(jù)和異常數(shù)據(jù)不敏感，但計(jì)算量顯然要比 K 均值要大，一般只適合小數(shù)據(jù)量。

2 ， C lara 算法。

上次課提到 K-medoids 算法不適合于大數(shù)據(jù)量的計(jì)算。這次課我們介紹 Clara 算法，這是一種基于采用的方法，它能夠處理大量的數(shù)據(jù)。

Clara 算法的思想就是用實(shí)際數(shù)據(jù)的抽樣來(lái)代替整個(gè)數(shù)據(jù)，然后再在這些抽樣的數(shù)據(jù)上利用 K-medoids 算法得到最佳的 medoids 。 Clara 算法從實(shí)際數(shù)據(jù)中抽取多個(gè)采樣，在每個(gè)采樣上都用 K-medoids 算法得到相應(yīng)的（ O1,O2…Oi…Ok ），然后在這當(dāng)中選取 E 最小的一個(gè)作為最終的結(jié)果。

Clara 算法的效率取決于采樣的大小，一般不太可能得到最佳的結(jié)果。

在 Clara 算法的基礎(chǔ)上，我們提出了 Clarans 的算法，與 Clara 算法不同的是：在 Clara 算法尋找最佳的 medoids 的過(guò)程中，采樣都是不變的。而 Clarans 算法在每一次循環(huán)的過(guò)程中所采用的采樣都是不一樣的。與上次課所講的尋找最佳 medoids 的過(guò)程不同的是，必須人為地來(lái)限定循環(huán)的次數(shù)。

四，層次聚類(lèi)

層次聚類(lèi)，就是把所有的記錄層次聚類(lèi)可以分為兩種：凝聚的方式和分割的方式，取決于聚類(lèi)層次結(jié)構(gòu)的形成是自頂向下的還是自底向上的。

??? 凝聚的方式：這是一種至底向上的方法，將每一條記錄看作一個(gè)類(lèi)，然后根據(jù)一些規(guī)則將他們聚合成越來(lái)越大的類(lèi)，直到滿(mǎn)足一些預(yù)先設(shè)定的條件。大多數(shù)的層次聚類(lèi)方法屬于這一類(lèi)。

??? 分割的方式：這種自頂向下的方法是一個(gè)與凝聚的方式相反的過(guò)程，將整個(gè)數(shù)據(jù)庫(kù)作為一個(gè)大的類(lèi)，然后按照一些規(guī)則將這個(gè)類(lèi)分成小的類(lèi)，直到滿(mǎn)足一些預(yù)定的條件，例如類(lèi)的數(shù)目到了預(yù)定值，最近的兩個(gè)類(lèi)之間的最小距離大于設(shè)定值。

例 3 ：圖 5 給出了對(duì)于集合 {a,b,c,d,e} 層次聚類(lèi)兩種方式的聚類(lèi)過(guò)程。從這個(gè)圖我們可以看出，凝聚的方式是將每一個(gè)記錄看作一個(gè)類(lèi)，再按照一定的規(guī)則逐步將這些類(lèi)合并。舉個(gè)例子，如果類(lèi) C1 和類(lèi) C2 之間的距離小于預(yù)定的最小距離，那么他們就會(huì)被合并為一個(gè)類(lèi)，這兒兩個(gè)類(lèi)的距離是由兩個(gè)類(lèi)中距離最近的一對(duì)記錄來(lái)確定的。

??? 分割的方式則是先將所有的記錄作為一個(gè)大的類(lèi)，然后再根據(jù)一些規(guī)則將它進(jìn)行分割，例如最近的兩個(gè)記錄之間的距離。

無(wú)論凝聚的方式還是分割方式，用戶(hù)都可以根據(jù)自己的要求來(lái)設(shè)定所得類(lèi)的個(gè)數(shù)。

下面給出了四種常用測(cè)定兩個(gè)類(lèi)之間距離的方法，這兒的 mi 是類(lèi) ci 的中間值， ni 是 ci 中記錄的個(gè)數(shù)， |p-p’| 是兩個(gè)記錄之間的距離。

??? Minimum distance ： Dmin(Ci,Cj)=Min|p-p’|;( 這兒 p 在類(lèi) Ci 中 p’ 在 Cj 中 )

??? Maximum distance ： Dmax(Ci,Cj)=Max|p-p’|;( 這兒 p 在類(lèi) Ci 中 p’ 在 Cj 中 )

??? Mean distance ： ??? Dmean(Ci,Cj)=|mi-mj|;

??? Average distance ： ? Davg(Ci,Cj)=(1/ni*nj) ∑p?ci∑p’?cj;

層次聚類(lèi)雖然比較簡(jiǎn)單，但是在選擇凝聚或者分割點(diǎn)的時(shí)候經(jīng)常會(huì)遇到一些困難，這個(gè)是非常關(guān)鍵的，因?yàn)橐坏┯涗洷荒刍蛘叻指钜院螅乱徊降墓ぷ魇墙⒃谛滦纬傻念?lèi)的基礎(chǔ)之上的。因此，如果其中任何一步?jīng)]有做好的話，就會(huì)影響最終聚類(lèi)的結(jié)果。這個(gè)方法并不是太好，因?yàn)橐獱可娴胶艽髷?shù)量的類(lèi)和記錄。

一個(gè)比較有前途的能夠提高聚類(lèi)質(zhì)量的方向是將層次聚類(lèi)和其它的聚類(lèi)結(jié)合起來(lái)進(jìn)行，下面我們會(huì)介紹一些這樣的方法： 1 ，叫做“ Birth ” , 它首先把 層次聚類(lèi)的形成過(guò)程到結(jié)果看作一棵樹(shù)，然后再用其他的聚類(lèi)方法來(lái)進(jìn)行修剪。 2 ，叫做“ Cure ”，他用一定數(shù)量的記錄來(lái)代表一個(gè)類(lèi)，然后將他們縮為類(lèi)的中心。 3 ，叫做“ Rock ” , 它是基于類(lèi)之間的聯(lián)系將類(lèi)合并。 4 ，叫做“ Chameleon ”，在層次聚類(lèi)中尋找自動(dòng)的模式。

1， Birch: 這是一種綜合的層次聚類(lèi)的方法，它介紹了兩個(gè)概念，聚類(lèi)特征和聚類(lèi)特征樹(shù)，它們是用來(lái)表示聚類(lèi)的。這些結(jié)構(gòu)能夠幫助聚類(lèi)方法能運(yùn)行得更快，能夠處理大數(shù)據(jù)量。

下面我們來(lái)看一下上面提到的結(jié)構(gòu)，一個(gè)聚類(lèi)特征是由關(guān)于記錄子集的三重總概變量組成。假設(shè)在一個(gè)子類(lèi)中有 N 個(gè)記錄，那么這個(gè)子類(lèi)的聚類(lèi)特征就是

CF=(N,LS,SS), 其中 LS 是 N 個(gè)點(diǎn)（記錄）的直線相加， SS 是 N 個(gè)點(diǎn)的平方和相加。

一個(gè)聚類(lèi)特征本質(zhì)上是對(duì)于給定的子類(lèi)的統(tǒng)計(jì)和，它記錄了衡量一個(gè)子類(lèi)的最關(guān)鍵的部分，用存儲(chǔ)統(tǒng)計(jì)值代替了存儲(chǔ)整個(gè)類(lèi)的記錄，提高了存儲(chǔ)的效率。

一個(gè)聚類(lèi)特征樹(shù)是一個(gè)垂直平衡樹(shù)，它為一個(gè)層次聚類(lèi)存了各個(gè)步驟的聚類(lèi)特征。圖 8.6 給出了一個(gè)例子，我們約定一個(gè)“非葉子節(jié)點(diǎn)”是有“孩子”的 , 這個(gè)“非葉子節(jié)點(diǎn)”記錄了它的孩子的聚類(lèi)特征。一個(gè)聚類(lèi)特征有兩個(gè)變量——“分枝要素 B ”和“門(mén)限 T ”， B 限定了每個(gè)“非葉子節(jié)點(diǎn)”最多含有的孩子的個(gè)數(shù)， T 限定了存在葉節(jié)點(diǎn)的子類(lèi)的最大半徑，這兩個(gè)參數(shù)影響了最后產(chǎn)生的樹(shù)的大小。

那么“ Birch ”是怎樣工作的呢？ 1 ，它掃描整個(gè)數(shù)據(jù)庫(kù)一次，建立一個(gè)初始化的聚類(lèi)特征樹(shù)。 2 ，它用一個(gè)聚類(lèi)算法來(lái)聚合這些葉節(jié)點(diǎn)。

在第一階段，聚類(lèi)特征樹(shù)隨著記錄一個(gè)一個(gè)的加入而自動(dòng)形成的：一個(gè)記錄被放入那個(gè)離它最近的葉節(jié)點(diǎn)（類(lèi)）中去。如果放入以后這個(gè)子類(lèi)的半徑大于門(mén)限值 T 的話，那么這個(gè)葉節(jié)點(diǎn)就會(huì)被分割。這個(gè)放入的信息也會(huì)傳遞到根節(jié)點(diǎn)中去。聚類(lèi)特征樹(shù)的大小可以通過(guò)調(diào)節(jié)參數(shù)來(lái)改變，如果要存儲(chǔ)的樹(shù)需要的內(nèi)存超過(guò)了主內(nèi)存，那就要減小門(mén)限值重新建立一棵樹(shù)，這個(gè)重建過(guò)程并不需要將整個(gè)記錄掃描一次。而是建立在老的樹(shù)的葉節(jié)點(diǎn)的基礎(chǔ)之上的。因此，建立一個(gè)樹(shù)記錄需要被掃描一次，此外還有一些方法進(jìn)一步掃描記錄以提高聚類(lèi)特征樹(shù)的質(zhì)量，當(dāng)樹(shù)建好以后，我們可以在第二階段用其他的聚類(lèi)算法了。

Birch 算法用可利用的資源產(chǎn)生最好的聚類(lèi)，給定一限定的主內(nèi)存，一個(gè)很重要的考慮是盡量減少?gòu)?/span> I/O 請(qǐng)求所需要的時(shí)間。 Birch 算法用了多種聚類(lèi)的技術(shù)，對(duì)數(shù)據(jù)庫(kù)的一次掃描產(chǎn)生一個(gè)基本好的聚類(lèi)，一次或者更多的附加掃描能夠提高聚類(lèi)的質(zhì)量。

Birch 的效果怎么樣？由于每一個(gè)節(jié)點(diǎn)只能有一定數(shù)量的“孩子”，實(shí)際產(chǎn)生的聚類(lèi)特征樹(shù)并不是自然生成的聚類(lèi)。而且，如果聚類(lèi)生成的類(lèi)不成球形的話，這種算法就運(yùn)用得很好，因?yàn)樗冒霃交蛘咧睆絹?lái)控制類(lèi)的邊界。

2， Cure:

大多數(shù)的算法或者只能用于球狀類(lèi)和有相似大小的類(lèi)上面，或者無(wú)法解決特例的問(wèn)題。 Cure 算法則能夠解決這些問(wèn)題。

Cure 采用一種很新穎的層次聚類(lèi)算法，這種方法是介于“基于中心”和“基于記錄”的方法之間的。一定數(shù)量的記錄被選中，而不是用中心或者一個(gè)記錄來(lái)代替整個(gè)類(lèi)。那些能代表這個(gè)類(lèi)的幾個(gè)記錄 , 首先在一個(gè)類(lèi)中選擇幾個(gè)較為分散的記錄作為代表整個(gè)類(lèi)的記錄，然后用一個(gè)特別的 Fraction 將他們壓縮到類(lèi)的中心。在每一步，那些有最大相似度的類(lèi)就會(huì)被合并。

由于用了多個(gè)記錄來(lái)代表類(lèi)，使得這種算法能夠很好地對(duì)付非球狀的的類(lèi)以及一些例外的情況結(jié)構(gòu)。那么，在大數(shù)據(jù)量的情況下能夠在不犧牲聚類(lèi)質(zhì)量的情況下，對(duì)付大數(shù)據(jù)量進(jìn)行得很好。

為了對(duì)付大數(shù)據(jù)量， Cure 用了隨機(jī)抽取和分割的方法 :

1， 選取有 s 個(gè)記錄的采樣。

2， 將這 s 個(gè)采樣分割成 p 個(gè)部分，每個(gè)有 s/p 個(gè)記錄。

3， 將 s 個(gè)記錄分成 s/pq 個(gè)類(lèi)。

4， 通過(guò)隨機(jī)采樣去除那些特例的情況。

5， 將這些類(lèi)進(jìn)行聚類(lèi)，

五，基于密度的方法 :

?? 1,DBSCAN:

??? 這個(gè)方法將密度足夠大的那部分記錄組成類(lèi)，這兒定義了幾個(gè)新的名詞：

1， 對(duì)于給定的記錄，我們稱(chēng)在其半徑 e 范圍內(nèi)的一個(gè)記錄為這個(gè)記錄的 e- 鄰居。

2， 如果一個(gè)記錄的 e- 鄰居個(gè)數(shù)超過(guò)一個(gè)最小值， MinPts 那么我們就將這個(gè)記錄稱(chēng)做中心記錄。

3， 一個(gè)記錄的集合 D, 我們說(shuō)一個(gè)記錄 p 是記錄 q 的“ Directly density-reachable ”記錄，如果 p 是 q 的 e- 鄰居， ` 并且 q 是個(gè)中心記錄。

4， 對(duì)于這樣的一個(gè)鏈 p1,p2,…pn ，如果， p1=q,pn=p, 且 Pi+1 是 pi 的“ Directly density-reachable ”，那么我們就將 p 稱(chēng)做 q 的“ density-reachable ”。

??????? 5, 如果 p,q 都是一個(gè)記錄 o 的“ density-reachable ”，那么就稱(chēng) p,q “ density-connected ”。

??????? 根據(jù)上面的定義，我們?cè)鯓觼?lái)發(fā)現(xiàn)類(lèi)呢？首先掃描一下數(shù)據(jù)庫(kù)，計(jì)算每一個(gè)點(diǎn)（記

??????? 錄）的 e- 鄰居的個(gè)數(shù)，如果一個(gè)記錄的 e- 鄰居的個(gè)數(shù)大于一個(gè)門(mén)限值，那么就將

?????? 這個(gè)記錄叫做中心記錄，這樣一個(gè)新的以這個(gè)記錄為中心的類(lèi)就產(chǎn)生了。接著，就

?????? 尋找這個(gè)記錄的所有的“ density-reachable ”記錄，這個(gè)過(guò)程可能會(huì)將一些類(lèi)也合

?????? 并過(guò)，這個(gè)過(guò)程直到?jīng)]有新的記錄假如為止。

????? 2,OPTICS:

?????? ? 雖然 DBSCAN 算法能夠根據(jù)給定的參數(shù) e 和 MinPts 來(lái)對(duì)記錄進(jìn)行聚類(lèi)，但是這 ??

??????? 仍然由用戶(hù)主觀來(lái)選擇參數(shù)，參數(shù)就影響了最終產(chǎn)生的類(lèi)，實(shí)際上這也是很多聚

??????? 集算法面臨的問(wèn)題。這些參數(shù)都是根據(jù)經(jīng)驗(yàn)來(lái)取的，因此很難決定該選哪個(gè)，特

??????? 別是對(duì)實(shí)際的，多屬性的數(shù)據(jù)。大多數(shù)的算法對(duì)這些參數(shù)都是很敏感的，很小的

??????? 一些差別就有可能導(dǎo)致大不相同的聚類(lèi)結(jié)果。聚類(lèi)結(jié)果。

??????? 為了解決這些問(wèn)題，一個(gè)順序聚類(lèi)的方法“ OPTICS ”就被提出來(lái)了。再來(lái)看看

? ???? ?????? DBSCAN, 我們很容易就可以發(fā)現(xiàn)，對(duì)于給定的一個(gè) Min Pts 值，那些參數(shù) e 的值

??????? 小的所得到的類(lèi)一定完全包含在 e 值大的類(lèi)當(dāng)中了。注意一點(diǎn)這兒的 e 是一個(gè)距

? ??????????? 離（它是鄰居半徑）。因此，為了得到類(lèi)的集合，我們?cè)O(shè)定了提供了距離參數(shù)的集

??? ?????? ?????? 合。為了同時(shí)建立不同的類(lèi)，這些記錄應(yīng)該以一種順序形式組織起來(lái)。這樣我們

就可以將 e 從小開(kāi)始產(chǎn)生類(lèi)了。基于這些理念，對(duì)于每一個(gè)記錄都應(yīng)該存儲(chǔ) 2 個(gè)

值—— core-distance 和 reachability-distance:

core-distance ：一個(gè)記錄的 core-distance 是能使這個(gè)記錄 p 成為中心記錄的最小的

e’ 值。如果 p 不是個(gè)中心記錄，那么這個(gè)值就是未被定義。

reachability-distance （ p,q ）：如果中心記錄 p 和一個(gè)記錄之間的距離小于 e’, 那么這

個(gè)距離就是 e’, 其他的就是真實(shí)的距離。如果 p 不是中心記錄，它就沒(méi)有被定義。

對(duì)于在數(shù)據(jù)庫(kù)中的每一個(gè)記錄，首先將它們編號(hào)，然后計(jì)算每個(gè)記錄的這兩個(gè)距

離值。這就使得我們有足夠的信息來(lái)在 e 小于等于 e’ 的范圍內(nèi)得到很多的聚類(lèi)結(jié)

果了。

3， DENCLUE.

這個(gè)聚類(lèi)方法主要基于下面的一些思想：

a, 一個(gè)記錄的影響力可以用一個(gè)數(shù)學(xué)函數(shù)來(lái)表示，叫做“影響函數(shù)”，這表明了一個(gè)記錄對(duì)于其鄰居記錄的影響。

b, 整個(gè)數(shù)據(jù)空間的密度可以用所有的記錄的“影響函數(shù)”的總和來(lái)模化。

c, 類(lèi)可以通過(guò)確定“ density attrator ”來(lái)得到，這兒的“ density attrator ”是指在某個(gè)區(qū)域的最高峰。

基 于 模 型 的 聚 集 方 法

1，統(tǒng)計(jì)的方法：

???? 概念聚類(lèi)是在機(jī)器學(xué)習(xí)中聚類(lèi)的一種形式，與其他通常的聚類(lèi)方法（定義相似的記錄為一個(gè)類(lèi)）不同的是，概念聚類(lèi)則更進(jìn)一步來(lái)找出每一個(gè)類(lèi)的特征描述。這樣，概念聚類(lèi)就有兩步組成，首先，進(jìn)行聚類(lèi)，然后找出特征。這樣聚類(lèi)的質(zhì)量就不僅僅是單個(gè)記錄的一個(gè)函數(shù)，它還綜合了一些得出的類(lèi)的描述。

???? 大多數(shù)的概念聚類(lèi)采用了一個(gè)統(tǒng)計(jì)的方法——在決定一個(gè)類(lèi)的時(shí)候，用可能性的描述語(yǔ)句。 COBWEB 是一個(gè)通用且簡(jiǎn)單的概念聚類(lèi)的方法，它用分類(lèi)樹(shù)的形式來(lái)表現(xiàn)層次聚類(lèi)。

?? ?? 一個(gè)分類(lèi)樹(shù)與決策樹(shù)是不同的，分類(lèi)樹(shù)的每一個(gè)節(jié)點(diǎn)表示了一個(gè)概念，和對(duì)于這個(gè)概念（這個(gè)概念總概了這個(gè)節(jié)點(diǎn)下的記錄）的可能性的描述。這個(gè)可能性的描述包括形成這個(gè)類(lèi)的可能，以及在某個(gè)條件下類(lèi)中記錄的可能性，它可以表示為 P(Ai=Vij|Ck) ，這兒的 Ai=Vij 是個(gè)“屬性—值”對(duì)， Ck 就是類(lèi)。這與決策樹(shù)不同，它是用邏輯而非可能性描述。為了將一個(gè)記錄進(jìn)行分類(lèi)，就需要一個(gè)匹配函數(shù)來(lái)將阿嚏分到做適合的類(lèi)中去。

???? COBWEB 用了一種啟發(fā)式的評(píng)估衡量標(biāo)準(zhǔn)（ category utility ）來(lái)引導(dǎo)樹(shù)的建立。

? ???CU 的定義：

???? 這兒的 n 是節(jié)點(diǎn)的個(gè)數(shù)，也就是類(lèi)的個(gè)數(shù)。從另外一種意義上來(lái)說(shuō)， CU 的 P(Ai=Vij|) 表示了在條件 Ck 和沒(méi)有條件 Ck 之下的偏差。

???? 下面我們來(lái)看看 COBWEB 的工作過(guò)程：它以增入的方式將記錄加入到分類(lèi)樹(shù)中去，就象 Leader 算法一樣，它對(duì)于一個(gè)新的記錄計(jì)算它與以分好的類(lèi)的匹配度，選擇最好的節(jié)點(diǎn)將這個(gè)新的記錄放進(jìn)去。這個(gè)方法先將新記錄暫時(shí)放到每一個(gè)已經(jīng)形成的類(lèi)中，然后計(jì)算放入后的每次放入后的 CU 值，值最大的就是我們要找的最匹配的類(lèi)。

???? 那么，假如這個(gè)新記錄不屬于任何一個(gè)以形成的類(lèi)時(shí)怎么辦？實(shí)際上， COBWEB 也計(jì)算將這個(gè)新的記錄作為一個(gè)新的節(jié)點(diǎn)時(shí) CU 的值，如果這個(gè)值比上述過(guò)程所得到的都要大的話，就建立一個(gè)新類(lèi)。值得注意的是， COBWEB 能夠自己調(diào)整類(lèi)的數(shù)目的大小，而不向其他算法那樣自己設(shè)定類(lèi)的個(gè)數(shù)。

???? 但上述的操作對(duì)于的記錄的順序很敏感， COBWEB 利用兩個(gè)操作來(lái)將這種敏感性降到最低，這就是 merging 和 splitting 的方法，當(dāng)對(duì)一個(gè)新的記錄進(jìn)行分類(lèi)的時(shí)候，兩個(gè)最好的類(lèi)就可能被合并，當(dāng)然這些決定必須根據(jù) CU 值來(lái)。

???? COBWEB 的缺點(diǎn)：這個(gè)方法假定根據(jù)統(tǒng)計(jì)得到的對(duì)于單個(gè)屬性的概率分布函數(shù)與其他的屬性之間是獨(dú)立的，實(shí)際上在兩個(gè)屬性之間通常會(huì)存在一些聯(lián)系。

2，神經(jīng)網(wǎng)絡(luò)的方法

?? 神經(jīng)網(wǎng)絡(luò)用于聚類(lèi)的方法是將每一個(gè)類(lèi)看作一個(gè)標(biāo)本，它是這個(gè)類(lèi)的“典型”，但不需和某個(gè)具體的記錄或例子相對(duì)應(yīng)。根據(jù)新記錄和這個(gè)標(biāo)本之間的距離，就可以將這個(gè)記錄進(jìn)行分類(lèi)了。

?? 在這篇中，我們介紹 2 個(gè)神經(jīng)網(wǎng)絡(luò)用做聚類(lèi)的方法，分別是“ competitive learning ”和“ self-organizing feature maps ”。

異常情況分析

很多時(shí)候，會(huì)有一些記錄與通常的行為不一樣，對(duì)于那些跟數(shù)據(jù)庫(kù)中其他的記錄不相符合的記錄，我們稱(chēng)之為 outliers 。

??? Outliers 可能在聚類(lèi)運(yùn)行或者檢測(cè)的時(shí)候被發(fā)現(xiàn)，比如一個(gè)人的年齡是 999 ，這個(gè)在對(duì)數(shù)據(jù)庫(kù)進(jìn)行檢測(cè)的時(shí)候就會(huì)被發(fā)現(xiàn)。還有，就是 outliers 可能是本身就固有的，而不是一個(gè)錯(cuò)誤，比如部門(mén)經(jīng)理的工資就比一般員工的工資高出很多。

??? 很多數(shù)據(jù)挖掘技術(shù)都力圖將 outliers 的影響降到最小，直至完全沒(méi)有。但是，這有可能失去一些重要的隱藏的信息，因?yàn)閷?duì)于一方來(lái)講是“壞”的東西而對(duì)于另外的一方來(lái)講很可能是重要的東西。換句話說(shuō)，這個(gè)“異常”可能有特別的作用，例如發(fā)現(xiàn)詐騙行為。因此，發(fā)現(xiàn)和分析“詐騙行為”是一相很有意義的數(shù)據(jù)挖掘任務(wù)，我稱(chēng)為“ outlier mining ”。

outlier mining 的應(yīng)用是很廣泛的，除了上面說(shuō)的“欺騙發(fā)現(xiàn)”以外，它還能夠發(fā)現(xiàn)收入特別低或者特別高的顧客的購(gòu)買(mǎi)行為。 outlier mining 可以這么來(lái)描述：給定 n 個(gè)個(gè)記錄，和 k （我們期望得到的 outlier 的個(gè)數(shù)）；發(fā)現(xiàn) k 個(gè)與其他的記錄最不相象的記錄。這個(gè)過(guò)程可以看成 2 個(gè)子過(guò)程： 1 ，首先定義什么樣的記錄被稱(chēng)為“異常”； 2 ，根據(jù)上面的定義，找到一個(gè)很有效的方法來(lái)發(fā)現(xiàn)這些異常。

在這篇文章里，我們介紹了三種方法來(lái)發(fā)現(xiàn) outlier ：

1， 基于統(tǒng)計(jì)的方法 ：

統(tǒng)計(jì)的方法先假定在訓(xùn)練集中有一個(gè)分布模式存在，并且用一個(gè)“ discordancy test ”的方法來(lái)定義和發(fā)現(xiàn) outliers 。這個(gè)方法的應(yīng)用首先要設(shè)定一些參數(shù)——假定的分布模式，分布的參數(shù)，期望得到的 outlier 的的個(gè)數(shù)等等。

工作過(guò)程：首先檢測(cè) 2 個(gè)假說(shuō)，一個(gè) working hypothesis 和 alternative hypothesis 。 working hypothesis ， H, 是說(shuō)所有的記錄的數(shù)據(jù)都應(yīng)該遵從一個(gè)分布模式， F ，然后用一個(gè)“ discordancy test ”來(lái)檢測(cè)記錄 Oi 是否與 F 的關(guān)系很大。這兒的“ discordancy test ”是根據(jù)對(duì)于數(shù)據(jù)的了解以及 F 的選擇得出的。這兒，通過(guò) T 計(jì)算出 Oi 對(duì)應(yīng)的值 vi, 如果 SP(vi)=prob(T>vi) 的值很小的話，我們就可以考慮 Oi 是個(gè) outlier 。

2， 基于距離的方法 ：

如果一個(gè)記錄的距離大于 d 的鄰居的個(gè)數(shù)大于一個(gè)設(shè)定值 p 的話，就可以認(rèn)為這個(gè)記錄是個(gè) outlier 。換句話說(shuō)，就是這個(gè)記錄沒(méi)有足夠的鄰居數(shù)目，這兒的鄰居是根據(jù)距離來(lái)確定的。

Index-based algorithm: 給定一個(gè)數(shù)據(jù)集，這個(gè)算法檢查每一個(gè)記錄 o 的 d 半徑的鄰居個(gè)數(shù)，定義 M 為一個(gè) outlier 的最大 d- 鄰居個(gè)數(shù)，那么一旦一個(gè)記錄 o 有 M+1 個(gè) d- 鄰居，顯然這個(gè)記錄不是個(gè) outlier 。

Nest-loop algorithm: 與上一個(gè)方法相比，它優(yōu)點(diǎn)在于減少輸入、出個(gè)數(shù)，提高儲(chǔ)存效率。

Cell-based algorithm: 這種方法是將數(shù)據(jù)集分成 c 個(gè) cells, 每一個(gè) cell 有兩層，第一層有 1 個(gè) cell 的厚度，第二層有 2*sqrt(k) 個(gè) cell 的厚度。這個(gè)算法是一個(gè) cell 一個(gè) cell 地來(lái)找 outlier 。對(duì)于一個(gè) cell, 我們計(jì)算三個(gè)量：在這個(gè) cell 內(nèi)的記錄個(gè)數(shù)，在第一層的記錄個(gè)數(shù)，在第二層的記錄的個(gè)數(shù)，分別用 cell_count ， cell_+_1_layer-count, cell_+_2_layer-count 。

那么這個(gè)方法是怎樣來(lái)計(jì)算 outlier 的呢？首先計(jì)算 cell_+_1_layer-count ，如果它的值大于 M, 那么這個(gè) cell 內(nèi)的所有的記錄都不是 outlier ，如果它的值小于后者等于 M, 那么接著計(jì)算 cell_+_2_layer-count ，如果它的值小于后者等于 M, 那么 cell 中所有的記錄都可以認(rèn)為是 outlier 。否則我們按照 d- 鄰居的方法來(lái)一個(gè)一個(gè)地檢查這層中的記錄。

3，?? 基于背離度的方法：

這種方法是根據(jù)一個(gè)數(shù)據(jù)集中的主要特征來(lái)判定 outlier 的，那些與這個(gè)主要特征背離很大的記錄就被認(rèn)為是一個(gè) outlier 。

Sequential exception technique: 給定一個(gè)有 n 個(gè)記錄的數(shù)據(jù)集 S ，首先建立它的一個(gè)記錄子集序列， {S1,S2,S3,…Sm} ，這兒的 Sj 包含 Sj-1 。

在這個(gè)序列中我們可以計(jì)算子集間的不相象性，下面介紹幾個(gè)關(guān)鍵的概念。

Eeception set: 它定義為 outlier 的集合。

Dissimilarity functuion: 這個(gè)函數(shù)計(jì)算在一個(gè)集合中記錄的不相象性，如果各個(gè)記錄之間越象，那么這個(gè)值就越小，而記錄之間背離讀越大，則這個(gè)值就越大。

Cardinality function: 它計(jì)算在給定的一個(gè)集合中記錄的個(gè)數(shù)。

Smoothing factor: 這個(gè)函數(shù)計(jì)算了從原集合 S 中去除一個(gè)子集后 Dissimilarity 的減少值，那個(gè)減少的值最多的子集就是 outlier 。

聚類(lèi)的方法小節(jié)：

?? 這篇文章很全面的介紹了聚類(lèi)：包括聚類(lèi)的定義，聚類(lèi)的應(yīng)用，聚類(lèi)的幾種常用的算法 , ， 最后還介紹了異常的檢測(cè)。

??? 聚類(lèi)的算法包括分割的聚類(lèi)方法，層次聚類(lèi)，基于密度的方法，和基于模型的方法。

最近鄰居和聚集（Nearest Neighbor and Clustering）

?

距離近：在一些重要的屬性上比較相似

聚集（clustering）：是把相似的記錄放在一起。

用途

聚集

讓用戶(hù)在較高的層次上觀察數(shù)據(jù)庫(kù)。常被用來(lái)做商業(yè)上的顧客分片（segmentation）。

找到不能與其他記錄集合在一起的記錄，做例外分析。

最近鄰居

預(yù)測(cè)，距離相近的對(duì)象通常他們的預(yù)測(cè)值也相似，因此只要知道一個(gè)對(duì)象的預(yù)測(cè)值，就可以用他來(lái)預(yù)測(cè)他的鄰居的值。

分?jǐn)?shù)卡

凡是有該標(biāo)志的文章，都是該blog博主Caoer（草兒）原創(chuàng)，凡是索引、收藏
、轉(zhuǎn)載請(qǐng)注明來(lái)處和原文作者。非常感謝。