文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Generative model-based clustering of directional data
侵权投诉

Generative model-based clustering of directional data

High dimensional directional data is becoming increasingly important in contemporary applications such as analysis of text and gene-expression data. A natural model for multivariate directional data is provided by the von Mises-Fisher (vMF) distribution on

GenerativeModel-basedClusteringofDirectionalData

ArindamBanerjee

InderjitDhillon

UniversityDeptofAustin,TX,ofECETexasUSA

UniversityDeptofAustin,TX,ofCSTexasUSAabanerje@ece.utexas.edu

inderjit@cs.utexas.edu

HighABSTRACT

dimensionaldirectionaldataisbecomingincreasinglyimportantincontemporaryapplicationssuchasanalysisoftextandgene-expressiondata.Anaturalmodelformulti-variatedirectionaldataisprovidedbythevonMises-Fisher(vMF)distributionontheunithyperspherethatisdanal-ogoustothemulti-variateGaussiandistributioninR.Inthispaper,weproposemodelingcomplexdirectionaldataasamixtureofvMFdistributions.WederiveandanalyzetwovariantsoftheExpectationMaximization(EM)frameworkforestimatingtheparametersofthismixture.Wealsopro-posetwoclusteringalgorithmscorrespondingtothesevari-ants.Aninterestingaspectofourmethodologyisthatthesphericalkmeansalgorithm(kmeanswithcosinesimilarity)canbeshowntobeaspecialcaseofbothouralgorithms.Thus,modelingtextdatabyvMFdistributionslendstheo-reticalvaliditytotheuseofcosinesimilaritywhichhasbeenwidelyusedbytheinformationretrievalcommunity.Aspartofexperimentalvalidation,wepresentresultsonmodelinghigh-dimensionaltextandgene-expressiondataasamix-tureofvMFdistributions.Theresultsindicatethatourapproachyieldssuperiorclusteringsespeciallyfordi cultclusteringtasksinhigh-dimensionalspaces.

H.3.3Categories[InformationandSubjectStorageDescriptors

andRetrieval]:Informa-tionSearchandRetrieval;I.5.3[PatternRecognition]:Clustering

Clustering,Keywords

directionaldata,mixtures,vonMises-Fisher,EM

Clustering1.INTRODUCTION

orsegmentationofdataisafundamentaldataanalysisstepthathasbeenwidelystudiedacrossvariousdis-ciplines[19].However,severallargedatasetsthatarebeingacquiredfromscienti cdomains,aswellastheworldwideweb,haveavarietyofcomplexcharacteristicsthatseverelychallengetraditionalmethodsforclustering[15].Thisar-ticleisconcernedwiththeclusteringofhigh-dimensional

Permissionpersonaltomakedigitalorhardcopiesofallornotbearmadeororclassroomdistributeduseforispro tgrantedorcommercialwithoutfeeprovidedpartofthatthiscopiesworkforarerepublish,thisnoticepermissiontopostandontheserversfullcitationoronthe rstpage.advantageTocopyandotherwise,thatcopiesorDC,USA.Copyrightand/orafee.2003SIGKDDtoredistributetolists,requirespriorspeci cACM1-58113-737-0/03/0008...’03,August24-27,2003,$5.00.

Washington,JoydeepGhosh

SuvritSra

UniversityDeptofofECETexasUniversityDeptofCSAustin,TX,USAAustin,TX,ofTexasUSAghosh@ece.utexas.edu

suvrit@cs.utexas.edu

directionaldatathatisbecomingincreasinglycommoninseveralapplicationdomains.

Onecanbroadlycategorizeclusteringapproachesintogener-ative(parametric)[29,18]anddiscriminative(non-parametric)[17,27]ones.Theperformanceofanapproach(andofaspe-ci cmethodwithinthatapproach)isquitedatadependent;thereisnoclusteringmethodthatworksthebestacrossalltypesofdata.Generativemodels,however,oftenpro-videbetterinsightintothenatureoftheclusters.Fromanapplicationpointofview,alotofdomainknowledgecanbeincorporatedintogenerativemodelssothatclusteringofdatauncoversspeci cdesirablepatternsthatoneislook-ingfor.Clusteringalgorithmsusingthegenerativemodelframework,ofteninvolveanappropriateapplicationoftheExpectationMaximization(EM)algorithm[8,5]onaprop-erlychosenstatisticalgenerativemodelforthedataunderconsideration.Forvectordata,therearewellstudiedclus-teringalgorithmsforpopulargenerativemodelssuchasamixtureofGaussians,whosee ectisanalogoustotheuseofEuclideanorMahalanobistypedistancesfromthedis-criminativeperspective.

There1.1areMotivationseveralapplicationandRelateddomainsWork

whereclusteringbasedonminimizingEuclideandistortionsyieldspoorresults[30].Forexample,empiricalstudiesininformationretrievalap-plicationsshowthatcosinesimilarityisafarmoree ectivemeasureofsimilarityforanalyzingandclusteringtextdocu-ments.Suchdomainsrequiretheuseofdirectionaldata[22]—datathatdealsonlywiththedirectionsofunitvectors.Thus,thereisaneedforgenerativemodelsthataremoreap-propriatefortheanalysisandclusteringofdirectionaldata.Inthisarticle,weproposeagenerativemixturemodelfordirectionaldataontheunithypersphereandderivetwoclus-teringalgorithmsusingthismixturemodel.Weshowtheconnectionbetweentheproposedalgorithmsandaclassofexistingalgorithmsforclusteringhigh-dimensional,direc-tionaldataandpresentdetailedexperimentalcomparisonsamongthem.

Asalreadymentioed,oneimportantdomainwheredirec-tionaldataisencounteredistextanalysis,andtextclus-teringinparticular.Ithasbeenexperimentallyshownthatinordertoremovethebiasarisingduetothelengthofadocument,itoftenhelpstonormalizethedatavectors[11].Further,thespkmeansalgorithm[11],thatperformskmeansusingcosinesimilarityinsteadofEuclideandistortion,hasbeenfoundtoempiricallyoutperformseveralotherschemes.

第1页

你可能喜欢

热门文档

相关文档

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