3.K-Means 介紹
K-Means ：最為經典的基于劃分的聚類方法，是十大經典資料挖掘算法之一。
基本思想：以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過疊代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結果。
3.1 K-Means聚類原理：
假設我們提取到原始資料的集合為(X1, X2, „, Xn)，并且每個Xi為d維的向量（d維向量由原始資料的d個特征組成），K-means聚類的目的就是，在給定分類組數k（k ≤ n）值的條件下，将原始資料分成k類 S = {S1, S2, …, Sk}。
3.2 K-Means 執行過程：
①從資料集D中随機取k個元素，作為k個簇的各自的中心。
②分别計算剩下的元素到k個簇中心的相異度，将這些元素分别劃歸到相異度最低的簇。
③根據聚類結果，重新計算k個簇各自的中心，計算方法是取簇中所有元素各自次元的算術平均數。
④将D中全部元素按照新的中心重新聚類。
⑤重複第3、4步，直到每個簇的中心基本不再變化。
⑥将結果輸出。
難點主要是初始中心K值的選擇。
我們經常接觸到的聚類分析，一般都是數值聚類，一種常見的做法是同時提取 N 種特征，将它們放在一起組成一個 N 維向量，進而得到一個從原始資料集合到 N 維向量空間的映射——總是需要顯式地或者隐式地完成這樣一個過程，然後基于某種規則進行分類，在該規則下，同組分類具有最大的相似性。
聚類屬于無監督學習，以往的回歸、樸素貝葉斯、SVM等都是有類别标簽y的，也就是說樣例中已經給出了樣例的分類。而聚類的樣本中卻沒有給定y，隻有特征x。
3.3 K-Means 過程圖如下：
如圖所示，資料樣本用圓點表示，每個簇的中心點用叉叉表示。(a)剛開始時是原始資料，雜亂無章，沒有label，看起來都一樣，都是綠色的。(b)假設資料集可以分為兩類，令K=2，随機在坐标上選兩個點，作為兩個類的中心點。(c-f)示範了聚類的兩種疊代。先劃分，把每個資料樣本劃分到最近的中心點那一簇；劃分完後，更新每個簇的中心，即把該簇的所有資料點的坐标加起來去平均值。這樣不斷進行”劃分—更新—劃分—更新”，直到每個簇的中心不在移動為止。
3.4 k-Means聚類算法的應用
聚類就是按照一定的标準将事物進行區分和分類的過程，該過程是無監督的，即事先并不知道關于類分的任何知識。聚類分析又稱為資料分割，它是指應用數學的方法研究和處理給定對象的分類，使得每個組内部對象之間的相關性比其他對象之間的相關性高，組間的相異性較高。
聚類算法被用于許多知識領域，這些領域通常要求找出特定資料中的“自然關聯”。自然關聯的定義取決于不同的領域和特定的應用，可以具有多種形式。
3.5 K-Means 典型的應用例如：
①商務上，幫助市場分析人員從客戶基本資料庫中發現不同的客戶群，并用購買模式來刻畫不同客戶群的特征；
②聚類分析是細分市場的有效工具，同時也可用于研究消費者行為，尋找新的潛在市場、選擇實驗的市場，并作為多元分析的預處理；
③生物學上，用于推導植物和動物的分類，對基因進行分類，獲得對種群固有結構的認識；
④地理資訊方面，在地球觀測資料庫中相似區域的确定、汽車保險單持有者的分組，及根據房子的類型、價值和地理位置對一個城市中房屋的分組上可以發揮作用；
4.Canopy 算法介紹
Canopy聚類算法是一個将對象分組到類的簡單、快速、精确地方法。每個對象用多元特征空間裡的一個點來表示。這個算法使用一個快速近似距離度量和兩個距離門檻值 T1>T2來處理。
基本的算法是，從一個點集合開始并且随機删除一個，建立一個包含這個點的Canopy，并在剩餘的點集合上疊代。對于每個點，如果它距離第一個點的距離小于T1，然後這個點就加入這個聚集中。除此之外，如果這個距離<T2，然後将這個點從這個集合中删除。這樣非常靠近原點的點将避免所有的未來處理，不可以再做其它Canopy的中心。這個算法循環到初始集合為空為止，聚集一個集合的Canopies，每個可以包含一個或者多個點。每個點可以包含在多于一個的Canopy中。
Canopy算法其實本身也可以用于聚類，但它的結果可以為之後代價較高聚類提供幫助，其用在資料預處理上要比單純拿來聚類更有幫助。Canopy聚類經常被用作更加嚴格的聚類技術的初始步驟，像是K均值聚類。建立canopies之後，可以删除那些包含資料點數目較少的canopy，往往這些canopy是包含孤立點的。
4.1 Canopy算法的步驟
（1） 将所有資料放進list中，選擇兩個距離，T1，T2，T1>T2
（2）While(list不為空)
{
随機選擇一個節點做canopy的中心；并從list删除該點；
周遊list：
對于任何一條記錄，計算其到各個canopy的距離；
如果距離<T2,則給此資料打上強标記，并從list删除這條記錄；
如果距離<T1,則給此資料打上弱标記；
如果到任何canopy中心的距離都>T1,那麼将這條記錄作為一個新的canopy的中心，并從list中删除這個元素；
}
需要注意的是參數的調整：
當T1過大時，會使許多點屬于多個Canopy，可能會造成各個簇的中心點間距離較近，各簇間差別不明顯；
當T2過大時，增加強标記資料點的數量，會減少簇個個數；T2過小，會增加簇的個數，同時增加計算時間；
過程圖如下所示：
4.2 計算兩點間的距離的方法
CosineDistanceMeasure：計算兩向量間的夾角
SquaredEuclideanDistanceMeasure：計算歐式距離的平方
EuclideanDistanceMeasure：計算歐式距離
ManhattanDistanceMeasure：馬氏距離，貌似圖像進行中用的比較多
4.3 Canopy使用注意點
- 首先是輕量距離量度的選擇，是選擇資料模型其中的一個屬性，還是選擇其他外部屬性這對canopy的分布最為重要。
- T1,T2的取值影響到canopy重疊率f，以及canopy的粒度；
- Canopy有消除孤立點的作用，而k-means在這方面卻無能為力。建立canopies之後，可以删除那些包含資料點數目較少的canopy，往往這些canopy是包含孤立點的；
- 根據canopy内點的數目，來決定聚類中心數目k，這樣效果比較好；
4.4 Canopy算法
與傳統的聚類算法(比如K-means)不同，Canopy聚類最大的特點是不需要事先指定k值(即clustering的個數)，是以具有很大的實際應用價值。與其他聚類算法相比，Canopy聚類雖然精度較低，但其在速度上有很大優勢，是以可以使用Canopy聚類先對資料進行“粗”聚類，得到k值，以及大緻的K歌中心點，再使用K-means進行進一步“細”聚類。是以Canopy+K-means這種形式聚類算法聚類效果良好。
4.5 Canopy算法解析：
1）原始資料集合List按照一定的規則進行排序（這個規則是任意的，但是一旦确定就不再更改），初始距離門檻值為T1、T2，且T1＞T2（T1、T2的設定可以根據使用者的需要，或者使用交叉驗證獲得）。
2）在List中随機挑選一個資料向量A，使用一個粗糙距離計算方式計算A與List中其他樣本資料向量之間的距離d。
3）根據第2步中的距離d，把d小于T1的樣本資料向量劃到一個canopy中，同時把d小于T2的樣本資料向量從候選中心向量名單（這裡可以了解為就是List）中移除。
4）重複第2、3步，直到候選中心向量名單為空，即List為空，算法結束。
算法原理比較簡單，就是對資料進行不斷周遊，T2<dis<T1的可以作為中心名單，dis<T2的認為與canopy太近了，以後不會作為中心點，從list中删除，這樣的話一個點可能屬于多個canopy。
Canopy的效果圖：
4.6 Canopy算法優勢：
1、Kmeans對噪聲抗幹擾較弱，通過Canopy對比較小的NumPoint的Cluster直接去掉 有利于抗幹擾。
2、Canopy選擇出來的每個Canopy的centerPoint作為Kmeans比較科學。
3、隻是針對每個Canopy的内容做Kmeans聚類，減少相似計算的數量。
總結起來就是四個關鍵詞：噪聲點，K值，K中心點，計算開銷。（盡管這個算法準确性不是很理想，但是還是有用武之地的）
4.7 Canopy+K-Means的混合算法
Canopy+K-MEANS算法思路如下：
Stage1、聚類最耗費計算的地方是計算對象相似性的時候，Canopy Method在第一階段選擇簡單、計算代價較低的方法計算對象相似性，将相似的對象放在一個子集中，這個子集被叫做Canopy，通過一系列計算得到若幹Canopy，Canopy之間可以是重疊的，但不會存在某個對象不屬于任何Canopy的情況，可以把這一階段看做資料預處理；
Stage2、在各個Canopy内使用傳統的聚類方法(如K-means)，不屬于同一Canopy的對象之間不進行相似性計算。從這個方法起碼可以看出兩點好處：首先，Canopy不要太大且Canopy之間重疊的不要太多的話會大大減少後續需要計算相似性的對象的個數；其次，類似于K-means這樣的聚類方法是需要人為指出K的值的，通過Stage1得到的Canopy個數完全可以作為這個K值，一定程度上減少了選擇K的盲目性。
5.聚類算法K-Means與Canopy
首先介紹先K-means算法：所有做聚類分析的資料對象，會被描述成n為空間中的一個點，用向量（Vector）表示；算法開始會随機選擇K個點，作為一個簇的中心，然後其餘的點會根據它與每個簇心的距離，被配置設定到最近簇中去；接着以疊代的方式，先重新計算每個簇的中心（通過其包含的所有向量的平均值），計算完成後對所有點屬于哪個簇進行重新劃分；一直如此疊代直到過程收斂；可證明疊代次數是有限的。
雖然K-means簡單且高效，但它存在一定問題，首先K值（即簇的數量）是人為确定的，在對資料不了解的情況下，很難給出合理的K值；其次初始簇心的選擇是随機的，若選擇到了較孤立的點，會對聚類的效果産生非常大的影響。是以通常會用Canopy算法配合，進行初始化，确定簇數以及初始簇心。
Canopy算法首先會要求輸入兩個閥值 T1和T2，T1>T2；算法有一個叢集這裡叫Canopy的集合（Set），當然一開始它是空的；然後會将讀取到的第一個點作為集合中的一個Canopy，接着讀取下一個點，若該點與集合中的每個Canopy計算距離，若這個距離小于T1，則這個點會配置設定給這個Canopy（一個點可以配置設定給多個Canopy），而當這個距離小于T2時這個點不能作為一個新的Canopy而放到集合中。也就是說當一個點隻要與集合中任意一個Canopy的距離小于T2了，即表示它與那個Canopy太近不能作為新的Canopy。若都沒有則生成一個新的Canopy放入集合中。以此循環，直到沒有點了。
是以這裡用到的聚類分析算法的思路是：首先通過Canopy算法進行聚類，以确定簇數以及初始簇中心向量，接着通過K-means算法進行疊代運算，收斂出最後的聚類結果。