算法最好的空间

软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,2014,25(9):20372049[doi:10.
13328/j.
cnki.
jos.
004643]http://www.
jos.
org.
cn中国科学院软件研究所版权所有.
Tel/Fax:+86-10-62562563基于自适应Nystrm采样的大数据谱聚类算法丁世飞1,2,贾洪杰1,2,史忠植21(中国矿业大学计算机科学与技术学院,江苏徐州221116)2(中国科学院计算技术研究所智能信息处理重点实验室,北京100190)通讯作者:丁世飞,E-mail:dingsf@cumt.
edu.
cn摘要:面对结构复杂的数据集,谱聚类是一种灵活而有效的聚类方法,它基于谱图理论,通过将数据点映射到一个由特征向量构成的低维空间,优化数据的结构,得到令人满意的聚类结果.
但在谱聚类的过程中,特征分解的计算复杂度通常为O(n3),限制了谱聚类算法在大数据中的应用.
Nystrm扩展方法利用数据集中的部分抽样点,进行近似计算,逼近真实的特征空间,可以有效降低计算复杂度,为大数据谱聚类算法提供了新思路.
抽样策略的选择对Nystrm扩展技术至关重要,设计了一种自适应的Nystrm采样方法,每个数据点的抽样概率都会在一次采样完成后及时更新,而且从理论上证明了抽样误差会随着采样次数的增加呈指数下降.
基于自适应的Nystrm采样方法,提出一种适用于大数据的谱聚类算法,并对该算法的可行性和有效性进行了实验验证.

关键词:大数据;谱聚类;特征分解;Nystrm扩展;自适应采样中图法分类号:TP181中文引用格式:丁世飞,贾洪杰,史忠植.
基于自适应Nystrm采样的大数据谱聚类算法.
软件学报,2014,25(9):20372049.
http://www.
jos.
org.
cn/1000-9825/4643.
htm英文引用格式:DingSF,JiaHJ,ShiZZ.
SpectralclusteringalgorithmbasedonadaptiveNystrmsamplingforbigdataanalysis.
RuanJianXueBao/JournalofSoftware,2014,25(9):20372049(inChinese).
http://www.
jos.
org.
cn/1000-9825/4643.
htmSpectralClusteringAlgorithmBasedonAdaptiveNystrmSamplingforBigDataAnalysisDINGShi-Fei1,2,JIAHong-Jie1,2,SHIZhong-Zhi21(SchoolofComputerScienceandTechnology,ChinaUniversityofMiningandTechnology,Xuzhou221116,China)2(KeyLaboratoryofIntelligentInformationProcessing,InstituteofComputingTechnology,TheChineseAcademyofSciences,Beijing100190,China)Correspondingauthor:DINGShi-Fei,E-mail:dingsf@cumt.
edu.
cnAbstract:Spectralclusteringisaflexibleandeffectiveclusteringmethodforcomplexstructuredatasets.
Itisbasedonspectralgraphtheoryandcanproducesatisfactoryclusteringresultsbymappingthedatapointsintoalow-dimensionalspaceconstitutedbyeigenvectorssothatthedatastructureisoptimized.
Butintheprocessofspectralclustering,thecomputationalcomplexityofeigen-decompositionisusuallyO(n3),whichlimitstheapplicationofspectralclusteringalgorithminbigdataproblems.
Nystrmextensionmethodusespartialpointssampledfromthedatasetandapproximatecalculationtosimulatetherealeigenspace.
Inthisway,thecomputationalcomplexitycanbeeffectivelyreduced,whichprovidesanewideaforbigdataspectralclusteringalgorithm.
TheselectionofsamplingstrategyisessentialforNystrmextensiontechnology.
Inthispaper,thedesignofanadaptiveNystrmsamplingmethodispresented.
Thesamplingprobabilityofeverydatapointwillbeupdatedaftereachsamplingpass,andaproofisgiventhatthesamplingerrorwilldecreaseexponentiallywiththeincreaseofsampletimes.
BasedontheadaptiveNystrmsamplingmethod,aspectralclusteringalgorithmforbigdataanalysisispresented,anditsfeasibilityandeffectivenessisverifiedbyexperiments.
Keywords:bigdata;spectralclustering;eigen-decomposition;Nystrmextension;adaptivesampling基金项目:国家重点基础研究发展计划(973)(2013CB329502);国家自然科学基金(61379101)收稿时间:2014-04-07;定稿时间:2014-05-142038JournalofSoftware软件学报Vol.
25,No.
9,September2014聚类学习是一种重要的数据分析技术.
为了从纷繁复杂的数据中发现有用的信息,可以先对数据进行聚类,根据数据对象的相关特征,将相似的对象归到同一类里,而差别较大的对象划分到不同类中,找到数据之间的内在联系,为决策提供支持[1].
谱聚类是聚类分析中十分热门的研究领域,与传统的聚类算法(如k-means,FCM)相比,其优势在于:谱聚类算法可以很好地处理非凸形结构的数据集,得到比较满意的聚类结果[2].
谱聚类的背后有着坚实的理论基础,它用图划分的思想处理数据聚类问题,为了得到最优的子图划分,引入拉普拉斯矩阵并对其特征分解,利用特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.