第十二章聚類數(shù)據(jù)挖掘原理、算法與應(yīng)用（Python語言描述）聚類的定義聚類是典型的無監(jiān)督學(xué)習(xí)方法，?聚類將數(shù)據(jù)集中相似的樣本分到一組，每個組稱為一個簇，相同簇的樣本之間相似度較高，不同簇的樣本之間相似度較低，樣本之間的相似度通常是通過距離定義的，距離越遠，相似度越低。聚類與分類的區(qū)別不同于分類，分類是有監(jiān)督學(xué)習(xí)，樣本帶有標簽，分類模型重點考查的是模型的泛化能力；而聚類是按要求給樣本加標簽，重點考查模型聚類的效果，通常不需進行訓(xùn)練集與測試集的劃分。聚類的應(yīng)用聚類廣泛應(yīng)用于社會的各個領(lǐng)域。如根據(jù)客戶的消費記錄將客戶分成不同的消費群體；根據(jù)學(xué)生的不同行為習(xí)慣，將學(xué)生聚類，以便因材施教；根據(jù)全球各地觀測到的氣候特征，將全球劃分為不同的氣候區(qū)域。聚類也常用于數(shù)據(jù)預(yù)處理，找出數(shù)據(jù)集中的離群值。常用的聚類方法有：K-Means、AgglomerativeClustering、DBSCAN、MeanShift、SpectralClustering等。學(xué)習(xí)目標（1）

掌握樣本距離的常用計算方法。（2）掌握K均值聚類方法。（3）掌握層次聚類方法。（4）了解其他聚類方法。（5）掌握聚類模型的評價方法。目錄樣本距離計算歐氏距離曼哈頓距離切比雪夫距離閔可夫斯基距離余弦相似性相關(guān)距離杰卡德距離漢明距離常用聚類方法聚類模型評價案例：汽車車型聚類

12.1樣本距離計算數(shù)據(jù)挖掘算法中，K近鄰、聚類算法等都需要計算樣本間的距離，也就是計算不同樣本的相似性。樣本間距離的計算方法與具體解決的問題相關(guān)。常用的距離計算方法有：歐氏距離、曼哈頓距離、切比雪夫距離、閔可夫斯基距離、余弦相似性等。12.1.1歐氏距離歐氏距離是歐幾里得空間中兩點之間的直線距離，通常把樣本的不同特征看成歐幾里得空間的不同維度，是最常用的一種距離計算方法，n維空間的歐氏距離計算公式如下：12.1.1歐氏距離例12-1使用Numpy計算兩個樣本歐式距離importnumpyasnpx1=np.array([1,2,3])x2=np.array([4,5,6])d12=np.sqrt(np.sum(np.square(x1-x2)))#計算x1,x2的歐式距離print(d12)#輸出x1,x2的歐式距離輸出x1,x2的歐式距離為：5.19615242270663212.1.1歐氏距離例12-2使用scipy.spatial.distance中的pdist方法計算歐氏距離fromscipy.spatial.distanceimportpdistd12=pdist([x1,x2],"euclidean")#計算x1,x2的歐式距離print(d12)#輸出x1,x2的歐式距離輸出x1,x2的歐式距離為：5.1961524212.1.2曼哈頓距離曼哈頓距離是在歐幾里德空間的固定直角坐標系上兩點所形成的線段對坐標軸產(chǎn)生的投影的距離總和。就如在城市兩點之間不能橫穿，必須沿著街道走。曼哈頓距離也稱為城市街區(qū)距離(CityBlockdistance)。n維空間兩點的曼哈頓距離為：12.1.2曼哈頓距離例12-3使用Numpy計算x1,x2兩個樣本曼哈頓距離importnumpyasnpx1=np.array([1,2,3])x2=np.array([4,5,6])d12=sum(np.abs(x1-x2))#計算x1,x2的曼哈頓距離print(d12)#輸出x1,x2的曼哈頓距離x1,x2的曼哈頓距離：912.1.2曼哈頓距離例12-4

使用scipy.spatial.distance包中的pdist方法計算曼哈頓距離fromscipy.spatial.distanceimportpdistd12=pdist([x1,x2],"cityblock")#計算x1,x2的曼哈頓距離print(d12)#輸出x1,x2的曼哈頓距離x1,x2的曼哈頓距離：912.1.3切比雪夫距離切比雪夫距離是n維空間各坐標數(shù)值差絕對值的最大值。如國際象棋中國王走一步能夠移動到相鄰的8個方格中的任意一個。那么國王從格子(x1,y1)走到格子(x2,y2)最少需要的步數(shù)是max(|x2-x1|,|y2-y1|)步。n維空間中類似的一種距離度量稱為切比雪夫距離。12.1.3切比雪夫距離例12-5使用Numpy計算x1,x2兩個樣本切比雪夫距離importnumpyasnpnp.abs(x1-x2).max()輸出切比雪夫距離為：312.1.3切比雪夫距離例12-6

使用scipy.spatial.distance中的pdist方法計算切比雪夫距離fromscipy.spatial.distanceimportpdistd12=pdist([x1,x2],"chebyshev")輸出切比雪夫距離為：312.1.4閔可夫斯基距離閔可夫斯基距離不是一種距離，而是將多個距離公式（如曼哈頓距離、歐式距離、切比雪夫距離）總結(jié)成為的一個公式。兩個n維變量x1與x2間的閔可夫斯基距離(MinkowskiDistance)定義為：其中p是一個變參數(shù)，可以根據(jù)需要取值。當p=1時，計算曼哈頓距離；當p=2時，計算歐氏距離；當p→∞時，計算切比雪夫距離。12.1.4閔可夫斯基距離例12-7使用Numpy包計算x1,x2兩個樣本的閔可夫斯基距離importnumpyasnpp=3np.sum(np.abs(x1-x2)**p)**(1/p)輸出閔可夫斯基距離為：4.326748710922224512.1.4閔可夫斯基距離例12-8使用scipy.spatial.distance中的pdist方法計算fromscipy.spatial.distanceimportpdistpdist([x1,x2],"minkowski",p=3)輸出閔可夫斯基距離為：4.3267487112.1.5余弦相似性對文本數(shù)據(jù)分析時，常用余弦相似性來計算文本的相似性，其值越大說明文檔越相似。計算余弦相似性的公式為。使用scipy.spatial.distance中的pdist方法計算x1,x2兩個樣本的余弦相似性。12.1.5余弦相似性例12-9

pdist方法計算x1,x2兩個樣本的余弦相似性fromscipy.spatial.distanceimportpdistpdist([x1,x2],"cosine")輸出x1,x2余弦相似性為：0.0253681512.1.6相關(guān)距離相關(guān)系數(shù)(Correlationcoefficient)是衡量隨機變量X與Y相關(guān)程度的一種方法，相關(guān)系數(shù)的取值范圍是[-1,1]。相關(guān)系數(shù)的絕對值越大，則表明X與Y相關(guān)度越高。當X與Y線性相關(guān)時，相關(guān)系數(shù)取值為1（正線性相關(guān)）或-1（負線性相關(guān)）。其計算公式為：12.1.6相關(guān)距離對于n維隨機變量，它返回一個n×n方矩陣M，其中M(i,j)表示隨機變量i和j之間的相關(guān)系數(shù)。由于變量與變量自身之間的相關(guān)系數(shù)為1，因此所有對角線項(i,i)均等于1。對應(yīng)的相關(guān)距離計算公式為：12.1.6相關(guān)距離例12-10使用scipy.spatial.distance中的pdist方法計算x1,x2兩個樣本的相關(guān)距離fromscipy.spatial.distanceimportpdistimportnumpyasnpx1=np.array([1,2,3])x2=np.array([4.5,5.2,6.1])pdist([x1,x2],"correlation")#相關(guān)距離(Correlationdistance)x1,x2的相關(guān)距離為：0.0025940412.1.6相關(guān)距離例12-11使用numpy計算相關(guān)距離x12corr=np.corrcoef([x,y])#相關(guān)系數(shù)1-x12corr#計算相關(guān)距離取輸出矩陣[1,2]或[2,1]位置的元素，x1,x2的相關(guān)距離為：0.00259403812.1.7杰卡德距離二元屬性常常用1和0代表兩種取值，此類屬性對象的相似度可以用杰卡德距離計算。杰卡德相似系數(shù)是指兩個集合A、B的交集元素在A、B的并集中所占的比例，稱為兩個集合的杰卡德相似系數(shù)，用符號J(A,B)表示：12.1.7杰卡德距離杰卡德距離(JaccardDistance)與杰卡德相似系數(shù)相反，用兩個集合中不同元素占所有元素的比例來衡量兩個集合的區(qū)分度。12.1.7杰卡德距離例12-12使用scipy.spatial.distance中的pdist方法計算x1,x2兩個樣本的杰卡德距離fromscipy.spatial.distanceimportpdistimportnumpyasnpx1=np.array([1,2,3,4,5])x2=np.array([2,3,4,5,6])pdist([x1,x2],"Jaccard")#計算、輸出x1,x2兩個樣本的杰卡德距離x1，x2對應(yīng)位置無相同元素，杰卡德相似系數(shù)為0，杰卡德距離為：112.1.7杰卡德距離例12-12使用scipy.spatial.distance中的pdist方法計算x1,x2兩個樣本的杰卡德距離x1=np.array([2,2,3,4,5])x2=np.array([2,3,4,4,5])pdist([x1,x2],"Jaccard")#計算、輸出x1,x2兩個樣本的杰卡德距離x1、x2兩個向量的5個對應(yīng)位置上有3個相同元素，杰卡德相似系數(shù)為0.6，輸出距離為0.4。12.1.8漢明距離漢明距離也稱為漢明重量，定義為將兩個等長字符串s1與s2其中一個變?yōu)榱硗庖粋€所需要作的最小替換次數(shù)。例12-13使用scipy.spatial.distance中的pdist方法計算x1,x2兩個樣本的漢明距離fromscipy.spatial.distanceimportpdistimportnumpyasnpx1=list(int(c)forcin"12345")x2=list(int(c)forcin"12345")pdist([x1,x2],'hamming')#計算、輸出兩個樣本的漢明距離x1,x2兩個樣本的漢明距離（替換次數(shù)/長度）：0.4目錄樣本距離計算常用聚類方法K均值聚類層次聚類帶噪聲的基于密度的聚類方法均值漂移聚類譜聚類聚類模型評價案例：汽車車型聚類

12.2常用聚類方法本節(jié)使用sklearn.Datasets的make_moons方法生成雙月亮數(shù)據(jù)集，make_blobs生成多類別的數(shù)據(jù)集。例12-14數(shù)據(jù)集生成并可視化fromsklearn.datasetsimportmake_circles,make_moons,make_blobsdata_blobs,color_blobs=make_blobs(n_samples=1000,n_features=2)data_moons,color_moons=make_moons(n_samples=1000,noise=0.1)importmatplotlib.pyplotaspltplt.rcParams["font.sans-serif"]=["SimHei"]plt.rcParams["axes.unicode_minus"]=False12.2常用聚類方法例12-14數(shù)據(jù)集生成并可視化data=data_blobscolor=color_blobsfig=plt.figure(figsize=(10,7))plt.scatter(data[:,0],data[:,1],c=color,cmap=plt.cm.Spectral)plt.title("blobs")color=color_s_curvefig=plt.figure(figsize=(10,7))ax=plt.axes(projection="3d",elev=10,azim=80)ax.scatter3D(data[:,0],data[:,1],data[:,2],c=color,cmap=plt.cm.Spectral)plt.title("S_Curve")12.2常用聚類方法例12-14數(shù)據(jù)集生成并可視化data=data_moonscolor=color_moonsfig=plt.figure(figsize=(10,7))#Creatingaplotusingtherandomdatasetsplt.scatter(data[:,0],data[:,1],c=color,cmap=plt.cm.Spectral)plt.title("D_circles")12.2.1

K均值聚類K均值聚類算法是使用最廣泛的聚類方法。該算法首先從數(shù)據(jù)集中隨機抽取k個樣本作為初始聚類的中心，由這個中心代表各個聚類；然后計算數(shù)據(jù)集中所有的樣本到這k個中心點的距離，并將數(shù)據(jù)集的樣本點歸到離其最近的聚類里；最后計算各個聚類的均值，以此作為新的聚類中心。重復(fù)以上過程直到聚類的中心不再移動或者移動距離足夠小，此時算法收斂；當?shù)拇螖?shù)達到上限也會結(jié)束計算，同時輸出提示信息。12.2.1

K均值聚類K均值算法計算量較大。其時間復(fù)雜度：上限為O(tKmn)，下限為O（Kmn）其空間復(fù)雜度：O((m+K)n)其中，t為迭代次數(shù)，K為簇的數(shù)目，m為樣本數(shù)，n為維數(shù)

。在計算過程中距離的度量可采用歐氏距離、曼哈頓距離、閔可夫斯基距離、余弦相似度等。不同的距離計算方式，有不同的聚類效果，需要根據(jù)聚類效果來確定最優(yōu)的距離計算方法。12.2.1

K均值聚類K為超參數(shù)，是用戶確定的類的數(shù)量。k一般不會設(shè)置很大，可以通過枚舉，令k從2到一個固定值（如10），在每個k值上重復(fù)運行數(shù)次K均值聚類，以避免獲取局部最優(yōu)解，并計算當前k值聚類結(jié)果的平均輪廓系數(shù)，最后選取輪廓系數(shù)最大的值對應(yīng)的k作為最終的集群數(shù)目。初始點的選擇影響收斂的速度，通常不使用完全隨機的方式，通常采用kmeans++、層次聚類、Canopy算法或指定點進行初始聚類12.2.1

K均值聚類方法1：kmeans++1.從輸入的數(shù)據(jù)點集合中隨機選擇一個點作為一個聚類中心；2.對于數(shù)據(jù)集中的每一個點i，計算它與最近聚類中心（指已選擇的聚類中心）的距離D(i)；3.選擇一個新的數(shù)據(jù)點作為新的聚類中心，選擇的原則是：D(i)較大的點，被選取作為聚類中心的概率較大；4.重復(fù)2和3直到k個聚類中心被選出來；5.利用這k個初始的聚類中心來運行標準的k-means算法。方法2：選用層次聚類或Canopy算法進行初始聚類，然后從k個類別中分別隨機選取k個點，來作為kmeans的初始聚類中心點。方法3：指定點。12.2.1

K均值聚類Kmeans參數(shù)說明：KMeans(n_clusters=8,#簇數(shù)init='k-means++',#初始質(zhì)心算法n_init=10,#初始化次數(shù)max_iter=300,#最大迭代次數(shù)tol=0.0001,#收斂閾值precompute_distances='deprecated',verbose=0,

#輸出信息詳細程度控制random_state=None,copy_x=True,#是否修改原始數(shù)據(jù)。預(yù)計算距離，數(shù)據(jù)減去均值后再加上均值引起數(shù)值的微小差別。algorithm='auto'#K-means使用的算法)12.2.1

K均值聚類例12-15K-Means聚類data=data_moonsmodel_km=KMeans(n_clusters=2,random_state=10,algorithm="elkan").fit(data)auto_label=model_km.labels_auto_cluster=model_km.cluster_centers_data=data_moonscolor=auto_labelfig=plt.figure(figsize=(5,3))plt.scatter(data[:,0],data[:,1],c=color)plt.title("D_moons聚類結(jié)果可視化")D_moons聚類結(jié)果可視化如右：12.2.1

K均值聚類例12-15K-Means聚類data=data_blobsmodel_km=KMeans(n_clusters=3,random_state=10,algorithm="elkan").fit(data)auto_label=model_km.labels_auto_cluster=model_km.cluster_centers_color=auto_labelfig=plt.figure(figsize=(5,3))plt.scatter(data[:,0],data[:,1],c=color)plt.title("blobs聚類結(jié)果可視化")blobs數(shù)據(jù)聚類結(jié)果可視化如下：12.2.2層次聚類層次聚類是通過計算不同類別數(shù)據(jù)點間的相似度來創(chuàng)建一棵有層次的嵌套聚類樹，不同類別的原始數(shù)據(jù)點是樹的最低層，樹的頂層是一個聚類的根節(jié)點。層次聚類有兩種常用的形式，自頂向下和自底向上。自頂向下法以樹的根開頭，將所有對象放在單個聚類中，根據(jù)不同簇簇間、簇內(nèi)的相似度大小重復(fù)分裂簇，直到簇的個數(shù)達到給定值。自底向上法在開始時，將每個樣本視為一個簇，重復(fù)合并最近的兩個簇，直到簇的個數(shù)達到給定值。通常用譜系圖來描述自底向上簇合并的過程。12.2.2層次聚類常用的度量簇間距離的方式有：完整連接法（complete）：兩簇之間最遠的樣本之間的距離。平均連接法（average）：兩簇間所有樣本對的距離的平均值。單連接法（single）：兩簇之間最近的樣本之間的距離。離差平方和法（ward）：兩簇的離差平方和之和（合并后的n*方差增量最?。?2.2.2層次聚類AgglomerativeClustering常用參數(shù)說明：AgglomerativeClustering(

n_clusters=2,#簇數(shù)affinity='euclidean',#距離計算方法memory=None,#指定緩存的目錄connectivity=None,#一個數(shù)組或者可調(diào)用對象或者為None，用于指定連接矩陣。它給出了每個樣本的可連接樣本。compute_full_tree='auto',#是否訓(xùn)練生成一顆完整的樹。linkage='ward',#簇的距離計算方法)12.2.2層次聚類例12-16層次聚類實現(xiàn)data=data_blobsfromsklearn.clusterimportAgglomerativeClusteringmodel=AgglomerativeClustering(n_clusters=3,linkage="average")model.fit(data)#訓(xùn)練模型auto_label=model.labels_#輸出模型結(jié)果

color=auto_labelfig=plt.figure(figsize=(5,3))plt.scatter(data[:,0],data[:,1],c=color)plt.title("blobs聚類結(jié)果可視化")blobs聚類結(jié)果可視化：12.2.2層次聚類例12-16層次聚類實現(xiàn)data=data_moonsfromsklearn.clusterimportAgglomerativeClusteringmodel=AgglomerativeClustering(n_clusters=3,linkage="average")model.fit(data)#訓(xùn)練模型auto_label=model.labels_#輸出模型結(jié)果

color=auto_labelfig=plt.figure(figsize=(5,3))plt.scatter(data[:,0],data[:,1],c=color)plt.title("moons聚類結(jié)果可視化")moons聚類結(jié)果可視化：12.2.3帶噪聲的基于密度的聚類方法帶噪聲的基于密度的聚類方法（DBSCAN，Density-BasedSpatialClusteringofApplicationswithNoise）主要思想是把樣本空間中不同的高密度區(qū)域劃分為不同簇。對于一個樣本點，如果在它的半徑為??的超球體（鄰域）內(nèi)的樣本點個數(shù)大于Nmin，則認為這個樣本點在一個高密度區(qū)域內(nèi)，稱這個點為核心對象。對于兩個都處在高密度區(qū)域的樣本點，如果他們之間的距離足夠近（即互相在對方的鄰域內(nèi)），則認為它們同屬于一個簇。12.2.3帶噪聲的基于密度的聚類方法DBSCAN的具體算法：1.從一個點開始，對其半徑為??的鄰域內(nèi)的點賦予同一個簇標記，并尋找鄰域內(nèi)的其他核心對象；2.對于找到的核心對象，重復(fù)步驟1；3.重復(fù)上述過程直到無法找到新的高密度點為止，認為一個簇被完整找出；4.從未被訪問過的點開始，尋找下一個簇，最終沒有出現(xiàn)在任何簇內(nèi)的點被標記為孤立點。12.2.3帶噪聲的基于密度的聚類方法DBSCAN主要參數(shù)說明：DBSCAN(eps=0.5,#設(shè)置??的大小min_samples=5,#設(shè)置高密度點??鄰域最小樣本數(shù)metric='euclidean',#距離計算方法algorithm='auto',#最近鄰搜索算法參數(shù)，brute、KD_tree、ball_treeleaf_size=30,#最近鄰搜索算法參數(shù)，為使用KD樹或者球樹時，

停止建子樹的葉子節(jié)點數(shù)量的閾值p=None,#最近鄰距離度量參數(shù)，p=1為曼哈頓距離，p=2為歐式距離n_jobs=None,)12.2.3帶噪聲的基于密度的聚類方法例12-17DBSCAN聚類的實現(xiàn)：data=data_blobsfromsklearn.clusterimportDBSCANmodel=DBSCAN(eps=1.5,min_samples=4)model.fit(data)#訓(xùn)練模型auto_label=model.labels_#保存模型結(jié)果color=auto_labelfig=plt.figure(figsize=(5,3))plt.scatter(data[:,0],data[:,1],c=color)plt.title("blobsDBSCAN聚類結(jié)果可視化")blobsDBSCAN聚類結(jié)果可視化：12.2.3帶噪聲的基于密度的聚類方法例12-17DBSCAN聚類的實現(xiàn)：data=data_moonsfromsklearn.clusterimportDBSCANmodel=DBSCAN(eps=1.5,min_samples=4)model.fit(data)#訓(xùn)練模型auto_label=model.labels_#保存模型結(jié)果color=auto_labelfig=plt.figure(figsize=(5,3))plt.scatter(data[:,0],data[:,1],c=color)plt.title("moonsDBSCAN聚類結(jié)果可視化")moonsDBSCAN聚類結(jié)果可視化：12.2.4均值漂移聚類均值漂移聚類是假設(shè)簇的質(zhì)心在簇內(nèi)點最密集的地方，尋找質(zhì)心的方法是隨機選擇一個點(seed)，從這個點開始不斷的將這個點更新為這個點鄰域內(nèi)點的均值點，這樣，這個點就會不斷的向高密度區(qū)域移動，直至到達最密集處。12.2.4均值漂移聚類MeanShift聚類具體算法：1.初始從多個起始點(seed)開始的，如果幾個不同的起始點經(jīng)過移動最終聚集在一起，則認為他們找了同一個簇的質(zhì)心，將他們合并。通常不使用全部樣本點作為seed，而是根據(jù)窗寬bandwidth作為網(wǎng)格間隔，選擇起始點。選好簇質(zhì)心后，將樣本點分到最近的簇。2.在更新seed點的過程中，求均值時考慮臨近點與當前seed點的距離，使用高斯核函數(shù)進行加權(quán)平均，即距離越近的點權(quán)重越大。3.高斯核需要輸入一個參數(shù)bandwidth（窗寬），用來控制seed點鄰域范圍的大小。12.2.4均值漂移聚類Bandwidth參數(shù)可選，如果不輸入，則使用estimate_bandwidth函數(shù)來計算。默認是使用樣本兩兩之間距離的0.3分位數(shù)作為窗寬。Seeds參數(shù)同樣，若沒有設(shè)置且bin_seeding=True則使用get_bin_seeds函數(shù)來計算，默認使用bandwidth作為網(wǎng)格大小來選擇起始點。cluster_all為True時，孤立點會被分到最近的簇內(nèi)；若為False，則對孤立點標記為-1。MeanShift主要參數(shù)說明：MeanShift(bandwidth=None,#窗寬seeds=None,#初始點設(shè)置max_iter=300,#最大迭代次數(shù))12.2.4均值漂移聚類例12-18MeanShift聚類的實現(xiàn)：data=data_blobsfromsklearn.clusterimportMeanShiftmodel=MeanShift(bandwidth=2)model.fit(data)data_label=model.labels_#樣本的標簽color=data_labelfig=plt.figure(figsize=(5,3))plt.scatter(data[:,0],data[:,1],c=color)plt.title("blobsMeanShift聚類結(jié)果可視化")blobsMeanShift聚類結(jié)果可視化：12.2.4均值漂移聚類例12-18MeanShift聚類的實現(xiàn)：data=data_moonsfromsklearn.clusterimportMeanShiftmodel=MeanShift(bandwidth=2)model.fit(data)data_label=model.labels_#樣本的標簽color=data_labelfig=plt.figure(figsize=(5,3))plt.scatter(data[:,0],data[:,1],c=color)plt.title("moonsMeanShift聚類結(jié)果可視化")moonsMeanShift聚類結(jié)果可視化：12.2.5譜聚類譜聚類是一種基于圖論的聚類方法，將所有的數(shù)據(jù)看成空間中的點，這些點之間可以用邊連接起來，距離較遠的點之間邊的權(quán)重低，距離較近的點間邊的權(quán)重高，然后對原圖進行切圖，使得不同子圖間邊的權(quán)重之和盡可能低，子圖內(nèi)邊的權(quán)重之和盡可能高，迭代的刪除最長的邊，從而達到聚類的目的。譜聚類可以理解為將高維空間的數(shù)據(jù)映射到低維，然后在低維空間用其他聚類算法（如KMeans）進行聚類。12.2.5譜聚類譜聚類算法：輸入：n個樣本點

X=x1,x2,…,xn?和聚類簇的數(shù)目k；輸出：聚類簇C1,C2,…,Ck1.

使用下面公式計算

的相似度矩陣W；

W為sij?組成的相似度矩陣。2.使用下面公式計算度矩陣D；即相似度矩陣W的每一行元素之和。D為di?組成的

對角矩陣。

12.2.5譜聚類3.計算拉普拉斯矩陣L=D-W?；

4.計算L的特征值，將特征值從小到大排序，取前k個特征值，并計算前k個特征值的特征向量u1,u2,…,uk?；

5.將上面的k個列向量組成矩陣U={u1,u2,…,uk}??；6.令yi∈Rk?是第i行的向量，其中i=1,2,…,n?；7.使用k-means等算法將新樣本點Y=y1,y2,…,yn?聚類成簇C1,C2,…,Ck?；8.輸出簇C1,C2,…,Ck。

12.2.5譜聚類SpectralClustering常用參數(shù)說明：SpectralClustering(n_clusters=8,#簇數(shù)eigen_solver=None,#特征值分解策略n_components=None,#用于譜嵌入的特征向量數(shù)random_state=None,n_init=10,#使用不同的質(zhì)心種子運行的次數(shù)gamma=1.0,#rbf、poly、sigmoid、laplacian和chi2內(nèi)核的內(nèi)核系數(shù)affinity='rbf',#構(gòu)建相似度矩陣的算法n_neighbors=10,#使用的鄰居數(shù)量

eigen_tol=0.0,#拉普拉斯矩陣特征分解的停止標準assign_labels='kmeans',#在嵌入空間中分配標簽的策略degree=3,#多項式核的度數(shù)coef0=1,#多項式和sigmoid內(nèi)核的零系數(shù)kernel_params=None,#內(nèi)核參數(shù)n_jobs=None,#并行作業(yè)數(shù)verbose=False,#輸出詳細模式)12.2.5譜聚類例12-19SpectralClustering聚類的實現(xiàn)：data=data_blobsfromsklearn.clusterimportSpectralClusteringmodel=SpectralClustering(n_clusters=3,assign_labels='discretize')model.fit(data)data_label=model.labels_color=data_labelfig=plt.figure(figsize=(5,3))plt.scatter(data[:,0],data[:,1],c=color)plt.title("blobs譜聚類聚類結(jié)果可視化")moonsMeanShift聚類結(jié)果可視化：12.2.5譜聚類例12-19SpectralClustering聚類的實現(xiàn)：data=data_moonsfromsklearn.clusterimportSpectralClusteringmodel=SpectralClustering(n_clusters=2,assign_labels='cluster_qr')model.fit(data)data_label=model.labels_color=data_labelfig=plt.figure(figsize=(5,3))plt.scatter(data[:,0],data[:,1],c=color)plt.title("moons譜聚類聚類結(jié)果可視化")moons譜聚類聚類結(jié)果可視化：目錄樣本距離計算常用聚類方法聚類模型評價輪廓系數(shù)蘭德指數(shù)案例：汽車車型聚類12.3.1輪廓系數(shù)輪廓系數(shù)是最常用于評價聚類效果的指標之一，輪廓系數(shù)結(jié)合了聚類的類內(nèi)凝聚度（Cohesion）和類間分離度（Separation），用于評估聚類的效果。該值處于-1~1之間，值越大，表示聚類效果越好。對于每個樣本點i，計算點i與其同一個簇內(nèi)的所有其他元素距離的平均值，記作a(i)，用于量化簇內(nèi)的凝聚度。選取i外的一個簇B，計算i與B中所有點的平均距離，遍歷所有其他簇，找到最近的這個平均距離,記作B(i)，即為i的鄰居類，用于量化簇之間分離度。12.3.1輪廓系數(shù)對于樣本點i，輪廓系數(shù)：計算所有i的輪廓系數(shù)，求出平均值即為當前聚類的整體輪廓系數(shù)，度量數(shù)據(jù)聚類的緊密程度。若s(i)小于0，說明i與其簇內(nèi)元素的平均距離小于最近的其他簇，表示聚類效果不好。如果a(i)趨于0，或者B(i)足夠大，即a(i)<<B(i)，那么s(i)趨近與1，說明聚類效果比較好。sklearn.metrics

中使用silhouette_score實現(xiàn)輪廓系數(shù)的計算。輸入?yún)?shù)為數(shù)據(jù)集與模型生成的聚類標簽。12.3.2蘭德系數(shù)例12-20輪廓系數(shù)對譜聚類結(jié)果評價：data=data_moonsfromsklearn.clusterimportSpectralClusteringmodel=SpectralClustering(n_clusters=2,assign_labels='cluster_qr')model.fit(data)data_label=model.labels_fromsklearn.metricsimportsilhouette_scoresilhouette_score(data,model.labels_)輸出輪廓系數(shù)為：0.4901910327755411輪廓系數(shù)在未知類別信息時可以很好的評價聚類的效果，在類別信息已知的情況下可以采用蘭德指數(shù)（randindex）評價聚類結(jié)果。給定真實類別信息C和聚類結(jié)果K：RI=(a+b)/(a+b+c+d)。其中：a：表示在C和K中都為同一類的樣本對的數(shù)量；b：表示在C和K中都屬于不同類的樣本對的數(shù)量；c：表示在C中屬于同一類，在K中屬于不同類的樣本對的數(shù)量；d：表示在C中屬于不同類，在K中屬于同一類的樣本對的數(shù)量。取值為[0,1]，越大聚類結(jié)果與真實情況越接近。12.3.2蘭德系數(shù)12.3.2蘭德系數(shù)蘭德指數(shù)的缺點：在聚類結(jié)果隨機產(chǎn)生的情況下，不能保證系數(shù)接近于0。因而對蘭德指數(shù)進行了調(diào)整，通常采用調(diào)整蘭德指數(shù)來評價。調(diào)整蘭德指數(shù)（adjustedrandindex）：ARI取值范圍為[-1,1]，負數(shù)表示結(jié)果不好，越接近于1結(jié)果越好。sklearn.metrics.cluster

中

adjusted_rand_score計算調(diào)整蘭德指數(shù)。adjusted_rand_score的參數(shù)為真實標簽和預(yù)測標簽。12.3.2蘭德系數(shù)例12-21調(diào)整蘭德指數(shù)對譜聚類結(jié)果的評價：data=data_moonsfromsklearn.clusterimportSpectralClusteringmodel=SpectralClustering(n_clusters=2,assign_labels='cluster_qr')model.fit(data)data_label=model.labels_fromsklearn.metrics.clusterimportadjusted_rand_scoreadjusted_rand_score(label_moons,data_label)#計算調(diào)整蘭德指數(shù)，需要有真實的類別標簽調(diào)整蘭德指數(shù)為：0.2738494132868083目錄樣本距離計算常用聚類方法聚類模型評價案例：汽車車型聚類目標數(shù)據(jù)集介紹實現(xiàn)代碼12.4.1目標根據(jù)汽車的排量、馬力、重量等特征對不同汽車車型進行聚類。12.4.2數(shù)據(jù)集介紹數(shù)據(jù)集介紹：數(shù)據(jù)集來源

：UCI機器學(xué)習(xí)存儲庫。數(shù)據(jù)集名稱：AutoMPGDataSet數(shù)據(jù)涉及城市循環(huán)燃料消耗，以每加侖英里數(shù)為單位。樣本數(shù)：398屬性數(shù)：9個屬性信息：mpg：油耗，連續(xù)cylinders：氣缸數(shù)，離散displacement：排量，連續(xù)horsepower：馬力，連續(xù)weight：重量，連續(xù)acceleration：加速性能，連續(xù)modelyear：年份，離散origin：產(chǎn)地，離散carname：車名，字符串（每個實例唯一）注意：馬力有6個缺失值12.4.3實現(xiàn)代碼1.導(dǎo)入必要的包fromsklearn.clusterimportKMeansfromsklearn.clusterimportAgglomerativeClusteringfromsklearn.clusterimportDBSCANfromsklearn.clusterimportMeanShiftfromsklearn.clusterimportSpectralClusteringfromsklearnimportmetricsimportnumpyasnpimportpandasaspdimportmatplotlib.pyplotaspltimportwarningswarnings.filterwarnings("ignore")2.讀入數(shù)據(jù)data=pd.read_csv("d:/datasets/auto-mpg.csv")3.數(shù)據(jù)探索data.head()#輸出前五行數(shù)據(jù)集前5行：12.4.3實現(xiàn)代碼3.數(shù)據(jù)探索()#查看數(shù)據(jù)類型及缺失值情況：12.4.3實現(xiàn)代碼3.數(shù)據(jù)探索data.describe(include="all")#查看各屬性的統(tǒng)計特征12.4.3實現(xiàn)代碼4.數(shù)據(jù)預(yù)處理data=data.drop("carname",axis=1)#刪除“carname”特征data[data["horsepower"]=="?"]#輸出"horsepower"=="?"的樣本"horsepower"=="?"的樣本：12.4.3實現(xiàn)代碼4.數(shù)據(jù)預(yù)處理#刪除帶“？”的不完整樣本data_auto=data[data["horsepower"]!="?"]#獲取不含？的樣本data_auto.horsepower=data_auto.horsepower.astype("int64")#轉(zhuǎn)換data_auto.horsepower為int64類型#標準化model_sc=StandardScaler()model_sc.fit(data_auto)data_auto_sc=model_sc.transform(data_auto)12.4.3實現(xiàn)代碼5.建模（1）Kmeansmodel_km=KMeans(n_clusters=2,random_state=10)model_km.fit(data_auto_sc)#聚類auto_label=model_km.labels_#獲取聚類標簽12.4.3實現(xiàn)代碼5.建模（2）探尋最優(yōu)的K值fromsklearnimportmetricsprint("n_clusters","","silhouette_score")forkin[2,3,4,5,6,7,8,9]:model_km=KMeans(n_clusters=k,random_state=10).fit(data_auto_sc)auto_label=model_km.labels_auto_cluster=model_km.cluster_centers_print(k,"",round(metrics.silhouette_score(data_auto_sc,auto_label),4))12.4.3實現(xiàn)代碼輸出如下，可見當n=2時，輪廓系數(shù)最大。12.4.3實現(xiàn)代碼（3）MeanShiftfromsklearn.clusterimportMeanShiftmodel_mn=MeanShift(bandwidth=2).fit(data_auto_sc)auto_label=model_mn.labels_auto_cluster=model_mn.cluster_centers_bandwidth_grid=np.arange(1,3,0.5)cluster_number=[]slt_score=[]foriinbandwidth_grid:model=MeanShift(bandwidth=i).fit(data_auto_sc)cluster_number.append(len(np.unique(model.labels_)))slt_score.append(metrics.silhouette_score(data_auto_sc,model.labels_))12.4.3實現(xiàn)代碼fromprettytableimportPrettyTablex=PrettyTable(["窗寬","蔟的個數(shù)","輪廓系數(shù)"])#實例化表格，定義表頭fori,j,kinzip(bandwidth_grid,cluster_number,slt_score):x.add_row([i,j,k])#增加一行print(x)#輸出"窗寬"、"蔟的個數(shù)"、"輪廓系數(shù)"關(guān)系表格輸出"窗寬"、"蔟的個數(shù)"、"輪廓系數(shù)"關(guān)系：12.4.3實現(xiàn)代碼（4）AgglomerativeClusteringmodel=AgglomerativeClustering(n_clusters=3,linkage="average").fit(data_auto_sc)auto_label=model.labels_lbs=pd.Series(auto_label).value_counts()#plt.bar(x=lbs.index,height=lbs)lbs.plot(kind="