最小生成树平滑支持向量机聚类算法研究及其应用

《最小生成树平滑支持向量机聚类算法研究及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、厦门大学硕士学位论文最小生成树平滑支持向量机聚类算法研究及其应用姓名：耿代申请学位级别：硕士专业：模式识别与智能系统指导教师：米红20070601摘要支持向量机(SupportVectorMachines，SVM)是在统计学习理论基础上发展起来的一种新的模式识别方法，近年来在其理论研究和算法实现方面取得了突破性进展。SVM聚类方法是一种新的聚类算法，它利用核函数，通过映射把输入空间的样本点映射到高维特征空间中进行处理。其方法在性能上比经典算法有较大的改进，但传统SVM算法随着数据集的增加其时间复杂度呈指数级增加，如何减少该算法的时间复杂度从而应用于实际数据挖掘问题，正

2、是现在研究的热点。本fJ文针对支持向量机的聚类方法进行了研究，提出了最小生成树平滑支持向量机的算法。本文所做的工作主要是：首先，通过支持向量求解算法的分析，结合聚类的特性，提出了将平滑技术引入聚类支持向量点求解的改进算法。该方法通过加入惩罚函数，将有约束的二次优化问题转变为无约束的优化问题，从而利用传统方法进行求解，算法在有效地保持求解支持向量精度的同时，大大提高算法的性能，节省了存储空间，使求解过程的时间复杂度大为减少。实验验证了该算法能够进一步降低优化时间。其次，对支持向量机聚类的标识方法和最小生成树聚类进行了研究，提出将最小生成树应用于聚类标识的方法。该方法通过

3、分析高维聚类数据分布特征改进了距离表达方法，更加合理地体现了特征空间内点的相似程度，使各类样本之间差别增大，增加了聚类的可靠性。此外，最小生成树的聚类标识大大减少了算法的时间度，实验结果表明该算法与其它方法相比，过程更加简单，所用时间更少。再次，将以上两种算法结合，提出了一种新的聚类算法MST-SSVC，通过实验对算法参数做出了分析，与传统算法及支持向量机改进算法的比较表明该算法大大简化了时间复杂度，同时精度基本不变，使得支持向量机聚类算法对实际大数据集的处理成为可能。。最后，首次将该方法应用于社会养老保险个人调查数据的聚类分析中，取得了一些有意义的结果，表明利用该算

4、法应用于数据挖掘是可行的。’关键词：聚类；平滑支持向量机；最小生成树。本文获国家社科基金项目“农村社会养老保障制度的基础框架研究”(批准号：05BSH049)支持。AbstractSupportVectorMachines(SVM)isanewmethodologyforpatternrecognition，whichisbasedonstatisticlearningtheory．Recentlyitstheoreticalresearchandalgorithmhaveagreatestdevelopment．SupportVectorClustering(SVC

5、)isanovelclusteringmethod，whichmapsthesamplesfrominputspacetohighdimensionfeaturespaceviakernelfunctions．Althoughitsperformancehasbeenimprovedcomparedwithotheralgorithms，thetimecomplexityofconventionalSVMincreasesexponentiallywhilethedatasetincreasing．SoitisthefocudofresearchtOdecreaset

6、hetimecomplexitySOastouseitasdataminingt001．ThispaperresearchesthemethodologyofSVC，andputsforwardanovelSVC：MinimumSpanningTreesSmoothingSupportVectorMachine．Themainworksofthispaperare：First，throughanalysisofthealgorithmforsearchingsupportvectorandthefeatureofclustering，animprovedalgorit

7、hmisbroughtforwardwhichcontainsthesmoothingmethodforsearchingsupportvector．Thisalgorithmchangestherestrictedquadraticoptimizationtonon—restrictedoptimizationSOthatitcanbesolvedbyconventionalmethods．Itcouldimprovetheperformancegreatly，savestoragespaceanddecreasethetimecomplexity