2011 UnsupervisedClusteringofMultidi

• (Applegate et al., 2011) ⇒ David Applegate, Tamraparni Dasu, Shankar Krishnan, and Simon Urbanek. (2011). “Unsupervised Clustering of Multidimensional Distributions Using Earth Mover Distance.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020508

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Unsupervised+Clustering+of+Multidimensional+Distributions+Using+Earth+Mover+Distance
• http://dl.acm.org/citation.cfm?id=2020408.2020508&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; algorithms; clustering; distributions; earth mover distance; signatures; similarity measures

Abstract

Multidimensional distributions are often used in data mining to describe and summarize different features of large datasets. It is natural to look for distinct classes in such datasets by clustering the data. A common approach entails the use of methods like k-means clustering. However, the k-means method inherently relies on the Euclidean metric in the embedded space and does not account for additional topology underlying the distribution.

In this paper, we propose using Earth Mover Distance (EMD) to compare multidimensional distributions. For a n-bin histogram, the EMD is based on a solution to the transportation problem with time complexity [math]\displaystyle{ O (n^3 \log\;n) }[/math]. To mitigate the high computational cost of EMD, we propose an approximation that reduces the cost to linear time. Given the large size of our dataset a fast approximation is crucial for this application.

Other notions of distances such as the information theoretic Kullback-Leibler divergence and statistical χ2 distance, account only for the correspondence between bins with the same index, and do not use information across bins, and are sensitive to bin size. A cross-bin distance measure like EMD is not affected by binning differences and meaningfully matches the perceptual notion of “nearness ".

Our technique is simple, efficient and practical for clustering distributions. We demonstrate the use of EMD on a real-world application of analyzing 411, 550 anonymous mobility usage patterns which are defined as distributions over a manifold. EMD allows us to represent inherent relationships in this space, and enables us to successfully cluster even sparse signatures.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 UnsupervisedClusteringofMultidi	David Applegate Tamraparni Dasu Shankar Krishnan Simon Urbanek			Unsupervised Clustering of Multidimensional Distributions Using Earth Mover Distance				10.1145/2020408.2020508		2011