無為

一， 什么是聚類？

聚類： - 將一個對象的集合分割成幾個類，每個類內的對象之間是相似的，但與其他類的對象是不相似的。

評判聚類好壞的標準： 1 ，能夠適用于大數據量。 2 ，能應付不同的數據類型。 3 ，能夠發現不同類型的聚類。 4 ，使對專業知識的要求降到最低。 5 ，能應付臟數據。 6 ，對于數據不同的順序不敏感。 7 ，能應付很多類型的數據。 8 ，模型可解釋，可使用。

二， 聚類所基于的數據類型。

聚類算法通常基于“數據矩陣”和“ Dissimilarity 矩陣”。

怎么樣計算不同對象之間的距離？

1 ，數值連續的變量（體重，身高等）：度量單位的選取對于聚類的結果的很重要的。例如將身高的單位從米變為尺，將體重的單位從公斤變為磅將對聚類的結果產生很大的影響。為了避免出現這種情況，我們必須將數據標準化：將數據中的單位“去掉”。

A, 計算絕對背離度。 B, 計算標準量度。

下面我們考慮怎樣來計算兩個對象之間的差異。 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 距離。這是上述兩種算法的通式。并且對于不同的變量，我們可以給它賦于不同的 weight.

2 ，二元數據變量：如果還是用上面的方法來計算的話，肯定會出現錯誤。這兒分

兩種情況，對稱的與非對稱的。

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

4 ， ordinal 變量（例如科長，處長，局長 …. ）

5 ， ratio-scaled 變量：

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

三， 分割的的方法。

1， K 均值算法：給定類的個數 K ，將 n 個對象分到 K 個類中去，使得類內對象之間的相似性最大，而類之間的相似性最小。

缺點：產生類的大小相差不會很大，對于臟數據很敏感。

??? ??? 改進的算法： k—medoids 方法。這兒選取一個對象叫做 mediod 來代替上面的中心

?????? 的作用，這樣的一個 medoid 就標識了這個類。步驟：

1， 任意選取 K 個對象作為 medoids （ O1,O2,…Oi…Ok ）。

以下是循環的：

2， 將余下的對象分到各個類中去（根據與 medoid 最相近的原則）；

3， 對于每個類（ Oi ）中，順序選取一個 Or ，計算用 Or 代替 Oi 后的消耗— E （ Or ）。選擇 E 最小的那個 Or 來代替 Oi 。這樣 K 個 medoids 就改變了，下面就再轉到 2 。

4， 這樣循環直到 K 個 medoids 固定下來。

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

2 ， C lara 算法。

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

Clara 算法的思想就是用實際數據的抽樣來代替整個數據，然后再在這些抽樣的數據上利用 K-medoids 算法得到最佳的 medoids 。 Clara 算法從實際數據中抽取多個采樣，在每個采樣上都用 K-medoids 算法得到相應的（ O1,O2…Oi…Ok ），然后在這當中選取 E 最小的一個作為最終的結果。

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

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

四，層次聚類

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

??? 凝聚的方式：這是一種至底向上的方法，將每一條記錄看作一個類，然后根據一些規則將他們聚合成越來越大的類，直到滿足一些預先設定的條件。大多數的層次聚類方法屬于這一類。

??? 分割的方式：這種自頂向下的方法是一個與凝聚的方式相反的過程，將整個數據庫作為一個大的類，然后按照一些規則將這個類分成小的類，直到滿足一些預定的條件，例如類的數目到了預定值，最近的兩個類之間的最小距離大于設定值。

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

??? 分割的方式則是先將所有的記錄作為一個大的類，然后再根據一些規則將它進行分割，例如最近的兩個記錄之間的距離。

無論凝聚的方式還是分割方式，用戶都可以根據自己的要求來設定所得類的個數。

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

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

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

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

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

層次聚類雖然比較簡單，但是在選擇凝聚或者分割點的時候經常會遇到一些困難，這個是非常關鍵的，因為一旦記錄被凝聚或者分割以后，下一步的工作是建立在新形成的類的基礎之上的。因此，如果其中任何一步沒有做好的話，就會影響最終聚類的結果。這個方法并不是太好，因為要牽涉到很大數量的類和記錄。

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

1， Birch: 這是一種綜合的層次聚類的方法，它介紹了兩個概念，聚類特征和聚類特征樹，它們是用來表示聚類的。這些結構能夠幫助聚類方法能運行得更快，能夠處理大數據量。

下面我們來看一下上面提到的結構，一個聚類特征是由關于記錄子集的三重總概變量組成。假設在一個子類中有 N 個記錄，那么這個子類的聚類特征就是

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

一個聚類特征本質上是對于給定的子類的統計和，它記錄了衡量一個子類的最關鍵的部分，用存儲統計值代替了存儲整個類的記錄，提高了存儲的效率。

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

那么“ Birch ”是怎樣工作的呢？ 1 ，它掃描整個數據庫一次，建立一個初始化的聚類特征樹。 2 ，它用一個聚類算法來聚合這些葉節點。

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

Birch 算法用可利用的資源產生最好的聚類，給定一限定的主內存，一個很重要的考慮是盡量減少從 I/O 請求所需要的時間。 Birch 算法用了多種聚類的技術，對數據庫的一次掃描產生一個基本好的聚類，一次或者更多的附加掃描能夠提高聚類的質量。

Birch 的效果怎么樣？由于每一個節點只能有一定數量的“孩子”，實際產生的聚類特征樹并不是自然生成的聚類。而且，如果聚類生成的類不成球形的話，這種算法就運用得很好，因為它用半徑或者直徑來控制類的邊界。

2， Cure:

大多數的算法或者只能用于球狀類和有相似大小的類上面，或者無法解決特例的問題。 Cure 算法則能夠解決這些問題。

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

由于用了多個記錄來代表類，使得這種算法能夠很好地對付非球狀的的類以及一些例外的情況結構。那么，在大數據量的情況下能夠在不犧牲聚類質量的情況下，對付大數據量進行得很好。

為了對付大數據量， Cure 用了隨機抽取和分割的方法 :

1， 選取有 s 個記錄的采樣。

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

3， 將 s 個記錄分成 s/pq 個類。

4， 通過隨機采樣去除那些特例的情況。

5， 將這些類進行聚類，

五，基于密度的方法 :

?? 1,DBSCAN:

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

1， 對于給定的記錄，我們稱在其半徑 e 范圍內的一個記錄為這個記錄的 e- 鄰居。

2， 如果一個記錄的 e- 鄰居個數超過一個最小值， MinPts 那么我們就將這個記錄稱做中心記錄。

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

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

??????? 5, 如果 p,q 都是一個記錄 o 的“ density-reachable ”，那么就稱 p,q “ density-connected ”。

??????? 根據上面的定義，我們怎樣來發現類呢？首先掃描一下數據庫，計算每一個點（記

??????? 錄）的 e- 鄰居的個數，如果一個記錄的 e- 鄰居的個數大于一個門限值，那么就將

?????? 這個記錄叫做中心記錄，這樣一個新的以這個記錄為中心的類就產生了。接著，就

?????? 尋找這個記錄的所有的“ density-reachable ”記錄，這個過程可能會將一些類也合

?????? 并過，這個過程直到沒有新的記錄假如為止。

????? 2,OPTICS:

?????? ? 雖然 DBSCAN 算法能夠根據給定的參數 e 和 MinPts 來對記錄進行聚類，但是這 ??

??????? 仍然由用戶主觀來選擇參數，參數就影響了最終產生的類，實際上這也是很多聚

??????? 集算法面臨的問題。這些參數都是根據經驗來取的，因此很難決定該選哪個，特

??????? 別是對實際的，多屬性的數據。大多數的算法對這些參數都是很敏感的，很小的

??????? 一些差別就有可能導致大不相同的聚類結果。聚類結果。

??????? 為了解決這些問題，一個順序聚類的方法“ OPTICS ”就被提出來了。再來看看

? ???? ?????? DBSCAN, 我們很容易就可以發現，對于給定的一個 Min Pts 值，那些參數 e 的值

??????? 小的所得到的類一定完全包含在 e 值大的類當中了。注意一點這兒的 e 是一個距

? ??????????? 離（它是鄰居半徑）。因此，為了得到類的集合，我們設定了提供了距離參數的集

??? ?????? ?????? 合。為了同時建立不同的類，這些記錄應該以一種順序形式組織起來。這樣我們

就可以將 e 從小開始產生類了。基于這些理念，對于每一個記錄都應該存儲 2 個

值—— core-distance 和 reachability-distance:

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

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

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

個距離就是 e’, 其他的就是真實的距離。如果 p 不是中心記錄，它就沒有被定義。

對于在數據庫中的每一個記錄，首先將它們編號，然后計算每個記錄的這兩個距

離值。這就使得我們有足夠的信息來在 e 小于等于 e’ 的范圍內得到很多的聚類結

果了。

3， DENCLUE.

這個聚類方法主要基于下面的一些思想：

a, 一個記錄的影響力可以用一個數學函數來表示，叫做“影響函數”，這表明了一個記錄對于其鄰居記錄的影響。

b, 整個數據空間的密度可以用所有的記錄的“影響函數”的總和來模化。

c, 類可以通過確定“ density attrator ”來得到，這兒的“ density attrator ”是指在某個區域的最高峰。

基 于 模 型 的 聚 集 方 法

1，統計的方法：

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

???? 大多數的概念聚類采用了一個統計的方法——在決定一個類的時候，用可能性的描述語句。 COBWEB 是一個通用且簡單的概念聚類的方法，它用分類樹的形式來表現層次聚類。

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

???? COBWEB 用了一種啟發式的評估衡量標準（ category utility ）來引導樹的建立。

? ???CU 的定義：

???? 這兒的 n 是節點的個數，也就是類的個數。從另外一種意義上來說， CU 的 P(Ai=Vij|) 表示了在條件 Ck 和沒有條件 Ck 之下的偏差。

???? 下面我們來看看 COBWEB 的工作過程：它以增入的方式將記錄加入到分類樹中去，就象 Leader 算法一樣，它對于一個新的記錄計算它與以分好的類的匹配度，選擇最好的節點將這個新的記錄放進去。這個方法先將新記錄暫時放到每一個已經形成的類中，然后計算放入后的每次放入后的 CU 值，值最大的就是我們要找的最匹配的類。

???? 那么，假如這個新記錄不屬于任何一個以形成的類時怎么辦？實際上， COBWEB 也計算將這個新的記錄作為一個新的節點時 CU 的值，如果這個值比上述過程所得到的都要大的話，就建立一個新類。值得注意的是， COBWEB 能夠自己調整類的數目的大小，而不向其他算法那樣自己設定類的個數。

???? 但上述的操作對于的記錄的順序很敏感， COBWEB 利用兩個操作來將這種敏感性降到最低，這就是 merging 和 splitting 的方法，當對一個新的記錄進行分類的時候，兩個最好的類就可能被合并，當然這些決定必須根據 CU 值來。

???? COBWEB 的缺點：這個方法假定根據統計得到的對于單個屬性的概率分布函數與其他的屬性之間是獨立的，實際上在兩個屬性之間通常會存在一些聯系。

2，神經網絡的方法

?? 神經網絡用于聚類的方法是將每一個類看作一個標本，它是這個類的“典型”，但不需和某個具體的記錄或例子相對應。根據新記錄和這個標本之間的距離，就可以將這個記錄進行分類了。

?? 在這篇中，我們介紹 2 個神經網絡用做聚類的方法，分別是“ competitive learning ”和“ self-organizing feature maps ”。

異常情況分析

很多時候，會有一些記錄與通常的行為不一樣，對于那些跟數據庫中其他的記錄不相符合的記錄，我們稱之為 outliers 。

??? Outliers 可能在聚類運行或者檢測的時候被發現，比如一個人的年齡是 999 ，這個在對數據庫進行檢測的時候就會被發現。還有，就是 outliers 可能是本身就固有的，而不是一個錯誤，比如部門經理的工資就比一般員工的工資高出很多。

??? 很多數據挖掘技術都力圖將 outliers 的影響降到最小，直至完全沒有。但是，這有可能失去一些重要的隱藏的信息，因為對于一方來講是“壞”的東西而對于另外的一方來講很可能是重要的東西。換句話說，這個“異常”可能有特別的作用，例如發現詐騙行為。因此，發現和分析“詐騙行為”是一相很有意義的數據挖掘任務，我稱為“ outlier mining ”。

outlier mining 的應用是很廣泛的，除了上面說的“欺騙發現”以外，它還能夠發現收入特別低或者特別高的顧客的購買行為。 outlier mining 可以這么來描述：給定 n 個個記錄，和 k （我們期望得到的 outlier 的個數）；發現 k 個與其他的記錄最不相象的記錄。這個過程可以看成 2 個子過程： 1 ，首先定義什么樣的記錄被稱為“異常”； 2 ，根據上面的定義，找到一個很有效的方法來發現這些異常。

在這篇文章里，我們介紹了三種方法來發現 outlier ：

1， 基于統計的方法 ：

統計的方法先假定在訓練集中有一個分布模式存在，并且用一個“ discordancy test ”的方法來定義和發現 outliers 。這個方法的應用首先要設定一些參數——假定的分布模式，分布的參數，期望得到的 outlier 的的個數等等。

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

2， 基于距離的方法 ：

如果一個記錄的距離大于 d 的鄰居的個數大于一個設定值 p 的話，就可以認為這個記錄是個 outlier 。換句話說，就是這個記錄沒有足夠的鄰居數目，這兒的鄰居是根據距離來確定的。

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

Nest-loop algorithm: 與上一個方法相比，它優點在于減少輸入、出個數，提高儲存效率。

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

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

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

這種方法是根據一個數據集中的主要特征來判定 outlier 的，那些與這個主要特征背離很大的記錄就被認為是一個 outlier 。

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

在這個序列中我們可以計算子集間的不相象性，下面介紹幾個關鍵的概念。

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

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

Cardinality function: 它計算在給定的一個集合中記錄的個數。

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

聚類的方法小節：

?? 這篇文章很全面的介紹了聚類：包括聚類的定義，聚類的應用，聚類的幾種常用的算法 , ， 最后還介紹了異常的檢測。

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

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

?

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

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

用途

聚集

讓用戶在較高的層次上觀察數據庫。常被用來做商業上的顧客分片（segmentation）。

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

最近鄰居

預測，距離相近的對象通常他們的預測值也相似，因此只要知道一個對象的預測值，就可以用他來預測他的鄰居的值。

分數卡

凡是有該標志的文章，都是該blog博主Caoer（草兒）原創，凡是索引、收藏
、轉載請注明來處和原文作者。非常感謝。