近似谱聚类算法描述
二、近似谱聚类算法描述
本节论文阐述基于相似矩阵稀疏化方法稀疏化后离群点的优化处理，并将该处理步骤应用于谱聚类算法中。基于上述分析近似谱聚类算法整体流程总结描述如表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
（3）reduce()函数：
reduce()函数类继承JobConfigurable接口中的MapReduceBase类并实现Reducer类，reduce()函数与combine()函数的不同之处在于，Reduce Task合并并传输Hadoop集群中不同节点的Map Task输出结果，在MapReduce应用程序中需重写reduce()函数。
二、MapReduce并行算法中依赖步骤的分解
目前，Hadoop MapReduce迭代式并行计算处于研究初期，受MapReduce并行计算模型支持抽象度计算所限，Hadoop 1.2.1 版本中MapReduce并行编程框架只能并行算法中不存在相互依赖的步骤，即不能显式地支持并行算法中迭代式的操作，但是，表3.2近似谱聚类算法中涉及多次迭代编程计算，如步骤7中k-means聚类算法聚类中心迭代更新，即聚类中心更新依赖于上次迭代的结果。在此情况下，怎样分解近似谱聚类算法中存在依赖关系的步骤的每次迭代以及何时终止迭代（可行的方法如：combine()函数对Reduce Task结果进行归并，MapReduce应用程序根据判定条件决定迭代是否终止，倘若不满足终止条件，则combine()函数再次将归并的结果数据传输给Map Task开始新一轮的迭代）、怎样优化处理Map Task 和Reduce Task重新创建时所引起的资源浪费、怎样存储每次迭代过程中Reduce Task归并的数据结果是基于Hadoop MapReduce并行近似谱聚类算法设计的难点，也是论文设计的重点。论文重点分析近似谱聚类算法中可用于Map Task独立计算的任务及其之间依赖性。论文所设计的MapReduce并行计算map()与reduce()函数都依据并行计算功能分解MapReduce 应用程序。MapReduce并行近似谱聚类算法中依赖步骤的分解将在本章第二节给出详细的设计及并行策略，并在第五章第四节实验过程中给出并行近似谱聚类算法设计的实验验证。第二节近似谱聚类算法Hadoop MapReduce并行分析与设计
本节基于Hadoop MapReduce分析并设计稀疏化离群点优化相似矩阵的近似谱聚类算法，首先，详细论述所提出的近似谱聚类算法步骤中时间复杂度较高的三个阶段：稀疏化近似相似矩阵、特征向量分解、k-means及其初始化聚类中心并行策略；其次，分别设计上述三个阶段的Mapper类与Reducer类以及Combiner类；最后，分析所设计基于Hadoop MapReduce 三个阶段时间复杂度。
一、稀疏化近似相似矩阵MapReduce并行策略与设计
（1）MapReduce 稀疏化近似相似矩阵并行策略
构建相似矩阵过程、使用近似法稀疏化相似矩阵过程以及对称半正定矩阵进行离群点调优过程中不存在迭代步骤也不相互依赖，故可设计上述三个过程的MapReduce并行计算的map()和reduce()函数。首先计算每个数据点到所有数据点的距离，以找出该数据点的个最近邻，设为Hadoop集群中slaves机器数目，对于的输入文件，理想情况下，每台机器分配个数据点。在使用Euclidean距离计算本地个数据点彼此之间的距离（distance），为减少计算的时间，首先提前计算除外每台机器分配个数据点的值。当本地本地个数据点个数据点的距离计算完成后，按距离排序找出第数据点作为的个最近邻的中位数，进而根据计算（gamma1）和（gamma2），使用最大堆保持本地数据点的个最近邻，按照公式把距离矩阵转化成相似矩阵。最后，由于可能存在数据点是的最近邻，但不是的最近邻调整成对称相似矩阵。
（2）Mapper阶段设计
稀疏化近似矩阵MapReduce 的Mapper阶段设计中，输入是数据集.txt文件，输出是(key, value)对，其中key表示每台机器上的个数据点距离矩阵或相似矩阵标识符行标识符，value 表示与之对应的距离矩阵或相似矩阵的元素值。
Mapper类设计伪代码表示如下：
Mapper类：map (Text key, Text input)
Input: 数据集.txt文件
Output: 输出(key, value)对
1. Class Mapper
2. Method map()
3. /* 设置输入分布式文件的格式与数据类型*/
4. conf.setInputFormat();
5. conf.setOutputKeyClass();
6. /*创建标识符，使得每台机器上的个数据点有相同的key*/
6. int index, localIndex = index / num, tNearestNeighbor;
7. double value;
8. /* 使用Euclidean距离计算本地个数据点彼此之间的距离*/
9. compute();//并行计算Euclidean距离distance和平均值以便计算gamma1和gamma2
10. /*按照第三章表3.2近似谱聚类算法步骤1计算相似度, 使用最大堆，保持本地
11. 数据点的个最近邻*/
12. distanceToSimilarity(); //Euclidean距离矩阵转换为相似矩阵，且在原位置
13. //存储行稀疏化后的数据点
14. similarity = exp(- distance * distance / (2 * gamma1 * gamma2))
15. /*调整相似矩阵为对称矩阵*/
16. similarityToSymmetry ();
17. /*按照第三章表3.2近似谱聚类算法步骤3对离群点进行调优*/
18. if do
19. outlierIndx = ；// outlierIndx表示离群点下标
20. //调优相似矩阵
21. // 行
22. Emit output.collect(IntWritable(index), Text(outString)) as (key, value) pair;
23. //输出(key, value)对，key近似相似矩阵标识符,value近似相似矩阵元素值
（3）Reducer阶段设计
稀疏化近似矩阵MapReduce 的Reducer设计目的是归并Mapper阶段个机器上计算所得的本地相似矩阵部分值，最终获得并存储整个数据集的近似相似矩阵。Reducer类设计伪代码表示如下：
Reducer类：reduce (IntWritable key, Iterator
Input: Mapper类阶段输出的分布式文件中(key, value)对
Output: 输出近似相似矩阵(key’, value’))对
1. Class Reducer
2. Method reduce()
3. int index; Sring[] partialV alues; Double values;
4. repeat
5. while (values.hasNext()) do
6. partialValues = values.next().toString().split();
7. for (int i = 0; i < partialValues.length - 1; i++) do
8. similarity.array[i] += Double.parseDouble(partialValues[i]);
9. end for
10. end while
11. end
12. Emit output.collect(IntWritable(index), Text(outString)) as (key’, value’) pair; //输出(key’, 14. // value’)对
（4）MapReduce并行稀疏化并行近似相似矩阵并行时间复杂度分析
Hadoop MapReduce并行前构建和之间相似矩阵的时间复杂度是：，使用稀疏化矩阵获得半正定矩阵并调整为对称半正定矩阵，其时间复杂度是：，则Hadoop MapReduce并行前构建基于近似法相似矩阵的时间复杂度是：。在Hadoop集群中理想情况下，假设并行计算稀疏化近似相似矩阵均匀分布到slaves上执行且不考虑优化离群点步骤是非确定性多项式困难问题NP-hard的计算时间，则Hadoop MapReduce并行后计算稀疏化近似相似矩阵的时间复杂度是：（其中指Hadoop集群中slaves机器数目），表 4.1给出Hadoop MapReduce并行前后计算稀疏化近似相似矩阵的时间复杂度对比。
表4.1 MapReduce 稀疏化近似相似矩阵并行时间复杂度分析
稀疏化近似矩阵Hadoop MapReduce并行前Hadoop MapReduce并行后
时间复杂度
二、拉普拉斯特征向量分解的MapReduce并行策略与设计
（1）MapReduce 特征向量分解并行策略
MapReduce并行计算并存储近似相似矩阵后，首先，计算获得对称半正定近似拉普拉斯矩阵（）；其次，在Paul G. Constantine等人[58]与Austin R. Benson等人[66]研究的基于MapRedcue QR矩阵分解基础上计算的SVD，最后，设计基于MapReduce并行计算编程模型的近似矩阵Mapper类和Reducer类求解其特征向量。
为避免MapReduce只能并行处理相互依赖的步骤，MapRedcue QR矩阵分解（是正交矩阵，是上三角矩阵）使用2个map()函数和1个reduce()函数并行求解和矩阵，如图4.1所示步骤一和步骤三中是map()函数，步骤二中是reduce函数。其中步骤一只是用Map Task计算本地QR矩阵分解，返回的Q、R矩阵分别存储在不同的HDFS文件中；步骤二中仅使用于一个Reduce Task，其中，输入是步骤一中矩阵分解计算所得的R矩
图4.1 MapReduce 并行计算QR示意图
阵集，该过程根据R矩阵计算Q矩阵并作为values键值输出，归并后的R矩阵即是所求矩阵分解中的上三角矩阵；步骤三中只使用一个Map Task，其输入是步骤一中计算所得的Q 矩阵集，输出是与步骤二计算所得的Q矩阵集的乘积，其结果是矩阵分解中的正交矩阵。为使用MapReduce并行编程框架计算近似矩阵特征向量分解，现对上述基于MapRedcue QR矩阵分解进行修改计算的SVD，步骤二的过程中增加计算则的特征向量分解为（其中、、是正交矩阵；是上三角矩阵；是半正定对角矩阵）。根据谱定理和半正定矩阵可知：的SVD与其特征分解存在相同特征空间[67][68]。通过上述方法可以避免因MapRedcue 不能迭代计算Arnoldi求解特征向量的难题。最后通过第二章公式（2.11）计算近似矩阵的k个近似特征值与特征向量。
（2）Mapper阶段设计
MapReduce解析近似相似矩阵分布式文件为(key, value)对，其中key指近似相似矩阵分布式文件行标识符（包括矩阵的列数和当前行数）；value指近似相似矩阵分布式文件对应key 的值。Mapper类设计伪代码表示如下：
Mapper类：map (TypedBytesWritable key, TypedBytesWritable values)
Input: 近似相似矩阵分布式文件
Output: (key, values)对
1. Class Mapper
2. Method map()
3. int numColumns，currentRow；//近似相似矩阵文件列数、当前行数
4. DenseMatrix ;
5. /* 设置输入分布式文件的格式与数据类型*/
6. conf.setInputFormat();
7. conf.setOutputKeyClass();
8. SubMethod compress()
9. begin
10. QR qr = QR.factorize( ); //对近似相似矩阵进行QR矩阵分解
11. UpperTriangDenseMatrix R = qr.getR(); //获得矩阵的上三角矩阵
12. EIG eig = EIG.eigsolver(R); //对上三角矩阵R进行特征分解
13. DiagonalMatrix = eig.get (); //获得矩阵R的特征向量
14. NormalizedMatrix QU = eig.getQU(); //获得矩阵R的左特征向量
15. TransposedMatrix V = eig.getV(); //获得矩阵R的右特征向量
16. /* 复制上三角矩阵R */
17. .set(i,j,R.get(i,j));
18. currentRow = numColumns; //记录矩阵R的当前行号
19. end
20. numColumns = row.length; //获得矩阵的总行数
21. repeat
22. if (currentRow >= .numRows()) do
23. compress();
24. end if
25. end
26. Emit output.collect(TypedBytesWritable(key), TypedBytesWritable (values)) as (key, values)
27. pair; // 输出(key, values)对，key 指近似相似矩阵分布式文件行标识符；values指QR分解28. //修改后步骤二中矩阵与UQ矩阵
（3）Reducer阶段设计
Reducer设计目的是归并Mapper阶段相同key的values键值，Reducer类设计伪代码表示如下：
Reducer类：reduce (TypedBytesWritable key, Iterator< TypedBytesWritable > values)
Input: Mapper类阶段输出的(key, (values)对
Output: 输出归并后的(key’, values’))对
1. Class Reducer
2. Method reduce()
3. /* Reduce Task归并Mapper类阶段输出的(key, (values)对*/
4. repeat
5. while (values.hasNext()) do
6. collect(key,values.next());
7. end
8. Emit output.collect(key, TypedBytesWritable (values)) as the new (key’, values’) pair;
（4）MapReduce特征向量分解时间并行复杂度分析
Hadoop MapReduce并行前计算的k个最小非零特征特征量的时间复杂度是：，在Hadoop 集群中理想情况下，假设计算新k个最小非零特征特征量均匀分布到slaves上执行，则Hadoop MapReduce并行后计算的k个最小非零特征特征量的时间复杂度是：（其中指Hadoop集群中slaves机器数目），表4.2给出Hadoop MapReduce并行前后计算的k个最小非零特征特征量的时间复杂度对比。
表4.2 MapReduce特征向量分解并行时间复杂度分析
特征向量分解Hadoop MapReduce并行前Hadoop MapReduce并行后
时间复杂度
三、k-means及其初始化聚类中心MapReduce并行策略与设计
（1）MapReduce k-means及其初始化聚类中心并行策略
根据MapReduce并行计算编程模型依赖步骤分解k-means及其初始化聚类中心：使用计算聚类中心时，计算所有数据点对的阈值：；以及每个数据点的内聚度：
耗时步骤设计并行计算；使用k-means聚类算法聚类近似相似矩阵的特征向量时，每个数据点与方法得到的k个聚类中心相互之间距离计算是互不依赖的问题求解，故设计MapReduce k-means及其初始化聚类中心并行计算。
（2）Mapper阶段设计
MapReduce默认解析方法得到的聚类中心文件为(key, value)对，其中key指数据点相对于中心文件起始点的偏移量；value指数据点各维信息字符串。Mapper类设计伪代码表示如下：
Mapper类：map (Text key, Text input)
Input: 方法得到的聚类中心文件
Output: (key, value)对
1. Class Mapper
2. Method map()
3. /*Calculate the centers using method and load them from the conf.get().split();
4. Calculate the distances between each pair of points and between this points and all other points as
5. well as the neighborhood of each point; Calculate the cohesion of each point and find out the first
6. center which is the greatest cohesion and determine the next most cohesion point, and return the
7.centers*/
8. minDist = Double.MAX_V ALUE, minIndex = 0;
9. index = 1; // minIndex数据点距k个聚类中心最近的中心下标
10. repeat //计算数据点与k个聚类中心最相似的中心并记录其下标作为key
11. foreach (center : centers) do
12. dist = .getDistance(point, centers[i]);
13. if dist< minDist do
14. minDist=dist;
15. minIndex=index;
16. end if
17. end
18.end
19. Emit output.collect(IntWritable(minIndex),Text(outString)) as (key,value) pair;
20. // 输出(key, value)对，outString数据点各维信息字符串
（3）Combiner阶段设计
设计Combiner类功能是归并Mapper类的本地Map Task输出的具有相同聚类中心minIndex 的数据点(key, value)对，其目的是减少k-means聚类算法中迭代过程中Reduce Task因远程传输Map Task本地中间值数据量而引起的网络通信负载。Combiner类设计伪代码表示如下：Combiner类：combine (IntWritable key, Iterator
Input: Mapper类阶段输出的本地(key, value)对
Output: (key, list(value))对
1. Class Combiner
2. Method combine()
3. /*使用Combiner类归并Mapper类的本地Map Task输出的具有相同聚类中心minIndex 的数
4. 据点(key, value)对*/
5. count = 0, String [] co_ordinates;
6. while (values.hasNext()) do
7. co_ordinates = values.next().toString().split();
8. if (co_ordinates[1].equals("-1")) do continue;
9. end if
10. for (int i = 2; i < co_ordinates.length; i++) do
11. point.array[i - 2] += Double.parseDouble(co_ordinates [i]);
12. end for
13. end while
14. count += 1; //相同Map Task中同一聚类中心数据点数目
15. Emit output.collect(key, Text(outString)) as (key, list(value)) pair; //输出(key, list(value))对，
16. //outString本地Map Task中同一聚类中心数据点总数及数据点各维信息字符串
（4）Reducer阶段设计
Reducer设计目的是归并Combiner阶段预归并的本地中间值并更新k-means聚类算法聚类中心，除以数据点数目count得出新的聚类中心，用于下一次算法迭代的聚类中心，Reducer 类设计伪代码表示如下：
Reducer类：reduce (IntWritable key, Iterator
Input: Combiner类阶段输出的归并后本地(key, list(value))对
Output: 输出新的聚类中心(key’, value’))对，value’新聚类中心数据点各维信息字符串
1. Class Reducer
2. Method reduce()
3. /*解析从Combiner类接收的中间结果，得到本地Map Task中同一聚类中心数据点总数及数
4. 据点各维信息字符串*/
近似谱聚类算法描述
二、近似谱聚类算法描述 本节论文阐述基于相似矩阵稀疏化方法稀疏化后离群点的优化处理，并将该处理步骤应用于谱聚类算法中。基于上述分析近似谱聚类算法整体流程总结描述如表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并行实验对
(完整word版)各种聚类算法介绍及对比
一、层次聚类 1、层次聚类的原理及分类 1）层次法（Hierarchical methods）先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成了一个类。其中类与类的距离的计算方法有：最短距离法，最长距离法，中间距离法，类平均法等。比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。 层次聚类算法根据层次分解的顺序分为：自下底向上和自上向下，即凝聚的层次聚类算法和分裂的层次聚类算法（agglomerative和divisive），也可以理解为自下而上法（bottom-up）和自上而下法（top-down）。自下而上法就是一开始每个个体（object）都是一个 类，然后根据linkage寻找同类，最后形成一个“类”。自上而下法就是反过来，一开始所有个体都属于一个“类”，然后根据linkage排除异己，最后每个个体都成为一个“类”。这两种路方法没有孰优孰劣之分，只是在实际应用的时候要根据数据特点以及你想要的“类”的个数，来考虑是自上而下更快还是自下而上更快。至于根据Linkage判断“类” 的方法就是最短距离法、最长距离法、中间距离法、类平均法等等（其中类平均法往往被认为是最常用也最好用的方法，一方面因为其良好的单调性，另一方面因为其空间扩张/浓缩的程度适中）。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。 2）Hierarchical methods中比较新的算法有BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies利用层次方法的平衡迭代规约和聚类）主要是在数据量很大的时候使用，而且数据类型是numerical。首先利用树的结构对对象集进行划分，然后再利用其它聚类方法对这些聚类进行优化；ROCK（A Hierarchical Clustering Algorithm for Categorical Attributes）主要用在categorical的数据类型上；Chameleon（A Hierarchical Clustering Algorithm Using Dynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此构建一个graph，Chameleon的聚类效果被认为非常强大，比BIRCH好用，但运算复杂度很高，O(n^2)。 2、层次聚类的流程 凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。这里给出采用最小距离的凝聚层次聚类算法流程： (1) 将每个对象看作一类，计算两两之间的最小距离； (2) 将距离最小的两个类合并成一个新类； (3) 重新计算新类与所有类之间的距离； (4) 重复(2)、(3)，直到所有类最后合并成一类。
大数据建模与挖掘应用
关于举办“大数据建模与分析挖掘应用”实战培训班的通知地点北京上海 时间12月 23-26 1月 12-15 一、课程简介 大数据建模与分析挖掘技术已经逐步地应用到新兴互联网企业（如电子商务网站、搜索引擎、社交网站、互联网广告服务提供商等）、银行金融证券企业、电信运营等行业，给这些行业带来了一定的数据价值增值作用。 本次课程面向有一定的数据分析挖掘算法基础的工程师，带大家实践大数据分析挖掘平台的项目训练，系统地讲解数据准备、数据建模、挖掘模型建立、大数据分析与挖掘算法应用在业务模型中，结合主流的Hadoop与Spark大数据分析平台架构，实现项目训练。 结合业界使用最广泛的主流大数据平台技术，重点剖析基于大数据分析算法与BI技术应用，包括分类算法、聚类算法、预测分析算法、推荐分析模型等在业务中的实践应用，并根据讲师给定的数据集，实现两个基本的日志数据分析挖掘系统，以及电商（或内容）推荐系统引擎。 本课程基本的实践环境是Linux集群，JDK1.8， Hadoop 2.7.*，Spark 2.1.*。 学员需要准备的电脑最好是i5及以上CPU，4GB及以上内存，硬盘空间预留50GB（可用移动硬盘），基本的大数据分析平台所依赖的软件包和依赖库等，讲师已经提前部署在虚拟机镜像（VMware镜像），学员根据讲师的操作任务进行实践。 本课程采用技术原理与项目实战相结合的方式进行教学，在讲授原理的过程中，穿插实际的系统操作，本课程讲师也精心准备的实际的应用案例供学员动手训练。 二、培训目标 1.本课程让学员充分掌握大数据平台技术架构、大数据分析的基本理论、机器学习的常用算法、国内外主流的大数据分析与BI商业智能分析解决方案、以及大数据分析在搜索引擎、广告服务推荐、电商数据分析、金融客户分析方面的应用案例。 2.本课程强调主流的大数据分析挖掘算法技术的应用和分析平台的实施，让学员掌握主流的基于大数据Hadoop和Spark、R的大数据分析平台架构和实际应用，并用结合实际的生产系统案例进
谱聚类Clustering -
聚类分析 1.聚类分析定义： 2.聚类方法： 3.谱聚类： 3.1 常见矩阵变换 3.2 谱聚类流程 3.3 谱聚类理论前提、证明 3.4 图像分割实例结果 4.总结：
聚类分析： ?聚类分析（Cluster analysis，亦称为群集分析）是对于静态数据分析的一门技术，在许多领域受到广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息。
算法分类： ?数据聚类算法可以分为结构性或者分散性。 ?结构性算法以前成功使用过的聚类器进行分类。结构性算法可以从上至下或者从下至上双向进行计算。从下至上算法从每个对象作为单独分类开始，不断融合其中相近的对象。而从上至下算法则是把所有对象作为一个整体分类，然后逐渐分小。 ?分散型算法是一次确定所有分类。K-均值法及衍生算法。 ?谱聚类（spectral clustering）
结构型：层次聚类的一个例子：
分散型：K-均值算法：
分散型k-means 及其衍生算法的比较：K-means K-Medoids K-Means算法： 1. 将数据分为k个非空子集 2. 计算每个类中心点（k-means
聚类算法分析报告汇总
嵌入式方向工程设计实验报告 学院班级：130712 学生学号：13071219 学生姓名：杨阳 同作者：无 实验日期：2010年12月
聚类算法分析研究 1 实验环境以及所用到的主要软件 Windows Vista NetBeans6.5.1 Weka3.6 MATLAB R2009a 2 实验内容描述 聚类是对数据对象进行划分的一种过程，与分类不同的是，它所划分的类是未知的，故此，这是一个“无指导的学习” 过程，它倾向于数据的自然划分。其中聚类算法常见的有基于层次方法、基于划分方法、基于密度以及网格等方法。本文中对近年来聚类算法的研究现状与新进展进行归纳总结。一方面对近年来提出的较有代表性的聚类算法，从算法思想。关键技术和优缺点等方面进行分析概括；另一方面选择一些典型的聚类算法和一些知名的数据集，主要从正确率和运行效率两个方面进行模拟实验，并分别就同一种聚类算法、不同的数据集以及同一个数据集、不同的聚类算法的聚类情况进行对比分析。最后通过综合上述两方面信息给出聚类分析的研究热点、难点、不足和有待解决的一些问题等。 实验中主要选择了K 均值聚类算法、FCM 模糊聚类算法并以UCI Machine Learning Repository 网站下载的IRIS 和WINE 数据集为基础通过MATLAB 实现对上述算法的实验测试。然后以WINE 数据集在学习了解Weka 软件接口方面的基础后作聚类分析，使用最常见的K 均值（即K-means ）聚类算法和FCM 模糊聚类算法。下面简单描述一下K 均值聚类的步骤。 K 均值算法首先随机的指定K 个类中心。然后： （1）将每个实例分配到距它最近的类中心，得到K 个类； （2）计分别计算各类中所有实例的均值，把它们作为各类新的类中心。 重复（1）和（2），直到K 个类中心的位置都固定，类的分配也固定。 在实验过程中通过利用Weka 软件中提供的simpleKmeans （也就是K 均值聚类算法对WINE 数据集进行聚类分析，更深刻的理解k 均值算法，并通过对实验结果进行观察分析，找出实验中所存在的问题。然后再在学习了解Weka 软件接口方面的基础上对Weka 软件进行一定的扩展以加入新的聚类算法来实现基于Weka 平台的聚类分析。 3 实验过程 3.1 K 均值聚类算法 3.1.1 K 均值聚类算法理论 K 均值算法是一种硬划分方法，简单流行但其也存在一些问题诸如其划分结果并不一定完全可信。K 均值算法的划分理论基础是 2 1 min i c k i k A i x v ∈=-∑∑ （1） 其中c 是划分的聚类数，i A 是已经属于第i 类的数据集i v 是相应的点到第i 类的平均距离，即
应用层DDOS攻击检测技术研究
应用层DDOS攻击检测技术研究 熊俊 (湖南警察学院湖南长沙410138) 【摘要】随着检测底层DDoS攻击的技术不断成熟和完善，应用层DDoS攻击越来越多。由于应用层协议的复杂性，应用层DDoS攻击更具隐蔽性和破坏性，检测难度更大。通过研究正常用户访问的网络流量特征和应用层DDoS攻击的流量特征，采用固定时间窗口内的请求时间间隔以及页面作为特征。通过正常用户和僵尸程序访问表现出不同的特点，对会话进行聚类分析，从而检测出攻击，经过实验，表明本检测算法具有较好的检测性能。 【关键词】DDOS；应用层；聚类；异常检测 Xiong Jun (Hunan Police Academy HunanChangsha410138) 0引言 根据世界著名网络安全公司ＡｒｂｏｒＮｅｔｗｏｒｋｓ在２０１１年发布的安全报告显示，分布式拒绝服务攻击是运 营商、服务提供商以及密切依赖网络的企业最大的威 胁。国内的网络安全公司—绿盟科技２０１１年发布的 网络安全回顾指出，目前网络攻击者逐渐将目标聚集到 实施破坏和信息窃取上来，而实施破坏的主要途径就是 针对网络空间发动ＤＤｏＳ攻击。国家互联网应急中心ＣＮＣＥＲＴ在２０１１发布的安全态势综述中指出，ＤＤｏＳ攻 击仍然呈频率高、规模大等特点，我国日均发生流量大 于１Ｇ的ＤＤｏＳ攻击事件达３６５起。大多数攻击针对网 站如政府网站、游戏服务器以及ＤＮＳ服务器，造成受害 者损失大量收入，对ＤＮＳ服务器的攻击会导致大片地区互联网用户不能使用网络服务，典型案例如２００９年 暴风事件，导致江西、河北等９个省市大量用户遭遇上 网故障。安全公司卡巴斯基发布的２０１１下半年安全监 控报告中指出，ｈｔｔｐ类型的ＤＤｏＳ攻击占据了所有的 ＤＤｏＳ攻击类型的８０％，可见应用层ＤＤｏＳ危害之大。 ＤＤｏＳ攻击最早开始于１９９６年，２００２年开始在国 内出现，２００３年便初具规模。ＤＤｏＳ攻击发展趋势为从 低层协议向高层协议发展，传统ＤＤｏＳ攻击利用协议漏 洞或者洪水攻击等对受害者发起攻击，如网络层Ｎｕｋｅ 攻击利用发送畸形的ＩＣＭＰ数据包使得受害者当机，网 络层泪滴攻击利用发送重叠的ＩＰ分片使得目标主机 ＴＣＰ／ＩＰ协议栈崩溃而拒绝服务。ＵＤＰＦｌｏｏｄ、ＴＣＰＦｌｏｏｄ等传输层的洪水攻击利用发送超出受害者服务能力的 大量数据包，消耗掉受害者的网络带宽、ＣＰＵ处理能力、
谱聚类报告
机器学习报告 一．绪论 聚类是探索性数据分析中广泛采用的一种技术，其应用范围包括统计学、计算机科学、生物学、社会科学和心理学等等。在处理经验数据的时候，我们可能倾向于根据数据的“近似表现”将数据确定到一定的类别。而本次我们小组的实验主要是基于聚类算法中的谱聚类方法，通过对两种谱聚类方法的实验和一些应用，验证算法的效果，加深对该方法的理解。 由于谱聚类的数值实现很简单，利用简单的线性代数学方法就能有效解决，而且相比传统的K 均值方法等聚类方法有很多优点，所以谱聚类方法称为了很流行的现代聚类算法之一。 以K 均值方法为例，正如我们所知，该方法主要存在这样一些问题：首先，其只适用于凸球形的样本空间，如果样本空间非凸，则会陷入局部最优，导致聚类效果不佳；再有，由于该方法计算使用的是欧氏空间中的原始数据向量，所以在样本维数很大的时候，K 均值算法的计算量会很大，导致了计算的困难；聚类数K 难以确定等等。而谱聚类则能很好地解决这些问题。 在本次实验中，我们小组根据相关文献，认真学习和讨论了谱聚类的先关概念。首先，我们研究了一般的谱聚类和标准化谱聚类的概念和它们的异同，并通过实验对比，验证了谱聚类的效果，其中标准化谱聚类有显著的优势。接下来，将谱聚类应用于图像分割问题，显示出谱聚类良好的应用价值。最后，我们查阅相关文献，尝试从另外一个角度去理解谱聚类方法。通过这次学习，我们对谱聚类的理解得到了大大加深，对于很多疑难的地方也通过查看有关文献和小组讨论得到了解决，并通过小组合作锻炼了自身的团队意识和配合工作的能力。 二．谱聚类基本思想 谱聚类是一种基于图论的聚类方法，把样本看作图的顶点，样本间的相似度对应带权值的边（其中相似度可以通过高斯核函数等方法构造），根据类间相似度最小，类内相似度最大的原则，便可以将样本聚类问题变成了图的分割问题：分割使得连接不同类之间的边的权值尽可能小，而类内点之间的边的权值尽可能高。虽然这样对应的最小化图分割问题是一个NP-HARD 问题，但是我们可以将其转化为最小化图的Laplace 矩阵的特征值问题。 具体地，给定样本特征之后，我们首先要计算样本两两之间的相似度值，并通过这些值构造出近邻矩阵。以高斯核函数为例，计算公式如下： 22||||(2)i j x x ij w e σ--= 作为第i 个样本和第j 个样本之间相似度的度量。而近邻矩阵如下： ()ij W w =。
数据仓库复习题
第一章概述 1.数据挖掘的定义？（书P2，PPT_P8） 从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 2.数据挖掘的源是否必须是数据仓库的数据？可以有哪些来源？（PPT_P14） 关系数据库、数据仓库、事务数据库、高级数据等 3.数据挖掘的常用方法？（P4、PPT_P29） 聚类分析、决策树、人工神经网络、粗糙集、关联规则挖掘、统计分析等 4.数据挖掘的过程包括哪些步骤，每一步具体包括哪些内容？（书P2-3，PPT_P17-19） 确定业务对象、数据准备、数据挖掘、结果分析与知识同化。 5.数据挖掘与数据仓库的关系（联系和区别）？书P6-7，PPT_P45-46 联系：1，数据仓库为数据挖掘提供了更好的，更广泛的数据源 2，数据仓库韦数据挖掘提供了新的支持平台。 3，数据仓库为更好地使用数据挖掘工具提供了方便 4，数据挖掘对数据仓库提供了更好的决策支持。 5，数据挖掘对数据仓库的数据组织提出了更高的要求 6，数据挖掘还为数据仓库提供了广泛的技术支持 区别：数据仓库是一种存储技术，它包含大量的历史数据、当前的详细数据以及综合数据，它能为不同用户的不同决策需要提供所需的数据和信息。~~数据挖掘是从人工智能机器学习中发展起来的，它研究各种方法和技术，从大量的数据中挖掘出有用的信息和知识。 第二章数据仓库 1.数据仓库的定义 数据仓库——是一个面向主题的、集成的、随时间而变化的、不容易丢失的数据集合，支持管理部门的决策定制过程。 2.数据仓库数据的四大基本特征： 面向主题的、集成的、不可更新的、随时间变化的。 3.数据仓库体系结构有三个独立的数据层次： 信息获取层、信息存储层、信息传递层。 4.粒度的定义？它对数据仓库有什么影响？ （1）是指数据仓库的数据单位中保存数据细化或综合程度的级别。粒度越小，细节程度越高，综合程度越低，回答查询的种类就越多。 （2）影响存放在数据仓库中的数据量大小；影响数据仓库所能回答查询问题的细节程度。 5.在数据仓库中，数据按照粒度从小到大可分为四个级别： 早期细节级、当前细节级、轻度细节级和高度细节级。 6.数据分割的标准：可按日期、地域、业务领域、或按多个分割标准的组合，但一般包括日期项。 7.数据仓库设计中，一般存在着三级数据模型： 概念数据模型、逻辑数据模型、物理数据模型 8.数据仓库设计步骤 （1）概念模型设计 （2）技术准备工作 （3）逻辑模型设计 （4）物理模型设计 （5）数据仓库的生成
谱聚类算法(Spectral Clustering)原理分析
谱聚类算法(Spectral Clustering) 谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远，以达到常见的聚类的目的。其中的最优是指最优目标函数不同，可以是割边最小分割——如图1的Smallest cut(如后文的Min cut)，也可以是分割规模差不多且割边最小的分割——如图1的Best cut(如后文的Normalized cut)。 图1 谱聚类无向图划分——Smallest cut和Best cut 这样，谱聚类能够识别任意形状的样本空间且收敛于全局最优解，其基本思想是利用样本数据的相似矩阵(拉普拉斯矩阵)进行特征分解后得到的特征向量进行聚类。 1 理论基础 对于如下空间向量item-user matrix： 如果要将item做聚类，常常想到k-means聚类方法，复杂度为o(tknm)，t为迭代次数，k为类的个数、n为item个数、m为空间向量特征数： 1 如果M足够大呢？ 2 K的选取？ 3 类的假设是凸球形的？ 4 如果item是不同的实体呢？ 5 Kmeans无可避免的局部最优收敛？ …… 这些都使常见的聚类问题变得相当复杂。 1.1 图的表示
如果我们计算出item与item之间的相似度，便可以得到一个只有item的相似矩阵，进一步，将item看成了Graph(G)中Vertex(V)，歌曲之间的相似度看成G中的Edge(E)，这样便得到我们常见的图的概念。 对于图的表示(如图2)，常用的有： 邻接矩阵：E，e ij表示v i和v i的边的权值，E为对称矩阵，对角线上元素为0，如图2-2。 Laplacian矩阵：L = D – E，其中d i (行或列元素的和)，如图2-3。 图2 图的表示 1.2 特征值与L矩阵 先考虑一种最优化图像分割方法，以二分为例，将图cut为S和T两部分，等价于如下损失函数cut(S, T)，如公式1所示，即最小(砍掉的边的加权和)。 假设二分成两类，S和T，用q(如公式2所示)表示分类情况，且q满足公式3的关系，用于类标识。 那么：
谱聚类算法 算法简介
谱聚类算法算法简介 谱聚类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。 该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并且计算矩阵的特征值和特征向量，然后选择合适的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉、VLS I 设计等领域，最近才开始用于机器学习中，并迅速成为国际上机器学习领域的研究热点。 谱聚类算法建立在图论中的谱图理论基础上，其本质是将聚类问题转化为图的最优划分问题，是一种点对聚类算法，对数据聚类具有很好的应用前景。 算法步骤 谱聚类算法将数据集中的每个对象看作是图的顶点V，将顶点间的相似度量化作为相应顶点连接边E的权值，这样就得到一个基于相似度的无向加权图G(V, E)，于是聚类问题就可以转化为图的划分问题。基于图论的最优划分准则就是使划分成的子图内部相似度最大，子图之间的相似度最小。 虽然根据不同的准则函数及谱映射方法，谱聚类算法有着不同的具体实现方法，但是这些实现方法都可以归纳为下面三个主要步骤： 1) 构建表示对象集的相似度矩阵W； 2) 通过计算相似度矩阵或拉普拉斯矩阵的前k个特征值与特征向量，构建特征向量空间； 3) 利用K-means或其它经典聚类算法对特征向量空间中的特征向量进行聚类。 上面的步骤只是谱聚类算法的一个总体框架，由于划分准则、相似度矩阵计算方法等因素的差别，具体的算法实现同样会有所差别，但其本质依然是图划分问题的连续放松形式。 划分准则 谱聚类算法将聚类问题就可以转化为图的划分问题之后，基于图论的划分准则的优劣直接影响到聚类结果的好坏。常见的划分准则有Mini cut，Average cut，Normalized cut，Min-max cut，Ratio cut，MNcut等。最小割集准则 在对图像分割中产生了较好的效果，但是该准则容易产生分割出只包含几个顶点的较小子图的歪斜分割现象。 规范割集准则 在2000年Shi和Malik根据谱图理论建立了2-way划分的规范割目标函数，此方法通过计算分割之后的连接边损失值在各个子图与所有顶点之间的连接边权重总值中所占比例之和来衡量划分的优劣。 比例割集准则 对于超大规模集成电路设计中的电路层次设计和分支划分问题，最
谱聚类
谱聚类 七月算法邹博 2015年11月15日
9月机器学习班2/21 谱和谱聚类 ?方阵作为线性算子，它的所有特征值的全体统称方阵的谱。 ?方阵的谱半径为最大的特征值 ?矩阵A 的谱半径：(A T A)的最大特征值 ?谱聚类是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类的目的。
9月机器学习班3/21 谱分析的整体过程 ?给定一组数据x 1,x 2,...x n ，记任意两个点之间的相似度(“距离”的减函数)为s ij =
9月机器学习班4/21 若干概念 ?无向图G=(V,E) ?邻接矩阵 ?顶点的度di →度矩阵D (对角阵)
9月机器学习班5/21 若干概念 ?子图A 的指示向量 ?A 和B 是图G 的不相交子图，则定义子图的连接权：
9月机器学习班6/21 相似度图G 的建立方法 ?全连接图 ?高斯相似度函数：距离越大，相似度越小 ?ε近邻图 ?给定参数ε ?思考：如何选择ε？ ?图G 的权值的均值 ?图G 的最小生成树的最大边 ?k 近邻图(k-nearest neighbor graph) ?若vi 的k 最近邻包含vj ，vj 的k 最近邻不一定包含vi ：有向图?忽略方向的图，往往简称“k 近邻图” ?两者都满足才连接的图，称作“互k 近邻图(mutual)”
Python大数据机器实战
关于举办“Python大数据机器学习实战”高级工程师 实战培训班的通知 地点：北京--时间：12月25-12月28 一、课程学习目标 1.每个算法模块按照“原理讲解→分析数据→自己动手实现→特征与调参”的顺序。 2.“Python数据清洗和特征提取”，提升学习深度、降低学习坡度。 3.增加网络爬虫的原理和编写，从获取数据开始，重视将实践问题转换成实际模型的能力，分享工作中的实际案例或Kaggle案例：广告销量分析、环境数据异常检测和分析、数字图像手写体识别、Titanic乘客存活率预测、用户-电影推荐、真实新闻组数据主题分析、中文分词、股票数据特征分析等。 4.强化矩阵运算、概率论、数理统计的知识运用，掌握机器学习根本。 5.阐述机器学习原理，提供配套源码和数据。 6.以直观解释，增强感性理解。 7.对比不同的特征选择带来的预测效果差异。 8.重视项目实践，重视落地。思考不同算法之间的区别和联系，提高在实际工作中选择算法的能力。 9.涉及和讲解的部分Python库有：Numpy、Scipy、matplotlib、Pandas、scikit-learn、XGBoost、libSVM、LDA、Gensim、NLTK、HMMLearn。 二、课程目标 本课程特点是从数学层面推导最经典的机器学习算法，以及每种算法的示例和代码实现（Python）、如何做算法的参数调试、以实际应用案例分析各种算法的选择等。 三、培训对象 大数据分析应用开发工程师、大数据分析项目的规划咨询管理人员、大数据分析项目的IT项目高管人员、大数据分析与挖掘处理算法应用工程师、大数据分析集群运维工程师、大数据分析项目的售前和售后技术支持服务人员
谱聚类算法及其在图像分割中的应用
谱聚类算法及其在图像分割中的应用 1 引言 在对图像的研究和应用中，人们往往仅对图像中的某些部分或者说某些区域感兴趣。这些部分常称为目标或前景（其他部分称为背景），它们一般对应图像中特定的具有独特性质的区域。为了辨识和分析目标，需要将它们从图像中分离提取出来，在此基础上才有可能对目标进一步利用。图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。这里的特性可以是像素的灰度、颜色和纹理等，预先定义的目标可以对应单个区域，也可以对应多个区域。 多年来，对图像分割的研究一直是图像技术研究中的热点和焦点，它不但是从图像处理到图像分析的关键步骤[1]，而且是计算机视觉领域低层次视觉中的主要问题。图像分割的结果是图像特征提取和识别等图像理解的基础，只有在图像被分割后，图像的分析才成为可能。 图像分割在实际应用中已得到了广泛的应用，如图像编码、模式识别、位移估计、目标跟踪、大气图像、军用图像、遥感图像、生物医学图像分析等领域。同时，图像分割也在计算机视觉和图像识别的各种应用系统中占有相当重要的地位，它是研制和开发计算机视觉系统、字符识别和目标自动获取等图像识别和理解系统首先要解决的问题。概括地说只要需对图像目标进行提取测量等都离不开图像分割。 对分割算法的研究已经有几十年的历史，至今借助于各种理论已经提出了数以千计的分割算法[2]，而且这方面的研究仍然在积极进行。尽管人们在图像分割方面做了许多工作，但至今仍无通用的分割算法，也不存在一个判断分割是否成功的客观标准。因此已经提出的分割算法大都是针对具体问题的，并没有一种适合于所有图像的通用的分割算法。实际上由于不同领域的图像千差万别，也不可能存在万能的通用算法。 现有的分割算法非常多，大体上可以分为以下几类：阈值化分割、基于边缘检测的、基于区域的、基于聚类的和基于一些特定理论工具的分割方法。从图像的类型来分最常见的：有灰度图像分割、彩色图像分割和纹理图像分割等等。本
基于校园大数据构建大学生画像的技术实现
152 ?电子技术与软件工程 Electronic Technology & Software Engineering 数据库技术 ? Data Base Technique 【关键词】校园大数据 大学生画像 用户建模 谱聚类 随着社会步入大数据时代，高校不可避免的需要在教学及管理方面进行一系列改革。这其中最大的变化在于，学生的一切行为在学校面前都将是“可视化”的，随着大数据技术的深入研究与应用，高校在教学及管理领域的专注点将聚焦于如何利用教育大数据为学生提供优质的课程设计、良好的学习环境、精准的生活服务。于是，“大学生画像”概念应运而生。 1 关于大学生画像 1.1 大学生画像之定义 用户画像(persona)的概念最早由交互设计之父Alan Cooper 在《About Face ：交互设计精髓2》一书中提出：“Personas are a concrete representation of target users.” 是指真实用户的虚拟代表，是建立在一系列真实属性数据之上的目标用户模型。 大学生画像来自于用户画像，其定义目前尚无统一标准。[1]李光耀等描述为“基于大数据技术，通过整理搜集学生在网上的浏览、点击、留言、评论等碎片化的行为轨迹，研究学生言行，这些学生的言行轨迹直接或间接反映了用户的性格、习惯、态度等信息”。[2]董潇潇等描述“大学生行为画像是利用校园数据将学生行为信息标签化。” 本文将大学生画像描述成“基于以学生为中心的理念和校园大数据，根据其人口学特征、学习行为、社交活动、消费行为、思想动态、兴趣爱好等信息抽象出来并标签化的一系列学生模型集合。”1.2 大学生画像之意义 大学生画像对于高校的教学、管理和服务等方面均有着重要的指导意义和现实价值。 在课程设置方面，分析学生学业画像， 基于校园大数据构建大学生画像的技术实现 文/张海华1 郭田友2 张非3 可以帮助教学管理部门更加客观的了解学生对 大学课程的真实需求，更加科学的设置课程体系，能够精准的评价每一名学生。成都电子科技大学通过构建“学生画像”成功实现大学生学习挂科预警机制。 在学生工作方面，分析学生消费画像，可以帮助学工部门了解学生的经济和消费状况，从而设计精准、科学的帮扶机制，帮助贫困生顺利完成学业。南京大学成功将大数据技术应用于贫困生帮扶。安徽师范大学利用大数据挖掘技术为科学资助和精准资助提供了决策支持。 在毕业指导方面，分析学生职业画像，根据学生的能力模型进行职业发展轨迹推荐和“学生-企业”双向推荐，实现毕业生个人素质、求职意愿和企业岗位需求信息的“人岗精准对接”。海南师范大学利用大数据技术实现学生精准就业，提升了聘效率，拓宽学生就业渠道，有效管控就业数据。 2 大学生画像之构建 2.1 构建类别 根据大学生在校期间各项活动和数据，我们可以构建学生基础画像、学业画像、消费画像、心理画像、思想政治画像、职业画像、人格画像、评优助困画像、健康画像等一系列大学生画像集合。2.2 构建方法 构建大学生画像主要包括数据采集、数据清洗、用户建模、标签挖掘、画像聚类、可视化等工作。 数据采集按实时性分为在线采集和离线采集，其中在线采集包含个人基础数据和使用智慧校园系统发生的行为数据（如学习、消费、交流、上网等）。离线采集包括对各类系统交互日志和网络爬虫数据按照一定的算法规则进行挖掘收集。 通过数据采集得到的原始数据源存在“脏数据”，为了保证后期标签挖掘的准确性，需要进行填空、去噪、删重、修正、规范化等预处理。通过文本挖掘算法得到标签元数据和标签数据集并使之标准化，基于前述画像维度进行用户建模，并通过聚类算法对学生画像分类。 3 关键技术实现 3.1 数据处理 在进行用户建模之前，需要进行数据采集和清洗，我们选择Python 中的Sklearn 和Pandas 等模块作为数据清洗工具。 分析结构化数据的构成，我们做了如下清洗工作：通过使用常量替换、均值填充、回归预测等方法处理如考试成绩、三餐消费等缺失值、异常值问题；筛选并删除重复数据；利用分箱技术的箱体均值法处理图书借阅的噪音数据问题；通过格式转换处理数据编码和日期表示不一致问题；最后对清洗结果中同一维度的数据进行归一化和正则化处理，如家庭收入、学习成绩均处理成[0,1]之间的数字。3.2 用户建模 一个事件模型包括时间、地址、人物、内容四要素，每一次学生行为均是一次随机事件，可以描述为谁在何时何地址做何操作。因此数据模型概括为如下公式：学生标识+时间+行为类型+应用系统+内容。 学生标签的权重可能随时间增加而衰减，因此定义时间衰减因子为r ，行为类型、应用系统决定权重，内容决定了标签，可转换为公式：标签权重=衰减因子×行为权重×应用权重。 如某学生上月10日在图书馆系统查询了主题为大数据研究的论文，假设时间衰减因子公式r=1-(m-m0)*0.05（即每隔一个月衰减0.05），图书馆系统的权重为0.8，则其数据模型为： 学生学术标签为：科研，大数据，权重为(1-0.05)*0.8=0.76。 通过定义各类行为的时间衰减因子和系统以及内容权重，就可以对学生的全部行为建模。3.3 标签挖掘 标签元数据是用于描述标签分类的数据，我们将标签元数据划分为基本标签、经济标签、成绩标签、知识标签、体育标签、消费标签、饮食标签、社交标签、性格标签、心理标签、学习标签、思想标签等。 从数据提取维度来看，标签分为事实标签、模型标签和策略标签。事实标签来源于真实数据，定性描述学生的基本属性等，如家庭好、消费高、学霸。模型标签是对学生属性及行为进行抽象和聚类概况出来的，如足球迷群体、电竞迷群体。策略标签是根据学生信息和行为配合一定的规则策略设定，如可能挂科、有自杀倾向等。 在实践中，通过抓取校园论坛挖掘思想动态标签，抓取百度贴吧挖掘社交标签，分析 学习成绩设置成绩标签，分析图书借阅数据设置知识标签，分析消费行为和消费水平设置消 <<下转153页
几种聚类算法在图像分割中的应用研究
龙源期刊网 https://www.docsj.com/doc/0a17292144.html, 几种聚类算法在图像分割中的应用研究 作者：苗欣雨 来源：《科教导刊·电子版》2015年第19期 摘要本文具体介绍了图像分割中几种聚类算法的工作原理。通过对比，分析了几种算法的优缺点，总结了在实际工作中对算法的选择问题。 关键词聚类算法图像分割均值漂移 K均值聚类 中图分类号：TP391.41 文献标识码：A 通常在分析以及使用图像时，人们需要的不是整幅图像而仅仅是其中的某些目标。图像分割就是把需要的部分分割出来，再进一步分析处理图像。每个图像都有它独有的特点，对图像进行分割时要想达到预期的结果就必须选择合适的算法，由此可见对算法的研究是很关键也很必要的。目前常用的几种分割方法有k均值聚类算法、模糊c均值算法、均值漂移算法等。 1聚类算法 1.1均值漂移算法 均值漂移（Mean Shift）算法是一种有效的统计迭代算法。均值漂移的算法原理是，在样本中随机选择一圆心为o，半径为h的区域，得出这个区域中所有样本点的平均值，圆心处的样本密度必然比均值处的样本密度小或者相等，将均值定为新的圆心重复以上步骤，直到收敛到密度极大值点。 1.2 K均值聚类算法 k均值聚类由于其原理简单而使用很广泛。该算法的工作原理是，首先将n个样本分为k 个组，在每组中随机选择一个元素当作聚类中心。然后得到其他采样点到这个中心的欧氏距离，把采样点归类到与之欧氏距离最小的聚类中心所在的类中。计算新形成的聚类中采样点的平均值，得到新的聚类中心。重复上述过程，直到每个样本都分类正确为止。 1.3模糊C均值聚类算法 模糊C均值是为解决实际应用问题对K均值进行改进得来的。在实际应用中图像目标在类别属性方面没有那么严格的区分。所以想出利用隶属度来判断每个目标样本的所属，来更好的划分。模糊C均值聚类的具体工作原理是，算法将n个样本分为c个组，得到各个组的聚类中心，最终让非相似性指标的目标函数达到最小。算法给各个样本点赋予0～1之间的隶属度，通过隶属度的值来判断样本归属于各个分类的程度。同时有规定一个样本的隶属度加和后值为一。
华为HCIA人工智能试题
华为HCIA人工智能试题 1. 神经网络研究属于下列哪个学派 [单选题] * 符号主义 连接主义(正确答案) 行为主义 以上都不是 2. 以下哪个不是ModelArts开发类型 [单选题] * 零基础建模 敏捷开发(正确答案) 快速建模 标准模型开发 3. HUWEI HIAI Engine无法提供以下哪个引擎 [单选题] * NLU引擎 CV引擎 ASR引擎 DSP引擎(正确答案) 4. 关于L1正则化与L2正则化以下表述正确的是？ [单选题] * L2正则化比L1正则化产生更加稀疏的模型 L1正则项有利于增强模型的泛化能力(正确答案) 加上L2正则项后，无法使用梯度下降算法迭代参数值 L1，L2正则项不能作用在损失函数之上。
5. 池化层一般接在哪种网络层之后。 [单选题] * 输入层 输出层 卷积层(正确答案) 全连接层 6. 下列关于随机变量的分布函数，分布律，密度函数的理解描述不正确的是？ [单选题] * 离散型随机变量没有分布函数(正确答案) 密度函数只能描述连续型随机变量的取值规律。 分布函数描述随机变量的取值规律 分布律只能描述离散型随机变量的取值规律 7. 感知器在空间中可以展现为？ [单选题] * 点(正确答案) 线 平面 超平面 8. 常见的聚类算法有哪些？ [单选题] * K-means(正确答案) 谱聚类 密度聚类 层次聚类 9. 下列选项中对泊松分布与二项分布的关系描述正确的是？ [单选题] * 泊松分布可以代替二项分布
泊松分布是二项分布当n很大p很小时的近似计算(正确答案)泊松分布与二项分布的数学模型都是拉格朗日概型 泊松分布与二项分布没有关系 10. Python3中5/2的结果是？ [单选题] * 3 2 2.5(正确答案) 1 11. 人工智能现在的技术应用方向主要有 * 控制系统 语音识别(正确答案) 计算机视觉(正确答案) 自然语言处理(正确答案) 12. 以下哪些是ModelsArts开发模式 * 自定义开发(正确答案) 迭代学习 数据标注(正确答案) 自动学习(正确答案) 13. tf.keras.preprocessing的作用是？ [单选题] * keras模型部署工具 keras数据处理工具(正确答案) Keras生成模型工具 Keras内置优化器
聚类算法分析
课程名称：数据挖掘 实验项目：聚类算法分析研究班级： 学号： 学生姓名：
聚类算法分析研究 1 实验环境以及所用到的主要软件 Windows Vista NetBeans6.5.1 Weka3.6 MATLAB R2009a 2 实验内容描述 聚类是对数据对象进行划分的一种过程，与分类不同的是，它所划分的类是未知的，故此，这是一个“无指导的学习” 过程，它倾向于数据的自然划分。其中聚类算法常见的有基于层次方法、基于划分方法、基于密度以及网格等方法。本文中对近年来聚类算法的研究现状与新进展进行归纳总结。一方面对近年来提出的较有代表性的聚类算法，从算法思想。关键技术和优缺点等方面进行分析概括；另一方面选择一些典型的聚类算法和一些知名的数据集，主要从正确率和运行效率两个方面进行模拟实验，并分别就同一种聚类算法、不同的数据集以及同一个数据集、不同的聚类算法的聚类情况进行对比分析。最后通过综合上述两方面信息给出聚类分析的研究热点、难点、不足和有待解决的一些问题等。 实验中主要选择了K 均值聚类算法、FCM 模糊聚类算法并以UCI Machine Learning Repository 网站下载的IRIS 和WINE 数据集为基础通过MATLAB 实现对上述算法的实验测试。然后以WINE 数据集在学习了解Weka 软件接口方面的基础后作聚类分析，使用最常见的K 均值（即K-means ）聚类算法和FCM 模糊聚类算法。下面简单描述一下K 均值聚类的步骤。 K 均值算法首先随机的指定K 个类中心。然后： （1）将每个实例分配到距它最近的类中心，得到K 个类； （2）计分别计算各类中所有实例的均值，把它们作为各类新的类中心。 重复（1）和（2），直到K 个类中心的位置都固定，类的分配也固定。 在实验过程中通过利用Weka 软件中提供的simpleKmeans （也就是K 均值聚类算法对WINE 数据集进行聚类分析，更深刻的理解k 均值算法，并通过对实验结果进行观察分析，找出实验中所存在的问题。然后再在学习了解Weka 软件接口方面的基础上对Weka 软件进行一定的扩展以加入新的聚类算法来实现基于Weka 平台的聚类分析。 3 实验过程 3.1 K 均值聚类算法 3.1.1 K 均值聚类算法理论 K 均值算法是一种硬划分方法，简单流行但其也存在一些问题诸如其划分结果并不一定完全可信。K 均值算法的划分理论基础是 2 1 min i c k i k A i x v ∈=-∑∑ （1） 其中c 是划分的聚类数，i A 是已经属于第i 类的数据集i v 是相应的点到第i 类的平均距离，即