US 2007/0192350 A1 · Co-clustering objects of heterogeneous types

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.

Claims20

Dependent claims

A system for co-clustering objects of heterogeneous types, comprising:

a component that represents relationships between objects of a first type and objects of a third type as a first bipartite graph;
a component that represents relationships between objects of a second type and objects of the third type as a second bipartite graph;
a component that provides a cut-based objective function representing relationships across cuts for both the first bipartite graph and the second bipartite graph;
a component that finds a solution to the cut-based objective function;
and
a component that identifies clusters of objects from the solution to the objective function.

3 more elements

A system for solving an objective function for consistent bipartite graph co-partitioning, comprising:

a component that provides object matrices, each representing a bipartite graph representing relationships between objects of different types where vertices represent objects and edges represent relationships;
a component that generates diagonal and Laplacian matrices for the object matrices;
a component that generates extended matrices based on the diagonal and Laplacian matrices;
a component that solves a cut-based objective function represents relationships across cuts for each of the bipartite graphs using the extended matrices using semi-definite programming;
and
a component that identifies clusters of objects from the solution.

3 more elements

Dependencies are inferred from the claim text.

Co-clustering objects of heterogeneous types

Life of this patent

Co-clustering objects of heterogeneous types

Life of this patent

Abstract

Claims20