Joint cluster analysis of attribute data and relationship data: The connected k-center problem, algorithms and applications

ABSTRACT

Attribute data and relationship data are two principal types of data, representing the intrinsic and extrinsic properties of entities. While attribute data have been the main source of data for cluster analysis, relationship data such as social networks or metabolic networks are becoming increasingly available. It is also common to observe both data types carry complementary information such as in market segmentation and community identification, which calls for a joint cluster analysis of both data types so as to achieve better results. In this article, we introduce the novel Connected k-Center (CkC) problem, a clustering model taking into account attribute data as well as relationship data. We analyze the complexity of the problem and prove its NP-hardness. Therefore, we analyze the approximability of the problem and also present a constant factor approximation algorithm. For the special case of the CkC problem where the relationship data form a tree structure, we propose a dynamic programming method giving an optimal solution in polynomial time. We further present NetScan, a heuristic algorithm that is efficient and effective for large real databases. Our extensive experimental evaluation on real datasets demonstrates the meaningfulness and accuracy of the NetScan results.

REFERENCES

• 1: Agarwal, P. and Procopiuc, C. M. 2002. Exact and approximation algorithms for clustering. Algorithmica 33, 2, 201--226.
• 2: 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
• 3: Barabasi, A. L., Jeong, H., Neda, Z., Ravasz, E., Schubert, A., and Vicseks, T. 2002. Evolution of the social network of scientific collaborations. Physica A 311, 3--4, 590--614.
• 4: Yair Bartal , Moses Charikar , Danny Raz, Approximating min-sum k-clustering in metric spaces, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.11-20, July 2001, Hersonissos, Greece [doi>10.1145/380752.380754]
• 5: Sugato Basu , Mikhail Bilenko , Raymond J. Mooney, A probabilistic framework for semi-supervised clustering, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014062]
• 6: Berriz, G. F., King, O. D., Bryant, B., Sander, C., and Roth, F. P. 2003. Characterizing gene sets with funcassociate. Bioinformatics 19, 18, 2502--2504.
• 7: Brandes, U., Gaertler, M., and Wagner, D. 2003. Experiments on graph clustering algorithms. In Proceedings of the 11th Annual European Symposium on Algorithms (Budapest, Hungary). Springer-Verlag, Berlin/Heidelberg, Germany, 568--579.
• 8: Brucker, P. 1977. On the complexity of clustering problems. In Optimization and Operations Research, R. Hehn, B. Korte, and W. Oettli, Eds. Springer-Verlag, Berlin, Germany, 45--54.
• 9: Chan, P. K., Schlag, M. D. F., and Zien, J. Y. 1994. Spectral k-way ratio-cut partitioning and clustering. IEEE Trans. Computer-Aided Desi. Integ. Circ. Syst. 13, 9, 1088--1096.
• 10: Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem, Journal of Computer and System Sciences, v.65 n.1, p.129-149, August 2002 [doi>10.1006/jcss.2002.1882]
• 11: Moses Charikar , Rina Panigrahy, Clustering to minimize the sum of cluster diameters, Journal of Computer and System Sciences, v.68 n.2, p.417-441, March 2004 [doi>10.1016/j.jcss.2003.07.0014]
• 12: CiteSeer. 2006. Scientific literature digital library. http://citeseer.ist.psu.edu/.
• 13: Davidson, I. and Ravi, S. S. 2005. Clustering with constraints: Feasibility issues and the k-means algorithm. In Proceedings of the 5th SIAM International Conference on Data Mining (Newport Beach, CA). Society for Industrial and Applied Mathematics, Philadelphia, PA, 138--149.
• 14: DBLP. Computer science bibliography. http://www.informatik.uni-trier.de/~ley/db/index.html.
• 15: Inderjit S. Dhillon , Yuqiang Guan , Brian Kulis, Weighted Graph Cuts without Eigenvectors A Multilevel Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.29 n.11, p.1944-1957, November 2007 [doi>10.1109/TPAMI.2007.1115]
• 16: Srinivas Doddi , Madhav V. Marathe , S. S. Ravi , David Scot Taylor , Peter Widmayer, Approximation Algorithms for Clustering to Minimize the Sum of Diameters, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.237-250, July 05-07, 2000
• 17: Dyer, M. and Frieze, A. M. 1985. A simple heuristic for the p-center problem. Oper. Res. Lett. 3, 285--288.
• 18: Ester, M., Ge, R., Gao, B. J., Hu, Z., and Ben-Moshe, B. 2006. Joint cluster analysis of attribute data and relationship data: the connected k-center problem. In Proceedings of the 6th SIAM Conference on Data Mining (Bethesda, MD). Society for Industrial and Applied Mathematics, Philadelphia, PA, 246--257.
• 19: Ester, M., Kriegel, H., 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 (Portland, OR). AAAI Press, 226--231.
• 20: Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62255]
• 21: Frederickson, G. N. and Johnson, D. B. 1979. Optimal algorithms for generating quantile information in x + y and matrices with sorted columns. In Proceedings of the 13th Annual Conference on Information Science and Systems. The Johns Hopkins Univ., Baltimore, MD, 47--52.
• 22: Gonzalez, T. 1985. Clustering to minimize the maximum inter-cluster distance. Theoret. Comput. Sci. 38, 2--3, 293--306.
• 23: ROCK: A Robust Clustering Algorithm for Categorical Attributes, Proceedings of the 15th International Conference on Data Engineering, p.512, March 23-26, 1999
• 24: Nili Guttmann-Beck , Refael Hassin, Approximation algorithms for min-sum p-clustering, Discrete Applied Mathematics, v.89 n.1-3, p.125-142, Dec. 1998 [doi>10.1016/S0166-218X(98)00100-0]
• 25: Hanisch, D., Zien, A., Zimmer, R., and Lengauer, T. 2002. Co-clustering of biological networks and gene expression data. Bioinformatics 18, S145--S154.
• 26: Hanneman, R. A. and Riddle, M. 2005. Introduction to social network methods. http://faculty.ucr.edu/~hanneman/.
• 27: Erez Hartuv , Ron Shamir, A clustering algorithm based on graph connectivity, Information Processing Letters, v.76 n.4-6, p.175-181, Dec.31 2000 [doi>10.1016/S0020-0190(00)00142-3]
• 28: Hochbaum, D. and Shmoys, D. 1985. A best possible heuristic for the k-center problem. Math. Oper. Res. 10, 180--184.
• 29: Iacobucci, D. 1996. Networks in Marketing. Sage Publications, Thousand Oaks, CA.
• 30: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 31: Kamal Jain , Vijay V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM (JACM), v.48 n.2, p.274-296, March 2001 [doi>10.1145/375827.375845]
• 32: Kariv, O. and Hakimi, S. L. 1979. An algorithmic approach to network location problems, Part II: p-medians. SIAM J. Appl. Math. 37, 539--560.
• 33: 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]
• 34: Kaufman, L. and Rousseeuw, P. 1990. Finding Groups in Data: An Introduction to Cluster Analysis. Wiley, New York.
• 35: Brian Kulis , Sugato Basu , Inderjit Dhillon , Raymond Mooney, Semi-supervised graph clustering: a kernel approach, Proceedings of the 22nd international conference on Machine learning, p.457-464, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102409]
• 36: Jyh-Han Lin , Jeffrey Scott Vitter, Approximation algorithms for geometric median problems, Information Processing Letters, v.44 n.5, p.245-249, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90208-D]
• 37: Lloyd, S. 1982. Least squares quantization in pcm. IEEE Trans. Inf. Theory 28, 2, 129--136.
• 38: MacQueen, J. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematics, Statistics and Probability. 281--297.
• 39: Megiddo, N. and Supowit, K. J. 1984. On the complexity of some common geometric location problems. SIAM Journal on Computing 13, 1, 182--196.
• 40: Megiddo, N., Tamir, A., Zemel, E., and Chandrasekaran, R. 1981. An o(n log² n) algorithm for the k-th longest path in a tree with applications to location problems. SIAM J. Comput. 10, 2, 328--337.
• 41: Flavia Moser , Rong Ge , Martin Ester, Joint cluster analysis of attribute and relationship data withouta-priori specification of the number of clusters, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281248]
• 42: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 43: Scott, J. 2000. Social Network Analysis: A handbook. Sage Publications, Thousand Oaks, CA.
• 44: Segal, E., Wang, H., and Koller, D. 2003. Discovering molecular pathways from protein interaction and gene expression data. Bioinformatics (Suppl. 1) 19, 264--272.
• 45: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 46: Spellman, P. T., Sherlock, G., Zhang, M. Q., Iyer, V. R., Anders, K., Eisen, M. B., Brown, P. O., Botstein, D., and Futcher, B. 1998. Comprehensive identification of cell cycle-regulated genes of the yeast saccharomyces cerevisiae by microarray hybridization. Molec. Biol. Cell 9, 12, 3273--3297.
• 47: Stark, C., Breitkreutz, B., Reguly, T., Boucher, L., Breitkreutz, A., and Tyers, M. 2006. Biogrid: A general repository for interaction datasets. Nucleic Acids Res. 34, D535--D539.
• 48: Steinbach, M., Karypis, G., and Kumar, V. 2000. A comparison of document clustering techniques. In KDD Workshop on Text Mining.
• 49: Steinhaus, H. 1956. Sur la division des corp materiels en parties. Bulletin L'Acadmie Polonaise des Science C1. III, IV, 801--804.
• 50: Chaitanya Swamy , Amit Kumar, Primal–Dual Algorithms for Connected Facility Location Problems, Algorithmica, v.40 n.4, p.245-269, September 2004 [doi>10.1007/s00453-004-1112-3]
• 51: Tamir, A. 1996. An o(pn²) algorithm for the p-median and related problems on tree graphs. Operations Research Letters 19, 59--64.
• 52: Taskar, B., Segal, E., and Koller, D. 2001. Probabilistic classification and clustering in relational data. In Proceedings of 17th International Joint Conference on Artificial Intelligence (Seattle, WA). Morgan Kaufmann, San Francisco, CA, 870--878.
• 53: Toregas, C., Swan, R., Revelle, C., and Bergman, L. 1971. The location of emergency service facilities. Oper. Res. 19, 1363--1373.
• 54: Anthony K. H. Tung , Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han, Constraint-based clustering in large databases, Proceedings of the 8th International Conference on Database Theory, p.405-419, January 04-06, 2001
• 55: Ulitsky, I. and Shamir, R. 2007. Identification of functional modules using network topology and high-throughput data. BMC System Biology 1, 8.
• 56: Wasserman, S. and Faust, K. 1994. Social Network Analysis. Cambridge University Press, Cambridge, UK.
• 57: Webster, C. and Morrison, P. 2004. Network analysis in marketing. Australasian Market. J. 12, 2, 8--18.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Management, Performance

Keywords:
Attribute data, NP-hardness, approximation algorithms, community identification, document clustering, joint cluster analysis, market segmentation, relationship data