近似谱聚类算法描述

二、近似谱聚类算法描述本节论文阐述基于相似矩阵稀疏化方法稀疏化后离群点的优化处理，并将该处理步骤应用于谱聚类算法中。基于上述分析近似谱聚类算法整体流程总结描述如表3.2所示。表3.2近似谱聚类算法（ASCA）算法：近似谱聚类算法（ASCA）输入：数据点，待聚类数目输出：聚类使用公式，（其中，是的个最近邻按距离排序后第个邻居，同理，），构建相似矩阵；使用稀疏化矩阵获得半正定矩阵，找出矩阵对称位置不一致的相似度，并将对称元素设置为0，调整为对称半正定矩阵；使用优化公式对矩阵进行离群点调优；计算对称半正定拉普拉斯矩阵；计算的特征向量分解，找出第k个最小非零特征特征量，并按列排列k个特征向量构建特征向量矩阵；计算标准化矩阵（）；使用粗糙集模型选择k-means初始化聚类中心位置并对矩阵进行k-means聚类,把其聚类成k组（）。基于近似谱聚类算法整体步骤描述，为进行近似谱聚类算法Matlab辅助实验铺垫，绘制近似谱聚类算法流程示意图如图3.1所示。Matlab辅助实验主要是将示意图3.1中的所示的算法与正交化Nystrom低阶子矩阵抽样近似相似矩阵谱聚类算法（ONSP:OrthogonalizationNystromSpectralClustering）和最近邻稀疏化近似相似矩阵谱聚类算法（tNNSC:SpectralClustering）进行对比，并验证其聚类效果。图3.1近似谱聚类算法流程示意图三、近似谱聚类算法时间复杂度分析现对基于相似矩阵稀疏化方法离群点优化的近似谱聚类算法时间复杂度简单分析，步骤1：使用高斯函数公式构建相似矩阵的时间复杂度是，其中表示数据点数目、表示数据维数，计算数据点和之间的相似度的时间复杂度是，则计算整个数据集的时间复杂度是；步骤2：使用稀疏化矩阵获得半正定矩阵并调整为对称半正定矩阵借助于最大堆，其时间复杂度是，其中是最近邻数；步骤3：优化离群点步骤是非确定性多项式困难问题NP-hard（NondeterministicPloynomialHard）问题，其时间复杂度随近似相似度矩阵维数按指数增长；步骤4与步骤5：计算对称半正定拉普拉斯矩阵并找出k个最小非零特征值的特征向量的时间复杂度在论文第二章第二节中已经详细分析过，即；步骤6：计算标准化矩阵的时间复杂度是；步骤7：执行k-means聚类时间复杂度是：，其中表示k-means聚类过程迭代的次数，指待聚类数目。第三节近似谱聚类算法实验分析一、近似谱聚类算法辅助实验（1）Matlab辅助实验环境描述为验证表3.2所示近似谱聚类算法与正交化Nystrom低阶子矩阵抽样近似相似矩阵谱聚类算法和最近邻稀疏化近似相似矩阵谱聚类算法的性能，鉴于HadoopMapReduce并行实验对比的工作量过大，故仅设计基于Matlab的对比性实验。Matlab辅助实验环境：近似谱聚类算法（ASC）的Matlab辅助性验证以及其与正交化Nystrom低阶子矩阵抽样近似相似矩阵谱聚类算法和最近邻稀疏化近似相似矩阵谱聚类算法的对比。实验所使用的Matlab版本是：MatlabR2011a，运行Matlab的服务器是：WindowsServer2008R2Datacenter，系统处理器：Intel（R）CPUE5-2600@2.30GHz（2处理器），其内存（RAM）32.0GB，系统类型：64位操作系统。（2）Matlab辅助实验数据集描述辅助性实验使用的经典文本分类数据集是路透社语料库卷I:RCV1（ReutersCorpusVolumeI）[64]，其具体描述见表3.3所示。表3.3实验数据集描述数据集类别数样本数特征维数数据集规模是否归一化来自领域RCV1103193844 1441.23MB是工业界术语（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）,NMI是主要的聚类质量评估标准，NMI值越大，表明近似谱聚类算法质量越高。其用于实际的聚类标识CAT（Categorylabel）与实验结果获得的聚类标识CLS（Clusterlabel），定义如下：（3.8）（3.9）其中，与熵分别表示CAT与CLS的交互信息量、标准化在范围内。、与分别表示实际的聚类的数据点数、实验结果获得的聚类的数据点数和既属于实际的聚类又属于实验结果获得的聚类的数据点数。图3.2ASC计算时间和聚类质量图3.2中可以得出论文提出的ASC算法在优化相似矩阵离群点上的计算时间最耗时，但使用RCV1数据集实验所得的聚类精确度非常高，基于这样的原因，本文研究设计并实现基于HadoopMapReduce并行近似谱聚类算法。图3.3ONSC计算时间和聚类质量图3.3展示论文第二章第三节所介绍的Nystrom低阶子矩阵抽样法近似谱聚类算法实验结果，目的是作为参照与所提出的ASC谱聚类实验进对比。该实验构建相似矩阵所使用的最近邻分别是t=20，30，40，50，100，200，300，400，500，1000，1500， 2000，图中分别显示计算Euclidean距离矩阵与构建相似矩阵的时间，以及SVD计算时间、k-means计算时间和ONSC计算的总时间，相对于所提出的ASC聚类，ONSC计算的总时间要小很多，但是其聚类精确度不高。图3.4tNNSC计算时间和聚类质量图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计算的总时间最少,但是其聚类精确度也不高。二、ASCMatlab实验结果对比分析根据并行算法研究方法学中复杂性标准和性能评估，设计并行算法时，重要的是考虑算法的时空复杂性，此外，还需要考虑算法的加速比、可扩展性等其它性能参数［65］。论文验证所提出的基于稀疏相似矩阵优化的谱聚类算法(ASC)旨在分析其计算时间和聚类质量，图3.5更加直观的对比显示优化的ASC算法、ONSC和tNNSC算法的总的计算时间，以及它们各自的SVD计算时间、k-means计算时间；优化的ASC算法、ONSC和tNNSC算法聚类质量，包括聚类的精确值和标准化交互信息量NMI。图3.5Matlab辅助实验计算时间和聚类质量对比论文鉴于构建优化的ASC算法近似相似矩阵的优化步骤时间、SVD计算时间、k-means计算时间，考虑ASC算法聚类精确度，研究设计并实现基于Hadoop的并行近似谱聚类算法，以期借助MapReduce并行编程框架达到在保证聚类精确度的前提下显著减少处理大规模高维数据的计算时间。第四章MapReduce并行计算近似谱聚类算法研究与设计第一节并行算法设计Hadoop分布式集群系统MapRedue并行计算编程模型框架下，基于相似矩阵稀疏化方法离群点优化的近似谱聚类算法并行设计目的是在确保聚类质量的前提下聚类大规模高维数据。论文基于此目的与MapReduce并行计算编程模型设计并验证第三章所提出的近似谱聚类算法。一、 MapReduce并行算法设计理念HadoopMapReduce并行近似谱聚类算法设计与分析依赖于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(IntWritablekey,Iterator<Text>values,OutputCollectorvIntWritable,Text〉output,Reporterreporter)实现本地map()函数中间结果值合并，减少网络通信对算法性能的影响。由于combine()函数阶段中间值对合并操作可以减少MapReduce应用程序中ReduceTask远程拷贝多个MapTask本地数据量(中间值)，因此，如果并行近似谱聚类算法中间步骤忽略网络通信对并行算法计算时间的影响，则不考虑combine()函数对并行算法设计的性能优化。(3)reduce()函数：reduce()函数类继承JobConfigurable接口中的MapReduceBase类并实现Reducer类，reduce()函数与combine()函数的不同之处在于，ReduceTask合并并传输Hadoop集群中不同节点的MapTask输出结果，在MapReduce应用程序中需重写reduce()函数。二、 MapReduce并行算法中依赖步骤的分解目前，HadoopMapReduce迭代式并行计算处于研究初期，受MapReduce并行计算模型支持抽象度计算所限，Hadoop1.2.1版本中MapReduce并行编程框架只能并行算法中不存在相互依赖的步骤，即不能显式地支持并行算法中迭代式的操作，但是，表3.2近似谱聚类算法中涉及多次迭代编程计算，如步骤7中k-means聚类算法聚类中心迭代更新，即聚类中心更新依赖于上次迭代的结果。在此情况下，怎样分解近似谱聚类算法中存在依赖关系的步骤的每次迭代以及何时终止迭代(可行的方法如：combine()函数对ReduceTask结果进行归并，MapReduce应用程序根据判定条件决定迭代是否终止，倘若不满足终止条件，则combine()函数再次将归并的结果数据传输给MapTask开始新一轮的迭代)、怎样优化处理MapTask和ReduceTask重新创建时所引起的资源浪费、怎样存储每次迭代过程中ReduceTask归并的数据结果是基于HadoopMapReduce并行近似谱聚类算法设计的难点，也是论文设计的重点。论文重点分析近似谱聚类算法中可用于MapTask独立计算的任务及其之间依赖性。论文所设计的MapReduce并行计算map()与reduce()函数都依据并行计算功能分解MapReduce应用程序。MapReduce并行近似谱聚类算法中依赖步骤的分解将在本章第二节给出详细的设计及并行策略，并在第五章第四节实验过程中给出并行近似谱聚类算法设计的实验验证。第二节近似谱聚类算法HadoopMapReduce并行分析与设计本节基于HadoopMapReduce分析并设计稀疏化离群点优化相似矩阵的近似谱聚类算法，首先，详细论述所提出的近似谱聚类算法步骤中时间复杂度较高的三个阶段：稀疏化近似相似矩阵、特征向量分解、k-means及其初始化聚类中心并行策略；其次，分别设计上述三个阶段的Mapper类与Reducer类以及Combiner类；最后，分析所设计基于HadoopMapReduce三个阶段时间复杂度。一、稀疏化近似相似矩阵MapReduce并行策略与设计(1)MapReduce稀疏化近似相似矩阵并行策略构建相似矩阵过程、使用近似法稀疏化相似矩阵过程以及对称半正定矩阵进行离群点调优过程中不存在迭代步骤也不相互依赖，故可设计上述三个过程的MapReduce并行计算的map()和reduce()函数。首先计算每个数据点到所有数据点的距离，以找出该数据点的个最近邻，设为Hadoop集群中slaves机器数目，对于的输入文件，理想情况下，每台机器分配个数据点。在使用Euclidean距离计算本地个数据点彼此之间的距离(distance)，为减少计算的时间，首先提前计算除外每台机器分配个数据点的值。当本地本地个数据点个数据点的距离计算完成后，按距离排序找出第数据点作为的个最近邻的中位数，进而根据计算(gammal)和(gamma2),使用最大堆保持本地数据点的个最近邻，按照公式把距离矩阵转化成相似矩阵。最后，由于可能存在数据点是的最近邻，但不是的最近邻调整成对称相似矩阵。(2)Mapper阶段设计稀疏化近似矩阵MapReduce的Mapper阶段设计中，输入是数据集.txt文件，输出是(key,value)对，其中key表示每台机器上的个数据点距离矩阵或相似矩阵标识符行标识符，value表示与之对应的距离矩阵或相似矩阵的元素值。Mapper类设计伪代码表示如下：Mapper类：map(Textkey,Textinput)Input:数据集.txt文件Output:输出(key,value)对ClassMapperMethodmap()/*设置输入分布式文件的格式与数据类型*/conf.setInputFormat();conf.setOutputKeyClass();6./*创建标识符，使得每台机器上的个数据点有相同的key*/intindex,localIndex=index/num,tNearestNeighbor;doublevalue;/*使用Euclidean距离计算本地个数据点彼此之间的距离*/compute。;//并行计算Euclidean距离distance和平均值以便计算gammal和gamma2/*按照第三章表3.2近似谱聚类算法步骤1计算相似度,使用最大堆，保持本地数据点的个最近邻*/distanceToSimilarity();//Euclidean距离矩阵转换为相似矩阵，且在原位置//存储行稀疏化后的数据点similarity=exp(-distance*distance/(2*gammal*gamma2))/*调整相似矩阵为对称矩阵*/similarityToSymmetry();/*按照第三章表3.2近似谱聚类算法步骤3对离群点进行调优*/ifdooutlierIndx=；//outlierIndx表示离群点下标//调优相似矩阵//行Emitoutput.collect(IntWritable(index),Text(outString))as(key,value)pair;〃输出(key,value)对，key近似相似矩阵标识符,value近似相似矩阵元素值(3)Reducer阶段设计稀疏化近似矩阵MapReduce的Reducer设计目的是归并Mapper阶段个机器上计算所得的本地相似矩阵部分值，最终获得并存储整个数据集的近似相似矩阵。Reducer类设计伪代码表示如下：Reducer类：reduce(IntWritablekey,Iterator<Text>values)Input:Mapper类阶段输出的分布式文件中(key,value)对Output:输出近似相似矩阵(key',value'))对ClassReducerMethodreduce()intindex;Sring[]partialValues;Doublevalues;repeatwhile(values.hasNext())dopartialValues=values.next().toString().split();for(inti=0;i<partialValues.length-l;i++)dosimilarity.array[i]+=Double.parseDouble(partialValues[i]);endforendwhileendEmitoutput.collect(IntWritable(index),Text(outString))as(key,value')pair;〃输出(key',l4. //value')对（4）MapReduce并行稀疏化并行近似相似矩阵并行时间复杂度分析HadoopMapReduce并行前构建和之间相似矩阵的时间复杂度是：，使用稀疏化矩阵获得半正定矩阵并调整为对称半正定矩阵，其时间复杂度是：，则HadoopMapReduce并行前构建基于近似法相似矩阵的时间复杂度是：。在Hadoop集群中理想情况下，假设并行计算稀疏化近似相似矩阵均匀分布到slaves上执行且不考虑优化离群点步骤是非确定性多项式困难问题NP-hard的计算时间，则HadoopMapReduce并行后计算稀疏化近似相似矩阵的时间复杂度是：（其中指Hadoop集群中slaves机器数目），表4.1给出HadoopMapReduce并行前后计算稀疏化近似相似矩阵的时间复杂度对比。表4.1MapReduce稀疏化近似相似矩阵并行时间复杂度分析稀疏化近似矩阵HadoopMapReduce并行前HadoopMapReduce并行后时间复杂度二、拉普拉斯特征向量分解的MapReduce并行策略与设计（1）MapReduce特征向量分解并行策略MapReduce并行计算并存储近似相似矩阵后，首先，计算获得对称半正定近似拉普拉斯矩阵（）；其次，在PaulG.Constantine等人［58］与AustinR.Benson等人［66］研究的基于MapRedcueQR矩阵分解基础上计算的SVD,最后，设计基于MapReduce并行计算编程模型的近似矩阵Mapper类和Reducer类求解其特征向量。为避免MapReduce只能并行处理相互依赖的步骤,MapRedcueQR矩阵分解（是正交矩阵，是上三角矩阵）使用2个map（）函数和1个reduce（）函数并行求解和矩阵，如图4.1所示步骤一和步骤三中是map（）函数，步骤二中是reduce函数。其中步骤一只是用MapTask计算本地QR矩阵分解，返回的Q、R矩阵分别存储在不同的HDFS文件中；步骤二中仅使用于一个ReduceTask，其中，输入是步骤一中矩阵分解计算所得的R矩图4.1MapReduce并行计算QR示意图阵集，该过程根据R矩阵计算Q矩阵并作为values键值输出，归并后的R矩阵即是所求矩阵分解中的上三角矩阵；步骤三中只使用一个MapTask，其输入是步骤一中计算所得的Q矩阵集，输出是与步骤二计算所得的Q矩阵集的乘积，其结果是矩阵分解中的正交矩阵。为使用MapReduce并行编程框架计算近似矩阵特征向量分解，现对上述基于MapRedcueQR矩阵分解进行修改计算的SVD，步骤二的过程中增加计算则的特征向量分解为（其中、、是正交矩阵；是上三角矩阵；是半正定对角矩阵）。根据谱定理和半正定矩阵可知：的SVD与其特征分解存在相同特征空间［67］［68］。通过上述方法可以避免因MapRedcue不能迭代计算Arnoldi求解特征向量的难题。最后通过第二章公式（2.11）计算近似矩阵的k个近似特征值与特征向量。（2）Mapper阶段设计MapReduce解析近似相似矩阵分布式文件为（key,value）对，其中key指近似相似矩阵分布式文件行标识符（包括矩阵的列数和当前行数）；value指近似相似矩阵分布式文件对应key的值。Mapper类设计伪代码表示如下：Mapper类：map（TypedBytesWritablekey,TypedBytesWritablevalues）Input:近似相似矩阵分布式文件Output:(key,values)对ClassMapperMethodmap()

intnumColumns,currentRow；〃近似相似矩阵文件列数、当前行数DenseMatrix;/*设置输入分布式文件的格式与数据类型*/conf.setInputFormat();conf.setOutputKeyClass();SubMethodcompress()beginQRqr=QR.factorize(); 〃对近似相似矩阵进行QR矩阵分解UpperTriangDenseMatrixR=qr.getR(); //获得矩阵的上三角矩阵EIGeig=EIG.eigsolver(R);EIGeig=EIG.eigsolver(R);DiagonalMatrix=eig.get();NormalizedMatrixQU=eig.getQU();TransposedMatrixV=eig.getV();/*复制上三角矩阵R*/.set(i,j,R.get(i,j));currentRow=numColumns;endnumColumns=row.length;repeatif(currentRow>=.numRows())〃对上三角矩阵R进行特征分解〃获得矩阵R的特征向量〃获得矩阵R的左特征向量〃获得矩阵R的右特征向量〃记录矩阵R的当前行号//获得矩阵的总行数docompress();endifendEmitoutput.collect(TypedBytesWritable(key),TypedBytesWritable(values))as(key,values)pair;//输出(key,values)对，key指近似相似矩阵分布式文件行标识符；values指QR分解28. 〃修改后步骤二中矩阵与UQ矩阵(3)Reducer阶段设计Reducer设计目的是归并Mapper阶段相同key的values键值，Reducer类设计伪代码表示如下：Reducer类：reduce(TypedBytesWritablekey,Iterator<TypedBytesWritable>values)Input:Mapper类阶段输出的(key,(values)对Output:输出归并后的(key',values'))对ClassReducerMethodreduce()/*ReduceTask归并Mapper类阶段输出的(key,(values)X^*/repeatwhile(values.hasNext())docollect(key,values.next());endpair;Emitoutput.collect(key,TypedBytesWritable(values))asthenew(key',values'pair;4)MapReduce特征向量分解时间并行复杂度分析HadoopMapReduce并行前计算的k个最小非零特征特征量的时间复杂度是：，在Hadoop集群中理想情况下，假设计算新k个最小非零特征特征量均匀分布到slaves上执行，则HadoopMapReduce并行后计算的k个最小非零特征特征量的时间复杂度是：(其中指Hadoop集群中slaves机器数目)，表4.2给出HadoopMapReduce并行前后计算的k个最小非零特征特征量的时间复杂度对比。表4.2MapReduce特征向量分解并行时间复杂度分析特征向量分解HadoopMapReduce并行前HadoopMapReduce并行后时间复杂度三、k-means及其初始化聚类中心MapReduce并行策略与设计MapReducek-means及其初始化聚类中心并行策略根据MapReduce并行计算编程模型依赖步骤分解k-means及其初始化聚类中心：使用计算聚类中心时，计算所有数据点对的阈值：；以及每个数据点的内聚度：耗时步骤设计并行计算；使用k-means聚类算法聚类近似相似矩阵的特征向量时，每个数据点与方法得到的k个聚类中心相互之间距离计算是互不依赖的问题求解，故设计MapReducek-means及其初始化聚类中心并行计算。Mapper阶段设计MapReduce默认解析方法得到的聚类中心文件为(key,value)对，其中key指数据点相对于中心文件起始点的偏移量；value指数据点各维信息字符串。Mapper类设计伪代码表示如下：Mapper类：map(Textkey,Textinput)Input:方法得到的聚类中心文件Output:(key,value)对ClassMapperMethodmap()/*Calculatethecentersusingmethodandloadthemfromtheconf.get().split();Calculatethedistancesbetweeneachpairofpointsandbetweenthispointsandallotherpointsaswellastheneighborhoodofeachpoint;Calculatethecohesionofeachpointandfindoutthefirstcenterwhichisthegreatestcohesionanddeterminethenextmostcohesionpoint,andreturnthecenters*/minDist=Double.MAX_VALUE,minIndex=0;index=1; //minIndex数据点距k个聚类中心最近的中心下标repeat 〃计算数据点与k个聚类中心最相似的中心并记录其下标作为keyforeach(center:centers)dodist=.getDistance(point,centers[i]);ifdist<minDistdominDist=dist;minIndex=index;endifendendEmitoutput.collect(IntWrita