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

7-1簡(jiǎn)述聚類算法的基本思想。

聚類是一種典型的無(wú)監(jiān)督學(xué)習(xí)方法，按照某個(gè)特定準(zhǔn)則將一組對(duì)象分成為若干個(gè)簇，使

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

能大。也就是說(shuō),聚類的目標(biāo)是使相似的對(duì)象盡可能地接近，而不相似的對(duì)象盡可能地遠(yuǎn)離。

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

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

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

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

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

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

值表示了一個(gè)數(shù)據(jù)點(diǎn)與每個(gè)簇的聯(lián)系程度，其值介于。和1之間?？偟膩?lái)說(shuō)，硬聚類更適合

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

7-3簡(jiǎn)述k均值聚類算法的過(guò)程。

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

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

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

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

量方法來(lái)計(jì)算每個(gè)數(shù)據(jù)點(diǎn)與每個(gè)質(zhì)心之間的距離，然后將該數(shù)據(jù)點(diǎn)分配到距離最近的質(zhì)心所

在的簇中。對(duì)于步驟3中的更新質(zhì)心過(guò)程，則是將每個(gè)簇內(nèi)的所有數(shù)據(jù)點(diǎn)的坐標(biāo)取平均值，

得到新的質(zhì)心位置。

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

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

會(huì)導(dǎo)致最終聚類結(jié)果不同。因此，為了得到更好的聚類結(jié)果，需要采用一些有效的方法來(lái)選

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

的值過(guò)大或過(guò)小，都可能會(huì)導(dǎo)致聚類結(jié)果不理想。因此，需要采用一些有效的方法來(lái)確定最

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

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

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

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

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

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

當(dāng)，也可能會(huì)影響聚類結(jié)果。

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

進(jìn)行實(shí)驗(yàn)比較。

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

首先導(dǎo)入相關(guān)庫(kù)

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]]）

設(shè)置不同的k值和初始簇中心，并用KMeans進(jìn)行聚類：____________________________

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設(shè)計(jì)一個(gè)能夠自動(dòng)確定k值的k均值算法，并基于表7-1中的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。

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

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

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

再生導(dǎo)入相關(guān)庫(kù)

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)

訓(xùn)練KMeans模型，/記錄SSE值

sse_list=[]

forkinkrange:

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

sse_list.append(kmeans.inertia_)

一蔡制S能與k殖的關(guān)系圖

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

plt.xlabelCk1)

plt.ylabel(SSE)

plt.title(*TheElbowMethod*)

plt.show()

得到一個(gè)SSE與k值的關(guān)系圖，通過(guò)觀察得出最優(yōu)的k值為2,接下來(lái)，再次iijfKMeans

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

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比較分析凝聚型層次聚類算法和分裂型層次聚類算法的異同點(diǎn)。

相同點(diǎn)：都是基于距離或相似度進(jìn)行聚類的方法；都可以得到層次化的聚類結(jié)果；都可

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

不同點(diǎn)：凝聚型層次聚類算法是自下而上的聚類過(guò)程，從每個(gè)樣本開始，逐步合并相鄰

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

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

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

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

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

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

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

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

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

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

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

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

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

首先導(dǎo)入相關(guān)庫(kù)

fromskleam.clusterimportAgglomerativeClustering

importnumpyasnp

構(gòu)造樣本特國(guó)矩陣

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)

輸出每個(gè)樣本所屬的簇

print(clustering.labels_)

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

關(guān)于分裂型層次聚類算法的示例代碼。

#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