二、近似谱聚类算法描述本节论文阐述基于相似矩阵稀疏化方法稀疏化后离群点的优化处理，并将该处理步骤应用于谱聚类算法中。
基于上述分析近似谱聚类算法整体流程总结描述如表3.2所示。
表3.2 近似谱聚类算法（ASCA）算法：近似谱聚类算法（ASCA）输入：数据点，待聚类数目输出：聚类1. 使用公式，（其中，是的个最近邻按距离排序后第个邻居，同理，），构建相似矩阵；2. 使用稀疏化矩阵获得半正定矩阵，找出矩阵对称位置不一致的相似度，并将对称元素设置为0，调整为对称半正定矩阵；3. 使用优化公式对矩阵进行离群点调优；4. 计算对称半正定拉普拉斯矩阵；5. 计算的特征向量分解，找出第k个最小非零特征特征量，并按列排列k个特征向量构建特征向量矩阵；6. 计算标准化矩阵（）；7. 使用粗糙集模型选择k-means初始化聚类中心位置并对矩阵进行k-means聚类，把其聚类成k组（）。
基于近似谱聚类算法整体步骤描述，为进行近似谱聚类算法Matlab辅助实验铺垫，绘制近似谱聚类算法流程示意图如图3.1所示。
Matlab辅助实验主要是将示意图3.1中的所示的算法与正交化Nyström低阶子矩阵抽样近似相似矩阵谱聚类算法（ONSP: Orthogonalization Nyström Spectral Clustering）和最近邻稀疏化近似相似矩阵谱聚类算法（tNNSC: Spectral Clustering）进行对比，并验证其聚类效果。
图3.1 近似谱聚类算法流程示意图三、近似谱聚类算法时间复杂度分析现对基于相似矩阵稀疏化方法离群点优化的近似谱聚类算法时间复杂度简单分析，步骤1：使用高斯函数公式构建相似矩阵的时间复杂度是，其中表示数据点数目、表示数据维数，计算数据点和之间的相似度的时间复杂度是，则计算整个数据集的时间复杂度是；步骤2：使用稀疏化矩阵获得半正定矩阵并调整为对称半正定矩阵借助于最大堆，其时间复杂度是，其中是最近邻数；步骤3：优化离群点步骤是非确定性多项式困难问题NP-hard （Non deterministic Ploynomial Hard）问题，其时间复杂度随近似相似度矩阵维数按指数增长；步骤4与步骤5：计算对称半正定拉普拉斯矩阵并找出k个最小非零特征值的特征向量的时间复杂度在论文第二章第二节中已经详细分析过，即；步骤6：计算标准化矩阵的时间复杂度是；步骤7：执行k-means聚类时间复杂度是：，其中表示k-means聚类过程迭代的次数，指待聚类数目。
第三节近似谱聚类算法实验分析一、近似谱聚类算法辅助实验（1）Matlab辅助实验环境描述为验证表3.2所示近似谱聚类算法与正交化Nyström低阶子矩阵抽样近似相似矩阵谱聚类算法和最近邻稀疏化近似相似矩阵谱聚类算法的性能，鉴于Hadoop MapReduce并行实验对比的工作量过大，故仅设计基于Matlab的对比性实验。
Matlab辅助实验环境：近似谱聚类算法（ASC）的Matlab辅助性验证以及其与正交化Nyström低阶子矩阵抽样近似相似矩阵谱聚类算法和最近邻稀疏化近似相似矩阵谱聚类算法的对比。
实验所使用的Matlab版本是：Matlab R2011a，运行Matlab的服务器是：Windows Server 2008 R2 Datacenter，系统处理器：Intel(R) CPU E5-260 0 @ 2.30GHz （2处理器），其内存（RAM）32.0GB，系统类型：64位操作系统。
（2）Matlab辅助实验数据集描述辅助性实验使用的经典文本分类数据集是路透社语料库卷I ：RCV1（Reuters Corpus Volume I）[64]，其具体描述见表3.3所示。
表3.3 实验数据集描述数据集类别数样本数特征维数数据集规模是否归一化来自领域RCV1 103 193844 144 1.23MB 是工业界术语（ECAT）（3）ASC Matlab实验和对比实验本实验主要是验证所提出的基于稀疏相似矩阵优化的谱聚类算法（ASC），图3.2显示分别构造RCV1数据集的稀疏化相似矩阵（t=10，20，30，40，50，100，200，300，400，500），计算相似矩阵离群点优化时间、ASC算法计算总时间、SVD计算时间和k-means计算时间，以及聚类质量（包括NMI 得分和聚类精确值，聚类精确值计算介绍参见论文第五章第三节实验评估标准），NMI标准化交互信息量（Normalized Mutual Information），NMI是主要的聚类质量评估标准，NMI值越大，表明近似谱聚类算法质量越高。
其用于实际的聚类标识CA T（Category label）与实验结果获得的聚类标识CLS（Cluster label），定义如下：（3.8）（3.9）其中，与熵分别表示CA T与CLS的交互信息量、标准化在范围内。
、与分别表示实际的聚类的数据点数、实验结果获得的聚类的数据点数和既属于实际的聚类又属于实验结果获得的聚类的数据点数。
图3.2 ASC计算时间和聚类质量图3.2中可以得出论文提出的ASC算法在优化相似矩阵离群点上的计算时间最耗时，但使用RCV1数据集实验所得的聚类精确度非常高，基于这样的原因，本文研究设计并实现基于Hadoop MapReduce并行近似谱聚类算法。
图3.3 ONSC计算时间和聚类质量图3.3展示论文第二章第三节所介绍的Nyström低阶子矩阵抽样法近似谱聚类算法实验结果，目的是作为参照与所提出的ASC谱聚类实验进对比。
该实验构建相似矩阵所使用的最近邻分别是t=20，30，40，50，100，200，300，400，500，1000，1500，2000，图中分别显示计算Euclidean距离矩阵与构建相似矩阵的时间，以及SVD计算时间、k-means计算时间和ONSC计算的总时间，相对于所提出的ASC聚类，ONSC计算的总时间要小很多，但是其聚类精确度不高。
图3.4 tNNSC计算时间和聚类质量图3.4描述论文第二章第三节所介绍的稀疏化矩阵法近似谱聚类算法实验结果，目的也是作为参照与所提出的ASC谱聚类实验进行对比。
该实验构建相似矩阵所使用的最近邻分别是t=5，15，30，40，50，100，150，200，250，300，350，400，450，500，图中分别显示计算Euclidean距离矩阵的时间，以及SVD计算时间、k-means计算时间和tNNSC计算的总时间，相对于所提出的ASC聚类以及ONSC聚类，tNNSC计算的总时间最少，但是其聚类精确度也不高。
二、ASC Matlab实验结果对比分析根据并行算法研究方法学中复杂性标准和性能评估，设计并行算法时，重要的是考虑算法的时空复杂性，此外，还需要考虑算法的加速比、可扩展性等其它性能参数[65]。
论文验证所提出的基于稀疏相似矩阵优化的谱聚类算法（ASC）旨在分析其计算时间和聚类质量，图3.5更加直观的对比显示优化的ASC算法、ONSC和tNNSC算法的总的计算时间，以及它们各自的SVD计算时间、k-means计算时间；优化的ASC算法、ONSC和tNNSC算法聚类质量，包括聚类的精确值和标准化交互信息量NMI。
图3.5 Matlab辅助实验计算时间和聚类质量对比论文鉴于构建优化的ASC算法近似相似矩阵的优化步骤时间、SVD计算时间、k-means计算时间，考虑ASC算法聚类精确度，研究设计并实现基于Hadoop的并行近似谱聚类算法，以期借助MapReduce并行编程框架达到在保证聚类精确度的前提下显著减少处理大规模高维数据的计算时间。
第四章MapReduce并行计算近似谱聚类算法研究与设计第一节并行算法设计Hadoop分布式集群系统MapRedue并行计算编程模型框架下，基于相似矩阵稀疏化方法离群点优化的近似谱聚类算法并行设计目的是在确保聚类质量的前提下聚类大规模高维数据。
论文基于此目的与MapReduce并行计算编程模型设计并验证第三章所提出的近似谱聚类算法。
一、MapReduce并行算法设计理念Hadoop MapReduce并行近似谱聚类算法设计与分析依赖于MapReduce并行计算模型。
MapReduce并行算法应用程序是同时执行并发作业Task的集合，Task作业集相互通信并同步协调，达到对近似谱聚类的并行求解。
MapReduce并行近似谱聚类并行算法执行分三个函数阶段设计：（1）map()函数：map()函数隶属于Mapper类，Mapper类继承JobConfigurable接口中的MapReduceBase类，接口中的configure方法按照MapReduce应用程序中定义的JobConf参数初始化Mapper类。
MapReduce应用程序使用InputFormat接口的RecordReader类调用InputSplit接口中的getRecordReader方法读取对，Mapper类中重写map()函数并行处理对，main()函数使用Mapper类中的run方法调用MapReduce应用程序中map()函数。
（2）combine()函数：combine()函数实际的功能是“本地的reduce()函数”，属于MapReduce并行计算算法设计中性能优化函数，它隶属于Combiner类，Combiner类继承JobConfigurable接口中的MapReduceBase类并实现Reducer类，重写reduce()函数：reduce(IntWritable key, Iterator<Text> values, OutputCollector <IntWritable, Text> output, Reporter reporter)，实现本地map()函数中间结果值合并，减少网络通信对算法性能的影响。
由于combine()函数阶段中间值对合并操作可以减少MapReduce应用程序中Reduce Task远程拷贝多个Map Task本地数据量（中间值），因此，如果并行近似谱聚类算法中间步骤忽略网络通信对并行算法计算时间的影响，则不考虑combine()函数对并行算法设计的性能优化。
（3）reduce()函数：reduce()函数类继承JobConfigurable接口中的MapReduceBase类并实现Reducer类，reduce()函数与combine()函数的不同之处在于，Reduce Task合并并传输Hadoop集群中不同节点的Map Task输出结果，在MapReduce应用程序中需重写reduce()函数。