Co-clustering objects of heterogeneous types

Details Co-clustering objects of heterogeneous types Co-clustering objects of heterogeneous types

2006-02-14

2008-12-02

Fleurantin, Jean B. (Department: 2162)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000, C715S252000

Reexamination Certificate

active

07461073

ABSTRACT:
A method and system for high-order co-clustering of objects of heterogeneous types using multiple bipartite graphs is provided. A clustering system represents relationships between objects of a first type and objects of a third type as a first bipartite graph and relationships between objects of a second type and objects of the third type as a second bipartite graph. The clustering system defines an objective function that specifies an objective of the clustering process that combines an objective for the first bipartite graph and an objective for the second bipartite graph. The clustering system solves the objective function and then applies a clustering algorithm such as the K-means algorithm to the solution to identify the clusters of heterogeneous objects.

REFERENCES:
patent: 6263334 (2001-07-01), Fayyad et al.
patent: 6269376 (2001-07-01), Dhillon et al.
patent: 6560597 (2003-05-01), Dhillon et al.
patent: 6581058 (2003-06-01), Fayyad et al.
patent: 6976020 (2005-12-01), Anthony et al.
patent: 7039638 (2006-05-01), Zhang et al.
patent: 7072891 (2006-07-01), Lee et al.
patent: 7272543 (2007-09-01), Estevez-Schwarz et al.
patent: 2003/0069908 (2003-04-01), Anthony et al.
patent: 2003/0084421 (2003-05-01), Estevez-Schwarz et al.
patent: 2003/0154181 (2003-08-01), Liu et al.
patent: 2003/0204484 (2003-10-01), Charpiot et al.
patent: 2005/0015366 (2005-01-01), Carrasco et al.
patent: 2005/0203889 (2005-09-01), Okubo et al.
patent: 2006/0242093 (2006-10-01), Richardson et al.
“Consistent Bipartite Graph Co-Partitioning for Star-Structured High-Order Heterogeneous Data Co-Clustering”—Bin Gao, Tie-Yan Lie, Xin Zheng, Qian-Sheng Cheng and Wei-Ying Ma—ACM- KDD'05, Aug. 21-24, 2005, Chicago, Illinois pp. 41-50.
“Relevance search and anomaly detection in bipartie graphs”—Jimeng Sun, Huiming Qu, Deepayan Chakrabarti and Christos Faloutsos—ACM SIGKDD Explorations Newletter—vol. 7, issue Dec. 2, 2005 (pp. 48-55).
“Solving cluster ensemble problems by bipartite graph partitioning”—Xioali Zhang Fern and Carla E. Brodley—ACM International Conference proceeding Series—ACM 2004, (pp. 36 including 8 pages).
U.S. Appl. No. 11/621,848, Liu et al.
“SDP Semidefinite Programming,” 2 pages, http://www-user.tu-chemnitz.de/˜helmberg/semidef.html [last accessed Nov. 29, 2006].
“SDPA Online Introduction,” 5 pages, http://grid.r.dendai.ac.jp/sdpa/intro.html [last accessed Jan. 9, 2006].
Bach, Francis R. and Michael I. Jordan, “Learning Spectral Clustering,” Neural Info. Processing Systems 16, NIPS 2003, 8 pages.
Baeza-Yates, R. and B. Ribeiro-Neto, “Chapter 2 Modeling,” Modern Information Retrieval, © 1999 by the ACM Press, pp. 19-71.
Banerjee, Arindam, Inderjit Dhillon and Dharmendra S. Modha, “A Generalized Maximum Entropy Approach to Bregman Co-clustering and Matrix Approximation,” Research Track Poster, KDD'04, Aug. 22-25, 2004, Seattle, Washington, pp. 509-514, © 2004 ACM.
Benson, H.P., “Global Optimization Algorithm for the Nonlinear Sum of Ratios Problem,” Journal of Optimization Theory and Applications, vol. 112, No. 1, Jan. 2002, © 2002 Plenum Publishing Corporation, pp. 1-29.
Boyd, Stephen and Lieven Vandenberghe, “Chapters 4.4, 4.6 and 11.6,” Convex Optimization, © 2004 Cambridge University Press, pp. 152-160, 167-17 & 596-608.
Cai, Deng et al., “Hierarchical Clustering of WWW Image Search Results Using Visual, Textual and Link Information,” MM'04, New York, © 2004 ACM, 8 pages.
Cai, Deng et al., “Organizing WWW Images Based on The Analysis of Page Layout and Web Link Structure,” In the 2004 IEEE International Conference on Multimedia and EXPO, © 2004 IEEE, 4 pages.
Chang, Tianhorng. and C. C. Jay Kuo, Texture Analysis and Classification with Tree-Structured Wavelet Transform, IEEE Transactions on Image Processing, vol. 2, No. 4, Oct. 1993, © 1993 IEEE, pp. 429-441.
Chen, Yixin, James Z. Wang and Robert Krovetz, “Content-Based Image Retrieval by Clustering,” MIR'03, Berkeley, California, © 2003 ACM Press, pp. 193-200.
Dhillon, Inderjit S., “Co-clustering documents and words using Bipartite Spectral Graph Partitioning,” In KDD'01, San Francisco, California, pp. 269-274, © 2001 ACM.
Dhillon, Inderjit S., Subramanyam Mallela and Dharmendra S. Modha, “Information-Theoretic Co-clustering,” SIGKDD'03, Aug. 2003, Washington, DC, pp. 89-98, © 2003 ACM.
Ding, Chris H.Q. et al., “A Min-max Cut Algorithm for Graph Partitioning and Data Clustering,” Proc. IEEE Int'l Conf. Data Mining 2001, pp. 1-8.
Duda, Richard O., Peter E. Hart and David G. Stork, “Chapter 10 Unsupervised Learning and Clustering,” Pattern Classification, Second Edition, © 2001 by John Wiley & Sons Inc., pp. 517-599.
Dumais, Susan T., “Chapter 4 Latent Semantic Analysis,” Annual Review of Information Science and Technology (ARIST), vol. 38, Section II, Technology, 2004, pp. 189-230.
El-Yaniv, Ran and Oren Souroujon, “Iterative Double Clustering for Unsupervised and Semi-Supervised Learning,” In Proceedings of ECML'01, pp. 121-132, 2001.
Freitas, Alex A., “A Critical Review of Multi-Objective Optimization in Data Mining: a position paper,” SIGKDD Explorations, vol. 6, Issue 2, 2004, pp. 77-86.
Frenk, J.B.G. and S. Schaible, “Fractional Programming,” Sep. 17, 2004, ERIM Report Series Reference No. ERS-2004-074-LIS, 55 pages, http://ssm.com/abstract=595012 [last accessed Nov. 29, 2006].
Fujisawa, Katsuki et al., “Numerical Evaluation of SDPA (SemiDefinite Programming Algorithm),” Revised Sep. 1998, 29 pages.
Gao, Bin et al., “Consistent Bipartite Graph Co-Partitioning for Star-Structured High-Order Heterogeneous Data Co-Clustering,” Research Track Paper, KDD'05, Chicago, © 2005 ACM, pp. 41-50.
Gao, Bin et al., “Hierarchical Taxonomy Preparation for Text Categorization Using Consistent Bipartite Spectral Graph Co-partitioning,” Sep. 2005, IEEE Transactions on Knowledge and Data Engineering, vol. 17, No. 9, © 2005 IEEE, pp. 1-11.
Gao, Bin et al., “Web Image Clustering by Consistent Utilization of Visual Features and Surrounding Texts,” MM'05, Nov. 6-11, 2005, Singapore, © 2005 ACM, pp. 112-121.
Golub, Gene H. and Charles F. Van Loan, “Chpts. 2.5, 7.1, 8.1 & 8.7,” Matrix Computations, Johns Hopkins University Press, 3rd edition, 1996, pp. 69-75, 310-320, 393-405 and 461-469.
Gordon, Shiri, Hayit Greenspan and Jacob Goldberger, “Applying the Information Bottleneck Principle to Unsupervised Clustering of Discrete and Continuous Image Representations,” Proceedings of the Ninth IEEE International Conference on Computer Vision (ICCV 2003), © 2003 IEEE, 8 pages.
Hagen, Lars and Andrew B. Kahng, “New Spectral Methods for Ratio Cut Partitioning and Clustering,” IEEE Transactions on Computer-Aided Design, vol. 11, Sep. 1992, © 1992 IEEE, pp. 1074-1085.
La Cascia, Marco et al., “Combining Textual and Visual Cues for Content-based Image Retrieval on the World Wide Web,” IEEE Workshop on Content-based Access of Image and Video Libraries, Jun. 1998, 5 pages.
Li, Zhiwei et al., “Group WWW Image Search Results by Novel Inhomogeneous Clustering Method,” In proceedings of the 11th International Multimedia Modelling Conference (MMM'05), © 2005 IEEE, 7 pages.
Long, Bo, Zhongfei (Mark) Zhang and Philip S. Yu, “Co-clustering by Block Value Decomposition,” Research Track Poster, KDD'05, Aug. 21-24, 2005, Chicago, Illinois, pp. 635-640, © 2005 ACM.
Mao, Jianchang and Anil K. Jain, “Texture Classification and Segmentation Using Multiresolution Simultaneous Autoregressive Models,” Jun. 20, 1991, Pattern Recognition, vol. 25, No. 2, © 1992 Pattern Recognition

Affiliated with

Also associated with

Rating

Co-clustering objects of heterogeneous types does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Co-clustering objects of heterogeneous types, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Co-clustering objects of heterogeneous types will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4020467