改进的支持向量聚类算法及其应用研究

发布时间：2017-10-11 21:33

  本文关键词：改进的支持向量聚类算法及其应用研究

  更多相关文章： 支持向量聚类 最小闭包球 邻接矩阵 文本聚类 主成分分析

【摘要】： 21世纪是知识经济时代,知识发现已受到日益广泛的关注。聚类分析是知识发现中一个极为重要的分支,几乎可用于社会生活的各个方面。而核聚类算法由于具有许多经典聚类算法无法比拟的优势,逐渐成为聚类算法研究领域的一大热点。本文主要研究的支持向量聚类(Support Vector Clustering, SVC)算法就是一种典型的核聚类算法。 与其他聚类算法相比,SVC算法具有两大显著优势：一是不需要事先确定簇的数目,且能产生任意形状的簇边界；二是能分析噪声数据点且能分离相互交错的簇。SVC算法分为两个阶段：SVC训练阶段和聚类分配阶段。这两个阶段分别需要计算Lagrange乘子和邻接矩阵,而这两个计算问题可能导致算法具有较高的时间复杂性。正是针对这两个问题,本文提出一种改进的SVC (Improved SVC, ISVC)算法。 在SVC训练阶段,提出一种基于熵的最小闭包球(Minimal Enclosing Sphere, MES)算法。可以证明,这种方法能有效减少计算Lagrange乘子的时间。在聚类分配阶段,首先利用核矩阵提供的信息对数据点进行初始分类,然后用计算初始类的中心点集上的邻接矩阵代替经典SVC算法中计算整个数据集上的邻接矩阵。这种方法能有效减少邻接矩阵的规模,从而提高邻接矩阵的计算效率。因此,ISVC算法对经典SVC算法的两个瓶颈问题都进行了改进。数值实验表明,ISVC算法不仅显著改善了经典SVC算法的时间性能,在聚类精度上也有一定程度的提高。 之后将ISVC算法应用于文本聚类。选择复旦大学整理的小规模语料库中的100篇文本进行实验。首先对实验文本集进行预处理,依次为：切分文本集；利用向量空间模型(Vector Space Model, VSM)将切分后的文本集表示成矩阵形式；利用主成分分析(Principal Component Analysis, PCA)技术对文本集进行降维。然后利用ISVC算法将预处理后的文本数据聚类,并对聚类结果进行描述。最后对比了ISVC、k-均值和层次聚类中的凝聚算法(DHCA)三种算法在实验文本集上的聚类结果,发现ISVC算法具有较高的精度。这说明本文的ISVC算法在一定程度上提高了文本聚类的效率。
【关键词】：支持向量聚类 最小闭包球 邻接矩阵 文本聚类 主成分分析
【学位授予单位】：大连理工大学
【学位级别】：硕士
【学位授予年份】：2010
【分类号】：F062.3;F224
【目录】：

• 摘要4-5
• Abstract5-9
• 1 绪论9-18
• 1.1 问题提出9-10
• 1.2 国内外研究现状10-16
• 1.2.1 核聚类算法的国内外研究现状10-15
• 1.2.2 文本聚类算法的国内外研究现状15-16
• 1.3 研究内容及思路16
• 1.4 内容安排16-18
• 2 支持向量机简介18-26
• 2.1 支持向量分类和回归简介18-22
• 2.1.1 结构风险最小化原则18-19
• 2.1.2 支持向量分类简介19-21
• 2.1.3 支持向量回归简介21-22
• 2.2 支持向量聚类算法简介22-26
• 2.2.1 SVC训练23-24
• 2.2.2 聚类分配24
• 2.2.3 SVC算法评价24-26
• 3 ISVC算法及数值实验26-38
• 3.1 ISVC算法26-34
• 3.1.1 SVC训练26-29
• 3.1.2 聚类分配29-31
• 3.1.3 ISVC算法的具体步骤31-32
• 3.1.4 ISVC算法的复杂性32-34
• 3.2 数值实验34-38
• 3.2.1 ISVC算法与经典SVC算法的比较34-37
• 3.2.2 ISVC算法与经典聚类算法的比较37-38
• 4 ISVC算法应用于文本聚类38-49
• 4.1 实验数据与环境38
• 4.2 实验设计38-48
• 4.2.1 文本预处理39-45
• 4.2.2 实验结果描述及评价45-48
• 4.3 与经典文本聚类算法的比较48-49
• 结论49-51
• 参考文献51-54
• 攻读硕士学位期间发表学术论文情况54
• 攻读硕士学位期间参加科研项目情况54-55
• 致谢55-57

【参考文献】

中国期刊全文数据库 前9条

1 纪秋颖;林健;;基于核方法的聚类算法及其应用[J];北京航空航天大学学报;2006年06期

2 吕佳;;核聚类算法及其在模式识别中的应用[J];重庆师范大学学报(自然科学版);2006年01期

3 郭崇慧,陆玉昌;预测型数据挖掘中的优化方法[J];工程数学学报;2005年01期

4 张胜;;数据挖掘中聚类算法的研究[J];软件导刊;2008年06期

5 孙德山;李海清;;基于线性规划的支持向量聚类算法[J];计算机工程与设计;2010年06期

6 伍忠东,高新波,谢维信;基于核方法的模糊聚类算法[J];西安电子科技大学学报;2004年04期

7 王英奇;;支持向量聚类算法的研究与改进[J];湛江师范学院学报;2008年06期

8 刘务华;罗铁坚;王文杰;;文本聚类算法的质量评价[J];中国科学院研究生院学报;2006年05期

9 王书舟;伞冶;;支持向量机的训练算法综述[J];智能系统学报;2008年06期

中国硕士学位论文全文数据库 前2条

1 周昭涛;文本聚类分析效果评价及文本表示研究[D];中国科学院研究生院（计算技术研究所）;2005年

2 姚清耘;基于向量空间模型的中文文本聚类方法的研究[D];上海交通大学;2008年

，

本文编号：1014877