文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 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

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

第1页

你可能喜欢

热门文档

相关文档

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