File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Metric and trigonometric pruning for clustering of uncertain data in 2D geometric space

TitleMetric and trigonometric pruning for clustering of uncertain data in 2D geometric space
Authors
KeywordsClustering
Data uncertainty
Issue Date2011
PublisherPergamon. The Journal's web site is located at http://www.elsevier.com/locate/is
Citation
Information Systems, 2011, v. 36 n. 2, p. 476-497 How to Cite?
AbstractWe study the problem of clustering data objects with location uncertainty. In our model, a data object is represented by an uncertainty region over which a probability density function (pdf) is defined. One method to cluster such uncertain objects is to apply the UK-means algorithm [1], an extension of the traditional K-means algorithm, which assigns each object to the cluster whose representative has the smallest expected distance from it. For arbitrary pdf, calculating the expected distance between an object and a cluster representative requires expensive integration of the pdf. We study two pruning methods: pre-computation (PC) and cluster shift (CS) that can significantly reduce the number of integrations computed. Both pruning methods rely on good bounding techniques. We propose and evaluate two such techniques that are based on metric properties (Met) and trigonometry (Tri). Our experimental results show that Tri offers a very high pruning power. In some cases, more than 99.9% of the expected distance calculations are pruned. This results in a very efficient clustering algorithm. 1. © 2010 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/136224
ISSN
2015 Impact Factor: 1.832
2015 SCImago Journal Rankings: 1.202
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorNgai, WKen_HK
dc.contributor.authorKao, Ben_HK
dc.contributor.authorCheng, Ren_HK
dc.contributor.authorChau, Men_HK
dc.contributor.authorLee, SDen_HK
dc.contributor.authorCheung, DWen_HK
dc.contributor.authorYip, KYen_HK
dc.date.accessioned2011-07-27T02:05:01Z-
dc.date.available2011-07-27T02:05:01Z-
dc.date.issued2011en_HK
dc.identifier.citationInformation Systems, 2011, v. 36 n. 2, p. 476-497en_HK
dc.identifier.issn0306-4379en_HK
dc.identifier.urihttp://hdl.handle.net/10722/136224-
dc.description.abstractWe study the problem of clustering data objects with location uncertainty. In our model, a data object is represented by an uncertainty region over which a probability density function (pdf) is defined. One method to cluster such uncertain objects is to apply the UK-means algorithm [1], an extension of the traditional K-means algorithm, which assigns each object to the cluster whose representative has the smallest expected distance from it. For arbitrary pdf, calculating the expected distance between an object and a cluster representative requires expensive integration of the pdf. We study two pruning methods: pre-computation (PC) and cluster shift (CS) that can significantly reduce the number of integrations computed. Both pruning methods rely on good bounding techniques. We propose and evaluate two such techniques that are based on metric properties (Met) and trigonometry (Tri). Our experimental results show that Tri offers a very high pruning power. In some cases, more than 99.9% of the expected distance calculations are pruned. This results in a very efficient clustering algorithm. 1. © 2010 Elsevier B.V. All rights reserved.en_HK
dc.languageengen_US
dc.publisherPergamon. The Journal's web site is located at http://www.elsevier.com/locate/isen_HK
dc.relation.ispartofInformation Systemsen_HK
dc.subjectClusteringen_HK
dc.subjectData uncertaintyen_HK
dc.titleMetric and trigonometric pruning for clustering of uncertain data in 2D geometric spaceen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0306-4379&volume=36&issue=2&spage=476&epage=497&date=2011&atitle=Metric+and+trigonometric+pruning+for+clustering+of+uncertain+data+in+2D+geometric+space-
dc.identifier.emailKao, B: kao@cs.hku.hken_HK
dc.identifier.emailCheng, R: ckcheng@cs.hku.hken_HK
dc.identifier.emailChau, M: mchau@hkucc.hku.hken_HK
dc.identifier.emailCheung, DW: dcheung@cs.hku.hken_HK
dc.identifier.authorityKao, B=rp00123en_HK
dc.identifier.authorityCheng, R=rp00074en_HK
dc.identifier.authorityChau, M=rp01051en_HK
dc.identifier.authorityCheung, DW=rp00101en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.is.2010.09.005en_HK
dc.identifier.scopuseid_2-s2.0-78649488798en_HK
dc.identifier.hkuros186898en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-78649488798&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume36en_HK
dc.identifier.issue2en_HK
dc.identifier.spage476en_HK
dc.identifier.epage497en_HK
dc.identifier.isiWOS:000285366700019-
dc.publisher.placeUnited Kingdomen_HK
dc.identifier.scopusauthoridNgai, WK=14029152300en_HK
dc.identifier.scopusauthoridKao, B=35221592600en_HK
dc.identifier.scopusauthoridCheng, R=7201955416en_HK
dc.identifier.scopusauthoridChau, M=7006073763en_HK
dc.identifier.scopusauthoridLee, SD=7601400741en_HK
dc.identifier.scopusauthoridCheung, DW=34567902600en_HK
dc.identifier.scopusauthoridYip, KY=7101909946en_HK
dc.identifier.citeulike7904823-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats