A MinMaxCut Spectral Method for Data Clustering and Graph Partitioning
AMinMaxCutSpectralMethodforDataClusteringandGraph
Partitioning
ChrisDinga,XiaofengHea,HongyuanZhab,MingGuc,HorstD.Simona
aLawrenceBerkeleyNationalLaboratory
UniversityofCalifornia,Berkeley,CA94720
bDepartmentofComputerScienceandEngineering
PennsylvaniaStateUniversity,UniversityPark,PA16802
cDepartmentofMathematics
UniversityofCalifornia,Berkeley,CA94720
{chqding,xhe,hdsimon}@lbl.gov,zha@cse.psu.edu,mgu@math.berkeley.edu
LBNLTechReport#54111.December1,2003
Abstract
Thegoalofdataclusteringcanbeformallystatedasamin-maxclusteringprinciple:datapointsaregroupedintoclusterssuchthat(a)between-clustersimilaritiesareminimizedwhile(b)within-clustersimilar-itiesaremaximized.Existingmethodstypicallyfocusononeoftheaboverequirements.Hereweproposeanewmethodthatemphasizesbothrequirementssimultaneously.TheMinMaxCutmethodusespairwisesimi-laritiesbetweenalldataobjects.Viewingthemastheadjacencymatrixofaweightedgraph,MinMaxCutisagraphpartitioningmethod.AnimportantfeatureisthatthecontinuoussolutionoftheclustermembershipindicatorvectoristheeigenvectorofthegeneralizedgraphLaplacianmatrix;thissimpli estheoptimizationofthemin-maxclusteringobjectivefunction.Weprovideacomprehensiveanalysisofthisprincipledclusteringmethod;asystematicevaluationonclusteringexperimentsonInternetnewsgroupsindicatesthatMinMaxCutoutperformsothercurrentpopularpartitioning/clusteringmethods.
1Introduction
Dataclustering,alsocalledclusteranalysis,isanactiveresearchareawithalonghistory(see[21,24,14,23]),fromtheK-meansmethods[25,26,22]andhierarchicalclusteringalgorithmsin1960s-1970stothepresent-daymorecomplexmethodssuchasthosebasedonGaussianmixtures[28]andothermodel-basedmethods[1],graphpartitioningmethods[31,19,32,29],andmethodsdevelopedbythedatabasecommunity(seethesummaryin
[20]).
Theessentialtaskofdataclusteringispartitioningdatapointsintodisjointclusterssothat(P1)objectsinthesameclusteraresimilar,(P2)objectsindi erentclustersaredissimilar.Whendataobjectsdistributeascompactclumpswhicharewellseparated,clustersarewellde nedandwerefertothosewell-de nedclustersasnaturalclusters,Whentheclumpsarenotcompactorwhenclumpsoverlapwitheachother,clustersarenotwellde ned;aclearandmeaningfulde nitionofclustersthenbecomescrucial.
Existingclusteringmethodstypicallyattempttosatisfyoneofthetworequirementsabove.K-meansalgo-rithm,forexample,attemptstoensurethatdatapointinthesameclusteraresimilarwhichis(P1),whilethe
Bipartite graph partitio... 暂无评价 8页 免费 A MinMaxCut Spectral Met..... Co-clustering documents and words using bipartite spectral graph partitioning ...
实际上是把原来求离散 Desent Method 图1 它所对应...《A Tutorial on Spectral Clustering》、《Data ...《Spectral and Isoperimetric Graph Partitioning》 3...
Bipartite graph partitio... 暂无评价 8页 免费 A MinMaxCut Spectral Met.....)Co-clustering documents and words using bipartite spectral graph partitioning...
Bipartite graph partitio... 暂无评价 8页 免费 A MinMaxCut Spectral Met..... Co-clustering documents and words using Bipartite Spectral Graph Partitioning ...
A MinMaxCut Spectral Met... 暂无评价 22页 免费 A Graph Partitioning Heu...The use of clustering is especially noticeable in the DSP market, including...
A MinMaxCut Spectral Met... 暂无评价 22页 免费 Co-clustering documents ....partitioning data Based on relatively “old” results Recently surged in ...
Spectral Clustering Royi Itzhak Spectral Clustering ...0 The relaxation method is for each vector on ...Clustering as a graph partitioning problem – ...
A MinMaxCut Spectral Met... 暂无评价 22页 ...method, is applied to cluster data points in ...clustering problem into a graph partitioning problem...
method for high dimensional data clustering (...Clustering Partitioning based Clustering partition the...Clustering Techniques mixer() random graph ...
A MinMaxCut Spectral Met... 暂无评价 22页 免费 Co-clustering documents .... Spectral partitioning Th... 23页 免费 Spectral Relaxation for ... 8页 ...
热门文档