近似谱聚类算法描述(3).docx资源-CSDN文库

版权申诉

82 浏览量 2022-11-12 14:24:28 上传评论收藏 90KB DOCX 举报

资源推荐

资源详情

资源评论

二、近似谱聚类算法描述

本节论文阐述基于相似矩阵稀疏化方法稀疏化后离群点的优化处理，并将该处理步骤应用

于谱聚类算法中。基于上述分析近似谱聚类算法整体流程总结描述如表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 并行实验对

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余8页未读，立即下载

内容反馈

版权申诉

คิดถึง643

粉丝: 3901
资源: 1万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip