物联网与数据挖掘 习题及答案 第7、8章

7-1简述聚类算法的基本思想。

聚类是一种典型的无监督学习方法，按照某个特定准则将一组对象分成为若干个簇，使

得在同一个簇中的对象之间的相似性尽可能大，而不在同一个簇中的对象之间的差异性尽可

能大。也就是说,聚类的目标是使相似的对象尽可能地接近，而不相似的对象尽可能地远离。

7-2比较分析硬聚类和软聚类。

硬聚类和软聚类都是聚类分析中常用的方法,它们的主要区别在于对数据点的归属度处

理方式。硬聚类算法将每个数据点划分到唯一的簇中，即每个数据点只能属于一个确定的类

别。这种聚类方法通常使用距离测量或相似性度量来计算数据点之间的相似性，并根据相似

性将它们分配到不同的簇中。硬聚类最常用的方法是K-means算法。与硬聚类不同，软聚类

允许数据点同时属于多个簇，并为每个数据点分配一个属于每个簇的隶属度值。这种隶属度

值表示了一个数据点与每个簇的联系程度，其值介于。和1之间。总的来说，硬聚类更适合

于明确的数据分类问题，而软聚类更适合于数据分类不明确或存在一定程度模糊的情况。

7-3简述k均值聚类算法的过程。

（1）首先选取K个初始质心，可以随机选择或根据数据的特点进行设置（2）将每个数

据点分配到距离其最近的质心所在的簇中；（3）重新计算每个簇的质心。

重复步骤（2）和（3）,直到达到收敛条件，即质心不再发生变化或达到了预设的最大

迭代次数。具体地说，对于步骤2中的分配过程，可以采用欧氏距离或曼哈顿距离等距离度

量方法来计算每个数据点与每个质心之间的距离，然后将该数据点分配到距离最近的质心所

在的簇中。对于步骤3中的更新质心过程，则是将每个簇内的所有数据点的坐标取平均值，

得到新的质心位置。

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

（1）初始质心的选择：K均值算法对于初始质心的位置非常敏感，不同的初始质心可能

会导致最终聚类结果不同。因此，为了得到更好的聚类结果，需要采用一些有效的方法来选

择合适的初始质心。（2）簇的数量K的选择：簇的数量K直接影响到聚类的结果，如果K

的值过大或过小，都可能会导致聚类结果不理想。因此，需要采用一些有效的方法来确定最

佳的簇的数量K。（3）距离度量方法的选择：K均值算法通常使用欧氏距离或曼哈顿距离等

距离度量方法来计算数据点之间的相似性，但这种方法对于不同的数据集可能并不适用。因

此，在选择距离度量方法时，需要根据具体情况进行选择。（4）数据集的特征：K均值算法

假定所有数据点都可以被分配到某个簇中，因此在处理不规则形状的数据集时可能会出现问

题。另外，如果数据集中存在异常值或噪声，也会影响聚类结果。（5）算法的收敛条件：K

均值算法通常使用质心的移动距离和迭代次数来判断算法是否收敛，但如果这些条件设置不

当，也可能会影响聚类结果。

7-5试编程实现k均值算法，设置多组不同的k值、初始簇中心，并在表7-1中的数据集上

进行实验比较。

参阅代码实现：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中的数据进行实验。

自动确定k值的k均值算法通常被称为“肘部法则它的基本思想是通过绘制不同k值

下的聚类误差平方和(SSE)与k值的关系图，找到一个“肘部”的位置，即SSE开始急剧下

降的位置。这个位置的k值就是最优的聚类个数。

再生导入相关库

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值的关系图，通过观察得出最优的k值为2,接下来，再次iijfKMeans

模型，并设置聚娄个数为2进行聚类;训练最优的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比较分析凝聚型层次聚类算法和分裂型层次聚类算法的异同点。

相同点：都是基于距离或相似度进行聚类的方法；都可以得到层次化的聚类结果；都可

以灵活地选择聚类簇的数量。

不同点：凝聚型层次聚类算法是自下而上的聚类过程，从每个样本开始，逐步合并相邻

的簇，直到所有样本都被归为一类。分裂型层次聚类算法则是自上而下的聚类过程，从整个

数据集开始，逐渐将数据划分为更小的簇，直到每个簇只包含一个样本。在凝聚型层次聚类

算法中，先计算所有样本之间的距离，并将最近的两个样本合并成一个簇。然后，再计算新

簇与其他簇之间的距离，并选择最近的两个簇进行合并。在分裂型层次聚类算法中，则是先

将整个数据集看作一个簇，然后逐步将其划分为更小的簇，直到每个簇只包含一个样本；凝

聚型层次聚类算法的时间复杂度一般为0(23),其中n是样本数量。分裂型层次聚类算法

的时间复杂度则一般为0(22logn)或0(23),具体取决于实现方式和数据特征；在凝聚

型层次聚类算法中，由于每个样本最终只能被分配到一个簇中，因此该算法不适合处理具有

噪声或离群点的数据。而在分裂型层次聚类算法中，可通过剪枝等方式来处理噪声或离群点。

7-8利用分裂型层次聚类算法对表7-1中的数据进行聚类。

可利用教材习题7-10中的算法得到一种可能的划分方式。

7-9试编程实现凝聚型层次聚类算法，并对表7-1中的数据进行聚类。

参阅代码实现：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试编程实现分裂型层次聚类算法，并对表7-1中的数据进行聚类。

关于分裂型层次聚类算法的示例代码。

#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算法是一种基于频繁项集的挖掘算法，用于在大规模数据集中发现频繁出现的

模式。该算法的核心思想是利用Apriori原理，即如果一个项集是频繁的，则其所有子集也

必须是频繁的。因此，该算法通过迭代增加项集的大小来发现频繁项集，直到无法找到更多

的频繁项集为止。Apriori算法的优点是简单易懂，易于实现，并且能够处理大规模数据集。

其缺点是需要多次扫描数据集，计算频繁项集，效率较低。针对这个问题，还有一些改进算

法，如FP-growth算法等。

8-2简述FP增长算法。

FP增长算法是一种用于发现频繁项集的数据挖掘算法，与Apriori算法相比，它能够更

快地发现频繁项集，并且不需要生成候选项集。FP增长算法的优点是在处理大规模数据集

时具有较高的效率，同时不需要生成候选项集，减少了空间和时间的开销

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