文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > A MinMaxCut Spectral Method for Data Clustering and Graph Partitioning
侵权投诉

A MinMaxCut Spectral Method for Data Clustering and Graph Partitioning

A MinMaxCut Spectral Method for Data Clustering and Graph Partitioning

In§4,thedivisiveMinMaxCutasaK-wayclusteringmethodisexplainedindetail.We rstprovethemono-tonicityofMinMaxCutandK-meansobjectivefunctionw.r.t.toclustermergingandsplitingin§4.1.In§4.2,weoutlinetheclusterselectionmethods:thosebasedonthesize-priority,averagesimilarity,cohesionandtemporaryobjectives.Stoppingcriteriaareoutlinedin§4.3.In§4.4,wediscussobjectivefunctionsaturation,asubtleissueinobjectivefunctionoptimizationbasedapproaches.In§4.5,resultsofcomprehensiveexperimentsonnewsgrouparepresentedwhichshowtheaveragesimilarityasabetterclusterselectionmethod.OurresultsalsoshowtheimportanceofMinMaxCutbasedre nementaftertheinitialclustersareobtainedinthedivisiveclustering.ThisindicatestheappropriatenessoftheMinMaxCutobjectivefunction.In§5,summaryanddiscussionsresultsaregiven.Somepreliminaryresults[10,8]ofthispaperwerepreviouslyrepresentedinconferences.

2Two-wayMinMaxCut

Givenpairwisesimilaritiesorassociationsforasetofndataobjectsspeci edinS=(sij),wewishtoclusterthedataobjectsintotwoclustersA,Bbasedonthefollowingmin-maxclusteringprinciple:datapointsaregroupedintoclusterssuchthatbetween-clusterassociationsareminimizedwhilewithin-clusterassociationsaremaximized.TheassociationbetweenA,Bisthesumofpairwiseassociationsbetweenthetwoclusters,s(A,B)= s.TheassociationwithinclusterAiss(A,A)=i∈A,j∈Biji∈A,j∈Asij;s(B,B)isanalogouslyde ned.Themin-maxclusteringprinciplerequires

mins(A,B),maxs(A,A),maxs(B,B).(1)

Theserequirementsaresimultaneouslysatis edbyminimizingtheobjectivefunction[10],

JMMC=s(A,B)s(B,B).(2)

NotethattherearemanyobjectivefunctionsthatsatisfyEq.(1).However,forJMMC,acontinuoussolutionscan

becomputede ciently.

Clusteringsolutioncanberepresentedbyanindicatorvectorq,

aifi∈Aqi=, bifi∈B

wherea= dA/dB,

dA=

sijisthedegreeofnodei.Thus

qTDe=0,(5) i∈Aj(3)di,dB=anddi= i∈Bdi,(4)

whereD=diag(d1,···,dn).We rstprovethat

minJMMC(A,B)= maxJm(q),Jm(q)=qqqTSq

2)2

上一页第3页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email