近似谱聚类算法描述 (2).pdf
版权申诉
39 浏览量
2022-11-12
14:24:57
上传
评论
收藏 328KB PDF 举报
二、近似谱聚类算法描述
本节论文阐述基于 相似矩阵稀疏化方法稀疏化后离群点的优化处理，并将该处理步骤应用
于谱聚类算法中。基于上述分析近似谱聚类算法整体流程总结描述如表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 并行实验对
资源评论
