File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Clustering uncertain data using voronoi diagrams

TitleClustering uncertain data using voronoi diagrams
Authors
Issue Date2008
Citation
Proceedings - Ieee International Conference On Data Mining, Icdm, 2008, p. 333-342 How to Cite?
AbstractWe study the problem of clustering uncertain objects whose locations are described by probability density functions (pdf). We show that the UK-means algorithm, which generalises the k-means algorithm to handle uncertain objects, is very inefficient. The inefficiency comes from the fact that UK-means computes expected distances (ED) between objects and cluster representatives. For arbitrary pdf 's, expected distances are computed by numerical integrations, which are costly operations. We propose pruning techniques that are based on Voronoi diagrams to reduce the number of expected distance calculation. These techniques are analytically proven to be more effective than the basic bounding-box-based technique previous known in the literature.We conduct experiments to evaluate the effectiveness of our pruning techniques and to show that our techniques significantly outperform previous methods. ©2008 IEEE.
DescriptionIEEE International Conference on Data Mining (ICDM 2008), Pisa, Italy
Persistent Identifierhttp://hdl.handle.net/10722/61177
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorKao, Ben_HK
dc.contributor.authorLee, SDen_HK
dc.contributor.authorCheung, DWen_HK
dc.contributor.authorHo, WSen_HK
dc.contributor.authorChan, KFen_HK
dc.date.accessioned2010-07-13T03:32:34Z-
dc.date.available2010-07-13T03:32:34Z-
dc.date.issued2008en_HK
dc.identifier.citationProceedings - Ieee International Conference On Data Mining, Icdm, 2008, p. 333-342en_HK
dc.identifier.issn1550-4786en_HK
dc.identifier.urihttp://hdl.handle.net/10722/61177-
dc.descriptionIEEE International Conference on Data Mining (ICDM 2008), Pisa, Italyen_HK
dc.description.abstractWe study the problem of clustering uncertain objects whose locations are described by probability density functions (pdf). We show that the UK-means algorithm, which generalises the k-means algorithm to handle uncertain objects, is very inefficient. The inefficiency comes from the fact that UK-means computes expected distances (ED) between objects and cluster representatives. For arbitrary pdf 's, expected distances are computed by numerical integrations, which are costly operations. We propose pruning techniques that are based on Voronoi diagrams to reduce the number of expected distance calculation. These techniques are analytically proven to be more effective than the basic bounding-box-based technique previous known in the literature.We conduct experiments to evaluate the effectiveness of our pruning techniques and to show that our techniques significantly outperform previous methods. ©2008 IEEE.en_HK
dc.languageengen_HK
dc.relation.ispartofProceedings - IEEE International Conference on Data Mining, ICDMen_HK
dc.titleClustering uncertain data using voronoi diagramsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailKao, B: kao@cs.hku.hken_HK
dc.identifier.emailCheung, DW: dcheung@cs.hku.hken_HK
dc.identifier.emailHo, WS: wsho@cs.hku.hken_HK
dc.identifier.authorityKao, B=rp00123en_HK
dc.identifier.authorityCheung, DW=rp00101en_HK
dc.identifier.authorityHo, WS=rp01730en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1109/ICDM.2008.31en_HK
dc.identifier.scopuseid_2-s2.0-67049133467en_HK
dc.identifier.hkuros151813en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-67049133467&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage333en_HK
dc.identifier.epage342en_HK
dc.identifier.scopusauthoridKao, B=35221592600en_HK
dc.identifier.scopusauthoridLee, SD=7601400741en_HK
dc.identifier.scopusauthoridCheung, DW=34567902600en_HK
dc.identifier.scopusauthoridHo, WS=7402968940en_HK
dc.identifier.scopusauthoridChan, KF=36915734900en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats