近似谱聚类算法描述

《近似谱聚类算法描述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、二、近似谱聚类算法描述本节论文阐述基于相似矩阵稀疏化方法稀疏化后离群点的优化处理，并将该处理步骤应用于谱聚类算法中。基于上述分析近似谱聚类算法整体流程总结描述如表3.2所示。表3.2近似谱聚类算法（ASCA）算法：近似谱聚类算法（ASCA）输入：数据点，待聚类数目 输出：聚类 1.使用公式，（其中，是的个最近邻按距离排序后第个邻居，同理，），构建相似矩阵；2.使用稀疏化矩阵获得半正定矩阵，找出矩阵对称位置不一致的相似度，并将对称元素设置为0，调整为对称半正定矩阵；3.使用优化公式对矩阵进行离群点调优；4.计算对称半正

2、定拉普拉斯矩阵；5.计算的特征向量分解，找出第k个最小非零特征特征量，并按列排列k个特征向量构建特征向量矩阵；6.计算标准化矩阵（）；7.使用粗糙集模型选择k-means初始化聚类中心位置并对矩阵进行k-means聚类，把其聚类成k组（）。 基于近似谱聚类算法整体步骤描述，为进行近似谱聚类算法Matlab辅助实验铺垫，绘制近似谱聚类算法流程示意图如图3.1所示。Matlab辅助实验主要是将示意图3.1中的所示的算法与正交化Nyström低阶子矩阵抽样近似相似矩阵谱聚类算法（ONSP:Orthogonalization

3、NyströmSpectralClustering）和最近邻稀疏化近似相似矩阵谱聚类算法（tNNSC:SpectralClustering）进行对比，并验证其聚类效果。图3.1近似谱聚类算法流程示意图三、近似谱聚类算法时间复杂度分析现对基于相似矩阵稀疏化方法离群点优化的近似谱聚类算法时间复杂度简单分析，步骤1：使用高斯函数公式构建相似矩阵的时间复杂度是，其中表示数据点数目、表示数据维数，计算数据点和之间的相似度的时间复杂度是，则计算整个数据集的时间复杂度是；步骤2：使用稀疏化矩阵获得半正定矩阵并调整为对称半正定矩阵借

4、助于最大堆，其时间复杂度是，其中是最近邻数；步骤3：优化离群点步骤是非确定性多项式困难问题NP-hard（NondeterministicPloynomialHard）问题，其时间复杂度随近似相似度矩阵维数按指数增长；步骤4与步骤5：计算对称半正定拉普拉斯矩阵并找出k个最小非零特征值的特征向量的时间复杂度在论文第二章第二节中已经详细分析过，即；步骤6：计算标准化矩阵的时间复杂度是；步骤7：执行k-means聚类时间复杂度是：，其中表示k-means聚类过程迭代的次数，指待聚类数目。第三节近似谱聚类算法实验分析一、近似

5、谱聚类算法辅助实验（1）Matlab辅助实验环境描述为验证表3.2所示近似谱聚类算法与正交化Nyström低阶子矩阵抽样近似相似矩阵谱聚类算法和最近邻稀疏化近似相似矩阵谱聚类算法的性能，鉴于HadoopMapReduce并行实验对比的工作量过大，故仅设计基于Matlab的对比性实验。Matlab辅助实验环境：近似谱聚类算法（ASC）的Matlab辅助性验证以及其与正交化Nyström低阶子矩阵抽样近似相似矩阵谱聚类算法和最近邻稀疏化近似相似矩阵谱聚类算法的对比。实验所使用的Matlab版本是：MatlabR2011a

6、，运行Matlab的服务器是：WindowsServer2008R2Datacenter，系统处理器：Intel(R)CPUE5-2600@2.30GHz（2处理器），其内存（RAM）32.0GB，系统类型：64位操作系统。（2）Matlab辅助实验数据集描述辅助性实验使用的经典文本分类数据集是路透社语料库卷I：RCV1（ReutersCorpusVolumeI）[64]，其具体描述见表3.3所示。表3.3实验数据集描述数据集类别数样本数特征维数数据集规模是否归一化来自领域RCV11031938441441.23MB

7、是工业界术语（ECAT）（3）ASCMatlab实验和对比实验本实验主要是验证所提出的基于稀疏相似矩阵优化的谱聚类算法（ASC），图3.2显示分别构造RCV1数据集的稀疏化相似矩阵（t=10，20，30，40，50，100，200，300，400，500），计算相似矩阵离群点优化时间、ASC算法计算总时间、SVD计算时间和k-means计算时间，以及聚类质量（包括NMI得分和聚类精确值，聚类精确值计算介绍参见论文第五章第三节实验评估标准），NMI标准化交互信息量（NormalizedMutualInformation

8、），NMI是主要的聚类质量评估标准，NMI值越大，表明近似谱聚类算法质量越高。其用于实际的聚类标识CAT（Categorylabel）与实验结果获得的聚类标识CLS（Clusterlabel），定义如下：（3.8）（3.9）其中，与熵分别表示CAT与CLS的交互信息量、标准化在范围内。、与分别表示实际的聚类的数据点数、实验结果获得的聚类的数据点