????? 原文鏈接：http://blog.csdn.net/yclzh0522/article/details/6839643

????? Canopy聚類算法是可以并行運(yùn)行的算法，數(shù)據(jù)并行意味著可以多線程進(jìn)行，加快聚類速度，開源ML庫Mahout使用。

一、概念 ? ?

?????? 與傳統(tǒng)的聚類算法(比如 K-means )不同，Canopy 聚類最大的特點(diǎn)是不需要事先指定 k 值( 即 clustering 的個(gè)數(shù))，因此具有很大的實(shí)際應(yīng)用價(jià)值。與其他聚類算法相比，Canopy聚類雖然精度較低，但其在速度上有很大優(yōu)勢，因此可以使用 Canopy 聚類先對數(shù)據(jù)進(jìn)行“粗”聚類，（摘自于Mahout一書：Canopy算法是一種快速地聚類技術(shù)，只需一次遍歷數(shù)據(jù)科技得到結(jié)果，無法給出精確的簇結(jié)果，但能給出最優(yōu)的簇?cái)?shù)量。可為K均值算法優(yōu)化超參數(shù)..K....）得到 k 值后再使用 K-means 進(jìn)行進(jìn)一步“細(xì)”聚類。這種Canopy + K-means的混合聚類方式分為以下兩步：

?Step1、聚類最耗費(fèi)計(jì)算的地方是計(jì)算對象相似性的時(shí)候，Canopy 聚類在第一階段選擇簡單、計(jì)算代價(jià)較低的方法計(jì)算對象相似性，將相似的對象放在一個(gè)子集中，這個(gè)子集被叫做Canopy ，通過一系列計(jì)算得到若干Canopy，Canopy 之間可以是重疊的，但不會存在某個(gè)對象不屬于任何Canopy的情況，可以把這一階段看做數(shù)據(jù)預(yù)處理；

?Step2、在各個(gè)Canopy?內(nèi)使用傳統(tǒng)的聚類方法(如K-means)，不屬于同一Canopy 的對象之間不進(jìn)行相似性計(jì)算。

????? 從這個(gè)方法起碼可以看出兩點(diǎn)好處：首先，Canopy 不要太大且Canopy 之間重疊的不要太多的話會大大減少后續(xù)需要計(jì)算相似性的對象的個(gè)數(shù)；其次，類似于K-means這樣的聚類方法是需要人為指出K的值的，通過Stage1得到的Canopy 個(gè)數(shù)完全可以作為這個(gè)K值，一定程度上減少了選擇K的盲目性。

二、聚類精度

????? 對傳統(tǒng)聚類來說，例如K-means、Expectation-Maximization、Greedy Agglomerative Clustering，某個(gè)對象與Cluster的相似性是該點(diǎn)到Cluster中心的距離，那么聚類精度能夠被很好保證的條件是：

????? 對于每個(gè)Cluster都存在一個(gè)Canopy，它包含所有屬于這個(gè)Cluster的元素。

????? 如果這種相似性的度量為當(dāng)前點(diǎn)與某個(gè)Cluster中離的最近的點(diǎn)的距離，那么聚類精度能夠被很好保證的條件是：

????? 對于每個(gè)Cluster都存在若干個(gè)Canopy，這些Canopy之間由Cluster中的元素連接（重疊的部分包含Cluster中的元素）。

????? 數(shù)據(jù)集的Canopy劃分完成后，類似于下圖：

三、Canopy算法流程

????? （1）將數(shù)據(jù)集向量化得到一個(gè)list后放入內(nèi)存，選擇兩個(gè)距離閾值：T1和T2，其中T1 > T2，對應(yīng)上圖，實(shí)線圈為T1，虛線圈為T2，T1和T2的值可以用交叉校驗(yàn)來確定；

????? （2）從list中任取一點(diǎn)P，用低計(jì)算成本方法快速計(jì)算點(diǎn)P與所有Canopy之間的距離（如果當(dāng)前不存在Canopy，則把點(diǎn)P作為一個(gè)Canopy），如果點(diǎn)P與某個(gè)Canopy距離在T1以內(nèi)，則將點(diǎn)P加入到這個(gè)Canopy；

????? （3）如果點(diǎn)P曾經(jīng)與某個(gè)Canopy的距離在T2以內(nèi)，則需要把點(diǎn)P從list中刪除，這一步是認(rèn)為點(diǎn)P此時(shí)與這個(gè)Canopy已經(jīng)夠近了，因此它不可以再做其它Canopy的中心了；

????? （4）重復(fù)步驟2、3，直到list為空結(jié)束。

?????? 注意：Canopy聚類不要求指定簇中心的個(gè)數(shù)，中心的個(gè)數(shù)僅僅依賴于舉例度量，T1和T2的選擇。

Python代碼：

#-*- coding:utf-8 -*- ''' ''' import numpy as np import matplotlib as nlp#The first op import scipy as sp import scipy.sparse.linalg import time from Old_regression import crossValidation#使用K均值 import kMeans as kmdef canopyClustering(datalist):state =[];#交叉驗(yàn)證獲取T1和T2;T1,T2 = crossValidation(datalist);#canopy 預(yù)聚類canopybins= canopy(datalist, T1 , T2);#使用K均值聚類k =len(canopybins);createCent = [canopy[0] for canopy in canopybins];#獲取canopybins中心dataSet = datalist；centroids, clusterAssment =km.kMeans(dataSet, k, distMeas=distEclud, createCent);return clusterAssment;#得到一個(gè)list后放入內(nèi)存，選擇兩個(gè)距離閾值：T1和T2，其中T1 > T2 #Canopy聚類不要求指定簇中心的個(gè)數(shù)，中心的個(gè)數(shù)僅僅依賴于舉例度量，T1和T2的選擇。 def canopy(datalist, T1 , T2):#state = [];datalist = [];#初始化第一個(gè)canopy元素canopyInit = datalist.pop();canopyCenter= calCanopyCenter([canopyInit] );canopyC = [canopyInit];#建立第一個(gè)canopycanopybins = [];canopybins.append([canopyCenter,canopyC ] );while not(len(datalist) ==0 ):PointNow =datalist[len(datalist)-1 ];#PointNow =datalist.pop();counter = 0;for canopy in canopybins:dis =calDis(PointNow, canopy[0]);#如果點(diǎn)P與某個(gè)Canopy距離在T1以內(nèi)，則將點(diǎn)P加入到這個(gè)Canopy；if dis<T1:canopy[1].append(PointNow);counter +=1;#break;if dis<T2:#點(diǎn)P曾經(jīng)與某個(gè)Canopy的距離在T2以內(nèi)，則需要把點(diǎn)P從list中刪除，#這一步是認(rèn)為點(diǎn)P此時(shí)與這個(gè)Canopy已經(jīng)夠近了，因此它不可以再做其它Canopy的中心了if not(counter ==0):#保證必須率屬于一個(gè)canopydel list[len(datalist)-1 ];break;else:#建立一個(gè)新的CanopycanopyC = [PointNow];canopyCenter= PointNow;canopybins.append([canopyCenter,canopyC ] );return canopybins;def calDis(va,vb):dis =0;for i in range(len(va) ):dis += va[i]*va[i]+ vb[i]*vb[i];return dis;#計(jì)算canopy中心 def calCanopyCenter(datalist):center =datalist[0];for i in len(range(center) ):center[i]=0;for data in datalist:center +=data;center /= len(center);return center;

總結(jié)

以上是生活随笔為你收集整理的Canopy聚类算法分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。