iVIBRATE: Interactive visualization-based framework for clustering large datasets

ABSTRACT

With continued advances in communication network technology and sensing technology, there is astounding growth in the amount of data produced and made available through cyberspace. Efficient and high-quality clustering of large datasets continues to be one of the most important problems in large-scale data analysis. A commonly used methodology for cluster analysis on large datasets is the three-phase framework of sampling/summarization, iterative cluster analysis, and disk-labeling. There are three known problems with this framework which demand effective solutions. The first problem is how to effectively define and validate irregularly shaped clusters, especially in large datasets. Automated algorithms and statistical methods are typically not effective in handling these particular clusters. The second problem is how to effectively label the entire data on disk (disk-labeling) without introducing additional errors, including the solutions for dealing with outliers, irregular clusters, and cluster boundary extension. The third obstacle is the lack of research about issues related to effectively integrating the three phases. In this article, we describe iVIBRATE---an interactive visualization-based three-phase framework for clustering large datasets. The two main components of iVIBRATE are its VISTA visual cluster-rendering subsystem which invites human interplay into the large-scale iterative clustering process through interactive visualization, and its adaptive ClusterMap labeling subsystem which offers visualization-guided disk-labeling solutions that are effective in dealing with outliers, irregular clusters, and cluster boundary extension. Another important contribution of iVIBRATE development is the identification of the special issues presented in integrating the two components and the sampling approach into a coherent framework, as well as the solutions for improving the reliability of the framework and for minimizing the amount of errors generated within the cluster analysis process. We study the effectiveness of the iVIBRATE framework through a walkthrough example dataset of a million records and we experimentally evaluate the iVIBRATE approach using both real-life and synthetic datasets. Our results show that iVIBRATE can efficiently involve the user in the clustering process and generate high-quality clustering results for large datasets.

REFERENCES

• 1: Mihael Ankerst , Markus M. Breunig , Hans-Peter Kriegel , Jörg Sander, OPTICS: ordering points to identify the clustering structure, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.49-60, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: Daniel Asimov, The grand tour: a tool for viewing multidimensional data, SIAM Journal on Scientific and Statistical Computing, v.6 n.1, p.128-143, Jan. 1985 [doi>10.1137/0906011]
• 3: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 4: Barbará, D., DuMouchel, W., Faloutsos, C., Haas, P. J., Hellerstein, J. M., Ioannidis, Y. E., Jagadish, H. V., Johnson, T., Ng, R. T., Poosala, V., Ross, K. A., and Sevcik, K. C. 1997. The New Jersey data reduction report. IEEE Data Eng. Bull. 20, 4, 3--45.
• 5: Bradley, P. S., Fayyad, U. M., and Reina, C. 1998. Scaling clustering algorithms to large databases. In Proceedings of the ACM SIGKDD Conference, 9--15.
• 6: Keke Chen , Ling Liu, ClusterMap: labeling clusters in large datasets via visualization, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031233]
• 7: Keke Chen , Ling Liu, VISTA: validating and refining clusters via visualization, Information Visualization, v.3 n.4, p.257-270, December 2004 [doi>10.1057/palgrave.ivs.9500076]
• 8: Keke Chen , Ling Liu, The "Best K" for entropy-based categorical data clustering, Proceedings of the 17th international conference on Scientific and statistical database management, p.253-262, June 27-29, 2005, Santa Barbara, CA
• 9: Conover, W. 1998. Practical Nonparametric Statistics. John Wiley and Sons, New York.
• 10: Cook, D., Buja, A., Cabrera, J., and Hurley, C. 1995. Grand tour and projection pursuit. J. Comput. Graphical Statistics 23, 155--172.
• 11: Cox, T. F. and Cox, M. A. A. 2001. Multidimensional Scaling. Chapman and Hall, London, UK.
• 12: Douglass R. Cutting , David R. Karger , Jan O. Pedersen , John W. Tukey, Scatter/Gather: a cluster-based approach to browsing large document collections, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-329, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133214]
• 13: Dhillon, I. S., Modha, D. S., and Spangler, W. S. 1998. Visualizing class structure of multidimensional data. In Proceedings of the 30th Symposium on the Interface: Computing Science and Statistics 30, 488--493.
• 14: Dubes, R. C. and Jain, A. K. 1979. Validity studies in clustering methodologies. Pattern Recogn. Lett., 235--254.
• 15: Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, 226--231.
• 16: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
• 17: Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
• 18: Jean Gallier, Geometric methods and applications: for computer science and engineering, Springer-Verlag, London, 2000
• 19: Gray, J. 2000. What next? A few remaining problems in information technlogy. In Proceedings of the Sigmod Conference 1999, ACM Turing Award Lecture (video). ACM SIGMOD Digital Symposium Collection 2, 2.
• 20: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.73-84, June 01-04, 1998, Seattle, Washington, United States
• 21: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, ROCK: a robust clustering algorithm for categorical attributes, Information Systems, v.25 n.5, p.345-366, July 2000 [doi>10.1016/S0306-4379(00)00022-3]
• 22: Maria Halkidi , Yannis Batistakis , Michalis Vazirgiannis, Cluster validity methods: part I, ACM SIGMOD Record, v.31 n.2, June 2002 [doi>10.1145/565117.565124]
• 23: Hinneburg, A. and Keim, D. A. 1998. An efficient approach to clustering in large multimedia databases with noise. In Proceedings of the ACM SIGKDD Conference, 58--65.
• 24: Alexander Hinneburg , Daniel A. Keim , Markus Wawryniuk, HD-Eye: Visual Mining of High-Dimensional Data, IEEE Computer Graphics and Applications, v.19 n.5, p.22-31, September 1999 [doi>10.1109/38.788795]
• 25: Patrick Hoffman , Georges Grinstein , Kenneth Marx , Ivo Grosse , Eugene Stanley, DNA visual and analytic data mining, Proceedings of the 8th conference on Visualization '97, p.437-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 26: A. Inselberg, Multidimensional detective, Proceedings of the 1997 IEEE Symposium on Information Visualization (InfoVis '97), p.100, October 18-25, 1997
• 27: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 28: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 29: Eser Kandogan, Visualizing multi-dimensional clusters, trends, and outliers using star coordinates, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.107-116, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502530]
• 30: George Karypis , Eui-Hong (Sam) Han , Vipin Kumar, Chameleon: Hierarchical Clustering Using Dynamic Modeling, Computer, v.32 n.8, p.68-75, August 1999 [doi>10.1109/2.781637]
• 31: Daniel A. Keim, Visual exploration of large data sets, Communications of the ACM, v.44 n.8, p.38-44, Aug. 2001 [doi>10.1145/381641.381656]
• 32: Larkin, J. and Simon, H. 1987. Why a diagram is (sometimes) worth ten thousand words. Cognitive Sci. 11, 65--99.
• 33: Jeffrey LeBlanc , Matthew O. Ward , Norman Wittels, Exploring N-dimensional databases, Proceedings of the 1st conference on Visualization '90, October 23-26, 1990, San Francisco, California
• 34: Chen Li , Edward Chang , Hector Garcia-Molina , Gio Wiederhold, Clustering for Approximate Similarity Search in High-Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.792-808, July 2002 [doi>10.1109/TKDE.2002.1019214]
• 35: Littlefield, R. J. 1983. Using the GLYPH concept to create user-definable display formats. National Comput. Graphics Association, 697--706.
• 36: Huan Liu , Hiroshi Motoda, Feature Extraction, Construction and Selection: A Data Mining Perspective, Kluwer Academic Publishers, Norwell, MA, 1998
• 37: Christopher Meek , Bo Thiesson , David Heckerman, The learning-curve sampling method applied to model-based clustering, The Journal of Machine Learning Research, 2, p.397-418, 3/1/2002 [doi>10.1162/153244302760200678]
• 38: Newman, M. E. 2003. The structure and function of complex networks. SIAM Rev., 167--256.
• 39: Christopher R. Palmer , Christos Faloutsos, Density biased sampling: an improved method for data mining and clustering, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.82-92, May 15-18, 2000, Dallas, Texas, United States
• 40: Lakshmish Ramaswamy , Bugra Gedik , Ling Liu, A Distributed Approach to Node Clustering in Decentralized Peer-to-Peer Networks, IEEE Transactions on Parallel and Distributed Systems, v.16 n.9, p.814-829, September 2005 [doi>10.1109/TPDS.2005.101]
• 41: Ross, S. M. 2000. Introduction to Probability Models. Academic Press, San Diego, CA.
• 42: Dmitri Roussinov , Kristine Tolle , Marshall Ramsey , Hsinchun Chen, Interactive Internet search through automatic clustering (poster abstract): an empirical study, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.289-290, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312714]
• 43: Hinrich Schütze , Craig Silverstein, Projections for efficient document clustering, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.74-81, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 44: Jinwook Seo , Ben Shneiderman, Interactively Exploring Hierarchical Clustering Results, Computer, v.35 n.7, p.80-86, July 2002 [doi>10.1109/MC.2002.1016905]
• 45: Subhash Sharma, Applied multivariate techniques, John Wiley & Sons, Inc., New York, NY, 1995
• 46: Gholamhosein Sheikholeslami , Surojit Chatterjee , Aidong Zhang, WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.428-439, August 24-27, 1998
• 47: Ben Shneiderman, Inventing discovery tools: combining information visualization with data mining, Information Visualization, v.1 n.1, p.5-12, March 2002 [doi>10.1057/palgrave/ivs/9500006]
• 48: Craig Silverstein , Jan O. Pedersen, Almost-constant-time clustering of arbitrary corpus subsets4, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.60-66, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 49: Sonka, M., Hlavac, V., and Boyle, R. 1999. Image Processing, Analysis and Machine Vision. Brooks/Cole Publishing, Pacific Grove, CA.
• 50: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]
• 51: Matthew O. Ward, XmdvTool: integrating multiple methods for visualizing multivariate data, Proceedings of the conference on Visualization '94, October 17-21, 1994, Washinton, D.C.
• 52: Peter Willett, Recent trends in hierarchic document clustering: a critical review, Information Processing and Management: an International Journal, v.24 n.5, p.577-597, 1988 [doi>10.1016/0306-4573(88)90027-1]
• 53: Xiaowei Xu , Martin Ester , Hans-Peter Kriegel , Jörg Sander, A Distribution-Based Clustering Algorithm for Mining in Large Spatial Databases, Proceedings of the Fourteenth International Conference on Data Engineering, p.324-331, February 23-27, 1998
• 54: Yang, J., Ward, M. O., and Rundensteiner, E. A. 2002. Interactive hierarchical displays: A general framework for visualization and exploration of large multivariate datasets. Comput. Graphics J. 27, 265--283.
• 55: Li Yang, Interactive exploration of very large relational datasets through 3D dynamic projections, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.236-243, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347134]
• 56: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997
• 57: Oren Zamir , Oren Etzioni, Web document clustering: a feasibility demonstration, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.46-54, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290956]
• 58: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.5 Implementation
          Subjects: Special architectures; Interactive systems

General Terms:
Algorithms, Design, Human Factors, Reliability

Keywords:
Clustering, interactive visualization, labeling, large datasets, performance