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

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之間?？偟膩碚f，硬聚類更適合

于明確的數(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中的更新質心過程，則是將每個簇內的所有數(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.array([[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“，”d”，”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_Iist:

sumdissm+=dissimilarity_matrix[ele][i]

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

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_value>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

index=0

forelementlistinclusterlist:

foriinelementlist:

forjinelementlist:

ifdissimilarity_matrix[i][j]>max_diameter_cluster_value:

max_diameter_cluster_value=dissimilaritymatrix[i][j]

max_diameter_cluster_index=index

index+=1

if(max_diameter_cluster_value<=0):

return-1

returnmax_diameter_cluster_index

current_clusters=([allelements])

level=1

index=0

while(index!=-l):

print(level,current_clusters)

(a_clstr,b_clstr)=split(current_clusters[index])

delcurrent_clusters[index]

current_clusters.append(a_clstr)

current_clusters.append(b_clstr)

index=max_diameter(current_clusters)

level+=1

print(level,currentclusters)

8-1簡述Apriori算法。

Apriori算法是一種基于頻繁項集的挖掘算法，用于在大規(guī)模數(shù)據(jù)集中發(fā)現(xiàn)頻繁出現(xiàn)的

模式。該算法的核心思想是利用Apriori原理，即如果一個項集是頻繁的，則其所有子集也

必須是頻繁的。因此，該算法通過迭代增加項集的大小來發(fā)現(xiàn)頻繁項集，直到無法找到更多

的頻繁項集為止。Apriori算法的優(yōu)點是簡單易懂，易于實現(xiàn)，并且能夠處理大規(guī)模數(shù)據(jù)集。

其缺點是需要多次掃描數(shù)據(jù)集，計算頻繁項集，效率較低。針對這個問題，還有一些改進算

法，如FP-growth算法等。

8-2簡述FP增長算法。

FP增長算法是一種用于發(fā)現(xiàn)頻繁項集的數(shù)據(jù)挖掘算法，與Apriori算法相比，它能夠更

快地發(fā)現(xiàn)頻繁項集，并且不需要生成候選項集。FP增長算法的優(yōu)點是在處理大規(guī)模數(shù)據(jù)集

時具有較高的效率，同時不需要生成候選項集，減少了空間和時間的開銷

8-3對比分析Apriori算法和FP增長算法。

結合教材習題8-1和8-2的答案。

8-4利用FP增長算法找出表8-1中的頻繁項集。設最小支持度為0.5。

｛A｝、｛B｝、｛R｝、｛A,B｝、｛A,R｝、｛B,R｝、｛A,B,R｝

8-5利用Apriori算法找出表8-10中的頻繁項集。設最小支持度為0.5。

1、計算單個項的支持度：

天氣=晴:2/6=0.333

天氣=陰：2/6=0.333

天氣=雨：2/6=0,333

溫度=熱:3/6=0.5

溫度=中：1/6=0.167

溫度=冷:2/6=0.333

風速=強:2/6=0,333

風速=弱:4/6=0.667

活動=進行:4/6=0.667

活動=取消：2/6=0.333

2、計算2項集的支持度：

｛天氣=晴，溫度=熱｝:2/6=0.333

｛天氣=晴，風速=弱｝:2/6=0.333

｛天氣=晴，活動=取消）：2/6=0.333

｛溫度=熱，風速=弱｝:3/6=0.5

｛溫度=熱，活動=進行｝:3/6=0.5

｛風速=弱,活動=進行｝:4/6=0.667

3、篩選出頻繁項集：

｛溫度=熱｝:0.5>=0.5

｛風速=弱｝：0.667>=0.5

｛活動=進行｝：0.667>=0.5

｛天氣=晴，溫度=熱｝:0.333<0.5

｛天氣=晴，風速=弱｝:0.333<0.5

｛天氣=晴，活動=取消｝:0.333<0.5

｛溫度=熱，風速=弱｝:0.5>=0.5

｛溫度=熱，活動=進行｝:0.5>=0.5

｛風速=弱，活動=進行｝:0.667>=0.5

8-6利用Apriori算法和FP增長算法找出表8-12中的頻繁項集。設最小支持度為0.5o