物聯(lián)網(wǎng)與數(shù)據(jù)挖掘習題答案 第7章 課后習題

7-1簡述聚類算法的基本思想。

聚類是一種典型的無監(jiān)督學習方法，按照某個特定準則將一組對象分成為若干個簇，使

得在同一個簇中的對象之間的相似性盡可能大，而不在同一個簇中的對象之間的差異性盡可

能大。也就是說,聚類的目標是使相似的對象盡可能地接近，而不相似的對象盡可能地遠離。

7-2比較分析硬聚類和軟聚類。

硬聚類和軟聚類都是聚類分析中常用的方法,它們的主要區(qū)別在于對數(shù)據(jù)點的歸屬度處

理方式。硬聚類算法將每個數(shù)據(jù)點劃分到唯一的簇中，即每個數(shù)據(jù)點只能屬于一個確定的類

別。這種聚類方法通常使用距離測量或相似性度量來計算數(shù)據(jù)點之間的相似性，并根據(jù)相似

性將它們分配到不同的簇中。硬聚類最常用的方法是K-means算法。與硬聚類不同，軟聚類

允許數(shù)據(jù)點同時屬于多個簇，并為每個數(shù)據(jù)點分配一個屬于每個簇的隸屬度值。這種隸屬度

值表示了一個數(shù)據(jù)點與每個簇的聯(lián)系程度，其值介于。和1之間。總的來說，硬聚類更適合

于明確的數(shù)據(jù)分類問題，而軟聚類更適合于數(shù)據(jù)分類不明確或存在一定程度模糊的情況。

7-3簡述k均值聚類算法的過程。

（1）首先選取K個初始質心，可以隨機選擇或根據(jù)數(shù)據(jù)的特點進行設置（2）將每個數(shù)

據(jù)點分配到距離其最近的質心所在的簇中；（3）重新計算每個簇的質心。

重復步驟（2）和（3）,直到達到收斂條件，即質心不再發(fā)生變化或達到了預設的最大

迭代次數(shù)。具體地說，對于步驟2中的分配過程，可以采用歐氏距離或曼哈頓距離等距離度

量方法來計算每個數(shù)據(jù)點與每個質心之間的距離，然后將該數(shù)據(jù)點分配到距離最近的質心所

在的簇中。對于步驟3中的更新質心過程，則是將每個簇內(nèi)的所有數(shù)據(jù)點的坐標取平均值，

得到新的質心位置。

7-4影響k均值算法性能的主要因素有哪些？

（1）初始質心的選擇：K均值算法對于初始質心的位置非常敏感，不同的初始質心可能

會導致最終聚類結果不同。因此，為了得到更好的聚類結果，需要采用一些有效的方法來選

擇合適的初始質心。（2）簇的數(shù)量K的選擇：簇的數(shù)量K直接影響到聚類的結果，如果K

的值過大或過小，都可能會導致聚類結果不理想。因此，需要采用一些有效的方法來確定最

佳的簇的數(shù)量K。（3）距離度量方法的選擇：K均值算法通常使用歐氏距離或曼哈頓距離等

距離度量方法來計算數(shù)據(jù)點之間的相似性，但這種方法對于不同的數(shù)據(jù)集可能并不適用。因

此，在選擇距離度量方法時，需要根據(jù)具體情況進行選擇。（4）數(shù)據(jù)集的特征：K均值算法

假定所有數(shù)據(jù)點都可以被分配到某個簇中，因此在處理不規(guī)則形狀的數(shù)據(jù)集時可能會出現(xiàn)問

題。另外，如果數(shù)據(jù)集中存在異常值或噪聲，也會影響聚類結果。（5）算法的收斂條件：K

均值算法通常使用質心的移動距離和迭代次數(shù)來判斷算法是否收斂，但如果這些條件設置不

當，也可能會影響聚類結果。

7-5試編程實現(xiàn)k均值算法，設置多組不同的k值、初始簇中心，并在表7-1中的數(shù)據(jù)集上

進行實驗比較。

參閱代碼實現(xiàn)：skleam.clusterimportKMeans

首先導入相關庫

importnumpyasnp

importmatplotlib.pyplotaspit

fromskleam.clusterimportKMeans

港義棗7?1中的樣本特彳或向量

X=np.array（[[l,1],[2,1],[1,2],[2,2],[4,3],[5,3],[4,4],[5,4]]）

設置不同的k值和初始簇中心，并用KMeans進行聚類：____________________________

kvalues=[2,3,4]

initcenters=[np.array([[l,1],[5,4]]),np.array([[l,1],[5,4],[4,3]]),np.array([[l,1],[5,4],

[4,3],[2,2]])]

foriinrange(len(k_vakies)):

forjinrange(len(init_centers[i])):

kmeans=KMeans(n_clusters=k_values[i],init=init_centers[i][j].reshape(-l,2),

random_state=0).fit(X)

labels=kmeans.labels_

plt.subplot(len(k_values),len(init_centers[i]),i*len(init_centers[i])4j+1)

plt.scatter(X[:,0],X[:,1],c=labels.astype(np.float))

plt.scatter(kmeans.cluster_centers_[:,0],kmeans.cluster_centers_[:,1],marker='x,,

s=200,linewidths=3,color=Ted')

plt.title(*k={},init_center={}*.fbrmat(k_values[i],init_centers[i][j]))

plt.show()

7-6設計一個能夠自動確定k值的k均值算法，并基于表7-1中的數(shù)據(jù)進行實驗。

自動確定k值的k均值算法通常被稱為“肘部法則它的基本思想是通過繪制不同k值

下的聚類誤差平方和(SSE)與k值的關系圖，找到一個“肘部”的位置，即SSE開始急劇下

降的位置。這個位置的k值就是最優(yōu)的聚類個數(shù)。

再生導入相關庫

importnumpyasnp

importmatplotlib.pyplotaspit

fromsklearn.clusterimportKMeans

定義樣本特征向量

x=np.anay([[l,1],[2,1],[1,2],[2,2],[4,3],[5,3],[4,4],[5,4]])

,足義嘗試的k值范圍

krange=range(1,7)

訓練KMeans模型，/記錄SSE值

sse_list=[]

forkinkrange:

kmeans=KMeans(n_clusters=k,random_state=0).fit(X)

sse_list.append(kmeans.inertia_)

一蔡制S能與k殖的關系圖

plt.plot(k_range,sse_list,'bx-*)

plt.xlabelCk1)

plt.ylabel(SSE)

plt.title(*TheElbowMethod*)

plt.show()

得到一個SSE與k值的關系圖，通過觀察得出最優(yōu)的k值為2,接下來，再次iijfKMeans

模型，并設置聚婁個數(shù)為2進行聚類;訓練最優(yōu)的KMeans模型T輸出聚類結果

kmeans=KMeans(n_clusters=2,random_state=0).fit(X)

labels=kmeans.labels_

plt.scatter(X[:,0],X[:,1],c=labels.astype(np.float))

plt.scatter(kmeans.clustercenters[:,0],kmeans.clustercenters[:,1],marker='x'，s=200,

linewidths=3,color='red')

plt.title('ClusteringResultwithk=2')

plt.show()

7-7比較分析凝聚型層次聚類算法和分裂型層次聚類算法的異同點。

相同點：都是基于距離或相似度進行聚類的方法；都可以得到層次化的聚類結果；都可

以靈活地選擇聚類簇的數(shù)量。

不同點：凝聚型層次聚類算法是自下而上的聚類過程，從每個樣本開始，逐步合并相鄰

的簇，直到所有樣本都被歸為一類。分裂型層次聚類算法則是自上而下的聚類過程，從整個

數(shù)據(jù)集開始，逐漸將數(shù)據(jù)劃分為更小的簇，直到每個簇只包含一個樣本。在凝聚型層次聚類

算法中，先計算所有樣本之間的距離，并將最近的兩個樣本合并成一個簇。然后，再計算新

簇與其他簇之間的距離，并選擇最近的兩個簇進行合并。在分裂型層次聚類算法中，則是先

將整個數(shù)據(jù)集看作一個簇，然后逐步將其劃分為更小的簇，直到每個簇只包含一個樣本；凝

聚型層次聚類算法的時間復雜度一般為0(23),其中n是樣本數(shù)量。分裂型層次聚類算法

的時間復雜度則一般為0(22logn)或0(23),具體取決于實現(xiàn)方式和數(shù)據(jù)特征；在凝聚

型層次聚類算法中，由于每個樣本最終只能被分配到一個簇中，因此該算法不適合處理具有

噪聲或離群點的數(shù)據(jù)。而在分裂型層次聚類算法中，可通過剪枝等方式來處理噪聲或離群點。

7-8利用分裂型層次聚類算法對表7-1中的數(shù)據(jù)進行聚類。

可利用教材習題7-10中的算法得到一種可能的劃分方式。

7-9試編程實現(xiàn)凝聚型層次聚類算法，并對表7-1中的數(shù)據(jù)進行聚類。

參閱代碼實現(xiàn)：skleam.clusterimportAgglomerativeClustering

首先導入相關庫

fromskleam.clusterimportAgglomerativeClustering

importnumpyasnp

構造樣本特國矩陣

X=np.array([[l,l],[2,1],[1,2],[2,2],

[4,3],[5,3],[4,4],[5,4]])

使用分裂型層次聚類算闞行聚美

clustering=AgglomerativeClustering(n_clusters=2)

clustering.fit(X)

輸出每個樣本所屬的簇

print(clustering.labels_)

7-10試編程實現(xiàn)分裂型層次聚類算法，并對表7-1中的數(shù)據(jù)進行聚類。

關于分裂型層次聚類算法的示例代碼。

#coding:utf-8

importnumpyasnp

importpandasaspd

fromscipy.spatialimportdistance_matrix

numclusters=0

data=np.array([[l,1],[2,1],[1,2],[2,2],[4,3],[5,3],[4,4],[5,4]])

mat=distancematrix(data,data)#(Euclidean)distancebetweentwosamples

all_elements=[“a1"b“Jc“Jd“，”e”，'Jg“Jh”]

dissimilarity_matrix=pd.DataFrame(mat,index=all_elements,columns=all_elements)

defavg_dissim_within_group_eleinent(ele,elementlist):

maxdiameter=-np.inf

sumdissm=0

fbriinelement_list:

sumdissm+=dissimilarity_matrix[ele][i]

if(dissimilarity_matrix[ele][i]>maxdiameter):

maxdiameter=dissimilarity_matrix[ele][i]

if(len(element_list)>l):

avg=sum_dissm/(len(element_list)-1)

else:

avg=0

returnavg

defavg_dissim_across_group_element(ele,main_list,splinterlist):

iflen(splinterlist)=0:

return0

sumdissm=0

fbrjinsplinter_list:

sumdissm=sumdissm+dissimilarity_matrix[ele][j]

avg=sum_dissm/(len(splinter_list))

returnavg

defsplinter(main_list,splintergroup):

most_dissm_object_value=-np.inf

most_dissm_objectindex=None

fbreleinmainlist:

x=avg_dissim_within_group_element(ele,mainlist)

y=avg_dissim_across_group_element(ele,main_list,splintergroup)

diff=x-y

ifdiff>most_dissm_object_value:

most_dissm_object_value=diff

most_dissm_object_index=ele

if(most_dissm_object_vahie>0):

return(most_dissm_object_index,1)

else:

return(-1,-1)

defsplit(element_list):

mainlist=element_list

splintergroup=[]

(most_dissm_object_index,flag)=splinter(main_list,splintergroup)

while(flag>0):

main_list.remove(most_dissm_object_index)

splinter_group.append(most_dissm_object_index)

(most_dissm_object_index,flag)=splinter(element_list,splintergroup)

return(mainlist,splintergroup)

defmax_diameter(cluster_list):

max_diameter_cluster_index=None

max_diameter_cluster_value=-np.inf