谱聚类算法探究：k与的影响

本资源主要涉及的是谱聚类算法在数据划分问题上的应用，具体是针对一个由两个半月形分布产生的200个数据点进行聚类。问题要求编写一个实现"Normalized Spectral Clustering - Algorithm 3 (Ng算法)"的程序，并探讨不同参数设置（即σ和k值）对聚类结果的影响。提供的标签包括“聚类”、“算法”和“矩阵”，暗示了这是数据挖掘或机器学习领域的作业内容。 在谱聚类中，亲和性矩阵W的计算基于k-近邻方法，每个数据点与其k个最近邻形成边，且矩阵需对称。矩阵的构建是通过计算样本点间的距离，然后依据给定的亲和度公式生成。σ用于控制距离的平滑程度，通常是一个正态分布的标准差。已知前100个点属于一个聚类，后100个点属于另一个聚类，以此评估聚类精度Accu，该指标衡量的是正确分类的样本点数量占总样本数的比例。 在实现上，数据加载函数用于从txt文件读取实验数据，图构造函数负责构建数据图和亲和性矩阵，而谱聚类函数则根据输入的亲和性矩阵进行计算，通过Laplacian矩阵找到前c个最小特征值对应的特征向量，这些向量被用作新的特征空间，然后用K-means算法进行最终的聚类。 实验结果显示，当σ值适当且k值较小（例如σ=1，k=10）时，可以达到完全正确的聚类结果。随着k值增大，聚类精度Accu降低，因为大k值可能导致两个聚类间的样本点建立连接，使得图不再满足二部图的条件，分离两个聚类变得更加困难。同时，当固定k值时，增大σ值会降低聚类精度，原因可能是σ过大强化了原本应该属于不同聚类的点之间的联系。 在分析过程中，还发现当σ值增大时，分类结果的正确性并不受影响，这表明在这种情况下，σ的选择对聚类结果不敏感。然而，当固定σ时，增大k值会导致聚类精度下降，这一现象与固定k时观察到的效果一致。 此作业强调了谱聚类中参数选择的重要性，σ和k值的适当调整对获得准确聚类至关重要。在实践中，应根据数据的特性以及对聚类结果的要求，通过实验探索最佳的参数组合。