US 7,461,073 B2Grant

Co-clustering objects of heterogeneous types

Issue Date:2008-12-02

•18 Claims

•8 Drawing Sheets

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.

Metadata

Assignee

Microsoft Corporation

Inventors

Bin Gao
Tie-Yan Liu
Wei-Ying Ma

Application Information

Application Number:US 11/354,208

Filing Date:2006-02-14

Priority Date:2006-02-14

Art Unit:2162

Classifications

IPC:

G06F17/00G06F17/30

Patent Drawings (8 sheets)

Description

Background

[0001] In many applications, it can be very useful to identify groups or clusters of objects such that objects in the same cluster are similar while objects in different clusters are dissimilar. Such identification of groups is referred to as “clustering.” Clustering has been used extensively to identify similar web-based objects. Web-based objects may include web pages, images, scientific articles, queries, authors, news reports, and so on. For example, when a collection of images is identified by a image search engine, the search engine may want to identify clusters of related images. The search engine may use various well-known algorithms including K-means, maximum likelihood estimation, spectral clustering, and so on. These algorithms generate clusters of homogeneous objects, that is, objects of the same type (e.g., generate clusters of images only or clusters of web pages only).

[0002] Recently, attempts have been made to cluster highly interrelated heterogeneous objects such as images and their surrounding text, documents and terms, customers and their purchased items, and so on. The goal of heterogeneous clustering is to identify clusters that contain related objects of two types. The use of homogeneous clustering on objects of each type separately may not be an acceptable basis for not heterogeneous clustering because the similarities among one type of objects sometimes can only be defined by the other type of objects. One attempt at co-clustering objects of two types tries to extend traditional spectral clustering algorithms using a bipartite spectral graph clustering algorithm to co-cluster documents and terms simultaneously. A similar attempt has been made at co-clustering heterogeneous objects in the field of biology and image processing. Some attempts have been made at high-order co-clustering, that is, co-clustering objects of more than two data types. However, such attempts have not used in an effective objective function nor is there sufficient evidence of the effectiveness of the iterative algorithms used by these attempts.

Summary

[0003] 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 objects are represented as vertices, and the relationships are represented as edges of the bipartite graphs. The clustering system represents the first bipartite graph as a matrix with rows representing objects of the first type and columns representing objects of the third type and the second bipartite graph as a matrix with rows representing objects of the second type and columns representing objects of the third type. The elements of the matrices represent the weights of the relationship between the objects. 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.

[0004] The clustering system may solve the objective function by transforming the objective function to a semi-definite programming problem. The clustering system converts what would be a sum-of-ratios quadratic fractional programming problem to a quadratically constrained quadratic programming problem by simplifying the objective function. The simplified objective function is a quadratically constrained quadratic programming problem since all the constraints are convex and certain diagonal matrices are positive semi-definite. The clustering system then casts the quadratically constrained quadratic programming problem as a semi-definite programming problem by relaxing further constraints. The clustering system then uses one of a variety of algorithms for solving the semi-definite programming problem. The clustering system then applies a clustering algorithm such as a K-means algorithm to the solution to identify clusters of heterogeneous objects.

[0005] This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.

Brief Description of the Drawings

[0006] FIG. 1 is a diagram representing a tripartite graph illustrating relationships between low-level features, images, and text.

[0007] FIG. 2 illustrates the transforming of a tripartite graph into two bipartite graphs.

[0008] FIG. 3 is a block diagram illustrating components of the clustering system in one embodiment.

[0009] FIG. 4 is a flow diagram illustrating processing of the CBGC component of the clustering system in one embodiment.

[0010] FIG. 5 is a flow diagram that illustrates the processing of the form Laplacian matrices component of the clustering system in one embodiment.

[0011] FIG. 6 is a flow diagram that illustrates the processing of the CBGC by SDP component of the clustering system in one embodiment.

[0012] FIG. 7 is a flow diagram that illustrates the processing of the generate extended matrices component of the clustering system in one embodiment.

Detailed Description

[0013] A method and system for high-order co-clustering of objects of heterogeneous types using multiple bipartite graphs is provided. In one embodiment, 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 objects are represented as vertices, and the relationships are represented as edges of the bipartite graphs. For example, the third type of object may be an image, the first type of object may be a feature vector of visual features of the image, and the second type of object may be text surrounding the image on a web page. The clustering system represents the first bipartite graph as a matrix with rows representing objects of the first type and columns representing objects of the third type and the second bipartite graph as a matrix with rows representing objects of the second type and columns representing objects of the third type. The elements of the matrices represent the weights of the relationship between the objects. For example, an element of a matrix that maps documents to terms may contain the number of occurrences of the term within the documents. The clustering system thus transforms the high-order co-clustering to multiple pair-wise co-clusterings with the bipartite graphs. 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. In one embodiment, the objective function is cut-based based in that it specifies the objective in terms of the cut between the vertices of one cluster and the vertices of another cluster. One objective function would be to minimize the cut, that is, ensure that the relationships represented by the edges that are cut are minimized. Another objective function, referred to as “ratio cut,” balances cluster sizes, and another objective function, referred to as “normalized cut,” balances the cluster weights. In one embodiment, the clustering system uses a normalized cut objective function. 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. The clustering system thus provides consistent bipartite graph co-partitioning.

[0014] In one embodiment, the clustering system solves the objective function by transforming the objective function to a semi-definite programming problem. The clustering system converts what would be a sum-of-ratios quadratic fractional programming problem to a quadratically constrained quadratic programming problem by simplifying the objective function. The simplified objective function is a quadratically constrained quadratic programming problem since all the constraints are convex and certain diagonal matrices are positive semi-definite. A positive semi-definite matrix is a square matrix with eigenvalues that are all non-negative and in which the matrix and its conjugate transpose are equal. The clustering system then casts the quadratically constrained quadratic programming problem as a semi-definite programming problem by relaxing further constraints. The clustering system then uses one of a variety of algorithms for solving the semi-definite programming problem. For example, the clustering system may use an interior-point method SDPA as described in Fujisawa, K., Fukuda, M., Kojima, M., and Nakata, K., “Numerical Evaluation of SDPA (SemiDefinite Programming Algorithm),” High Performance Optimization, Kluwer Academic Press, 267-301, 2000. The clustering system then applies a clustering algorithm such as a K-means algorithm to the solution to identify clusters of heterogeneous objects.

[0015] A normalized cut objective function is described in Shi, J. and Malik, J., “Normalized Cuts and Image Segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 22, No. 8, August 2000, which is hereby incorporated by reference. A normalized cut objective function is based on a disassociation measure that indicates that the cut cost is a fraction of the total edge connections to all the vertices in the graph and based on a normalized association measure within a cluster that indicates how tightly the vertices of a cluster are connected. The normalized cut objective function can be represented as follows:

[0016]

\begin{matrix} \min \frac{q^{T} Lq}{q^{T} Dq}, s . t . q^{T} De = 0, q \neq 0 & (1) \end{matrix}

where G=(V, E) represents a graph G with vertices V and edges E, the weights of the relationships are represented as:

[0017]

\begin{matrix} M_{ij} = {\begin{matrix} E_{ij}, & if < i, j > \in E \\ 0, & otherwise, \end{matrix} & (2) \end{matrix}

D is a diagonal matrix represented as:
D=Σ_kE_ik, (3)
L is a Laplacian matrix represented as:
L=D−M, (4)
e is a column vector with all its elements equal to 1, q is a column vector with an element for each object with q_i=c₁when i is an object in one cluster and q_i=−c₂when i is an object in a second cluster and c₁and c₂are constants derived from D. The equation is subject to (“s.t.”) the constraints as indicated. By relaxing the constraint of discrete values to continuous values, the solution for Equation 1 is the eigenvector corresponding to the second smallest eigenvalue λ₂of the generalized eigenvalue problem as represented by the following:
Lq=λDq (5)

[0018] FIG. 1 is a diagram representing a tripartite graph illustrating relationships between low-level features, images, and text, which are an example of different object types. The squares, circles, and diamonds represent low-level features F={f₁, f₂, . . . , f_m}, images H={h₁, h₂, . . . , h_n}, and terms in surrounding texts W={w₁, w₂, . . . , w_t}, respectively. The weight of an edge between low-level feature i and image j equals the value of low-level feature i in image j, while the weight of an edge between image j and term k equals the frequency of term k in the surrounding text of image j.

[0019] FIG. 2 illustrates the transforming of a tripartite graph into two bipartite graphs. The clustering system divides this tripartite graph into two bipartite graphs, which share the base objects of images. The clustering system thus transforms the original problem to the fusion of the pair-wise co-clustering problems over these two bipartite graphs. The clustering system attempts to find two clusters of images that provide a globally optimal solution to an objective function, that is, a combination of objective functions for each bipartite graph. Because the clustering system finds a globally optimal solution, the solution may not be locally optimal for each of the bipartite graphs individually. This clustering process is referred to as consistent bipartite graph co-partitioning (“CBGC”).

[0020] In one embodiment, the clustering system bi-partitions the two bipartite graphs so that the three types objects are simultaneously clustered into two groups. In the following, f, h, and w represent column vectors of m, n, and t dimensions for visual features, images, and terms, respectively. The vectors of the bipartite graphs are represented as:
q=(f,h)^Tand p=(h,w)^T (6)
A is a matrix representing the first bipartite graph and a_ijis element ij of A, and B is a matrix representing the second bipartite graph and b_ijis element ij of B, D^(f)is a diagonal matrix represented as
D^(f)_ii=Σ_ka_ik, (7)
D^(w)is a diagonal matrix represented as
D^(w)_ii=Σ_kb_ik, (8)
L^(f)is a Laplacian matrix represented as
L^(f)=D−A, (9)
and L^(w)is a Laplacian matrix represented as
L^(w)=D−B. (10)
The clustering system models a co-partitioning problem with multiple objective functions subject to constraints as represented by the following:

[0021]

\begin{matrix} \min \frac{q^{T} L^{(f)} q}{q^{T} D^{(f)} q} \min \frac{p^{T} L^{(w)} p}{p^{T} D^{(w)} p} s . t . (i) q^{T} D^{(f)} e = 0, q \neq 0 (ii) p^{T} D^{(w)} e = 0, p \neq 0 & (11) \end{matrix}

The clustering system models the consistent co-partitioning problem by linearly combining the multiple local objective functions into a global objective function subject to constraints as follows:

[0022]

\begin{matrix} \min [β \frac{q^{T} L^{(f)} q}{q^{T} D^{(f)} q} + (1 - β) \frac{p^{T} L^{(w)} p}{p^{T} D^{(w)} p}] s . t . (i) q^{T} D^{(f)} e = 0, q \neq 0 (ii) p^{T} D^{(w)} e = 0, p \neq 0 (iii) 0 < β < 1 & (12) \end{matrix}

where β is a weighting parameter indicating the relative weight to be given the relationships of the bipartite graphs.

[0023] To solve the combined objective function, the clustering system sets ω=(f, h, w)^Tto be a vector representing the combination of features, images, and terms s=m+n+t dimensions. The clustering system then extends matrices L^(f), L^(w), D^(f), and D^(w)to adopt the dimension of ω as follows:

[0024]

\begin{matrix} Γ_{1} = {[\begin{matrix} L^{(f)} & 0 \\ 0 & 0 \end{matrix}]}_{s \times s}, Γ_{2} = {[\begin{matrix} 0 & 0 \\ 0 & L^{(w)} \end{matrix}]}_{s \times s} & (13) \end{matrix}

[0025]

\begin{matrix} Π_{1} = {[\begin{matrix} D^{(f)} & 0 \\ 0 & 0 \end{matrix}]}_{s \times s}, Π_{2} = {[\begin{matrix} 0 & 0 \\ 0 & D^{(w)} \end{matrix}]}_{s \times s} & (14) \end{matrix}

The objective function can be written subject to constraints as follows:

[0026]

\begin{matrix} \min [β \frac{ω^{T} Γ_{1} ω}{ω^{T} Π_{1} ω} + (1 - β) \frac{ω^{T} Γ_{2} ω}{ω^{T} Π_{2} ω}] s . t . (i) ω^{T} Π_{1} e = 0 (ii) ω^{T} Π_{2} e = 0 (iii) ω \neq 0, 0 < β < 1 & (15) \end{matrix}

This equation represents a sum-of-ratios quadratic fractional programming problem, which is hard and complicated to solve although there have been some branch-and-bound algorithms. To avoid solving this fractional programming problem, the clustering system uses spectral clustering to simplify the objective function by fixing the values of the denominators in Equation 15 to e^TΠ₁e and e^TΠ₂e, respectively. The objective function subject to constraints can then be rewritten as follows:
minω^TΓω
s.t. (i) ω^TΠ₁ω=e^TΠ₁e
(ii) ω^TΠ₂ω=e^TΠ₂e
(iii) ω^TΠ₁e=0
(iv) ω^TΠ₂e=0 (16)
where

[0027]

\begin{matrix} Γ = \frac{β}{e^{T} Π_{1} e} Γ_{1} + \frac{1 - β}{e^{T} Π_{2} e} Γ_{2}, 0 < β < 1 & (17) \end{matrix}

[0028] The optimization problem of Equation 16 is a quadratically constrained quadratic programming (“QCQP”) problem since all the constraints are convex and matrices Π₁and Π₂are both positive semi-definite. A convex QCQP problem can be cast in the form of a semi-definite programming problem (“SDP”) to reduce the computational complexity of finding a solution. SDP is an optimization problem with a form as follows:
min C□W
s.t. (i) A□W=b_i, i=1, . . . , k
(ii) W is positive semi-definite (18)
where C is a symmetric coefficient matrix and W is a symmetric parameter matrix; A_i(and b_i), i=1, . . . , k are coefficient matrices (and vectors) for the constraints; and the matrix inner-product is defined as:

[0029]

\begin{matrix} C •W = \sum_{i, j} C_{ij} W_{ij} & (19) \end{matrix}

[0030] The clustering system reformulates this QCQP problem as an SDP problem by relaxing the product terms w_iw_jto an element Ω_ijof a symmetric matrix Ω:

[0031]

\begin{matrix} \min_{ω, Ω} [\begin{matrix} 0 & 0 \\ 0 & Γ \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] s . t . (i) [\begin{matrix} - e^{T} Π_{1} e & 0 \\ 0 & Π_{1} \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] = 0 (ii) [\begin{matrix} - e^{T} Π_{2} e & 0 \\ 0 & Π_{2} \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] = 0 (iii) [\begin{matrix} 0 & e^{T} Π_{1} / 2 \\ Π_{1} e / 2 & 0 \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] = 0 (iv) [\begin{matrix} 0 & e^{T} \prod_{2} / 2 \\ \prod_{2} e / 2 & 0 \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] = 0 (v) [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] is positive semi - definite & (20) \end{matrix}

[0032] Since the SDP relaxation of a QCQP problem may produce an approximation to the original problem with a good error bound, the clustering system relaxes the constraints of Ω=w_iw_jwith the objective function as follows:

[0033]

\begin{matrix} \min_{ω} [\begin{matrix} 0 & 0 \\ 0 & Γ \end{matrix}] \cdot W s . t . (i) [\begin{matrix} - e^{T} Π_{1} e & 0 \\ 0 & Π_{1} \end{matrix}] \cdot W = 0 (ii) [\begin{matrix} - e^{T} Π_{2} e & 0 \\ 0 & Π_{2} \end{matrix}] \cdot W = 0 (iii) [\begin{matrix} 0 & e^{T} Π_{1} / 2 \\ Π_{1} e / 2 & 0 \end{matrix}] \cdot W = 0 (iv) [\begin{matrix} 0 & e^{T} Π_{2} / 2 \\ Π_{2} e / 2 & 0 \end{matrix}] \cdot W = 0 (v) [\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}] \cdot W = 1 (vi) [\begin{matrix} 0 & e \\ e & 0 \end{matrix}] \cdot W = θ_{1} (vii) [\begin{matrix} 0 & e \\ e & E \end{matrix}] \cdot W = θ_{2} (viii) W is positive semi - definite & (21) \end{matrix}

where E is a matrix block with all the elements equal to one, the constraint (v) ensures that W_ij=1, and the constraints (vi) and (vii) are bound controllers with some constants θ₁and θ₂.

[0034] The objective function of Equation 21 represents a standard SDP problem. The first column of W (except W_ij) can be regarded as the representation of ω. The objective function can be solved using various iterative algorithms such as an interior-point method SDPA to identify ω. The clustering system can then use various clustering techniques of ω to identify the clusters.

[0035] The clustering system can be adapted to perform co-clustering for more than three different types of heterogeneous objects. If k different types of objects are to be co-clustered, then the k-partite graph can be divided into k−1 bipartite graphs. The clustering system represents the objective function as the following:

[0036]

\begin{matrix} {\begin{matrix} \min \sum_{i = 1}^{k - 1} β_{i} \frac{q_{i}^{T} L^{(i)} q_{i}}{q_{i}^{T} D^{(i)} q_{i}} \\ s . t . (i) q_{i}^{T} D^{(i)} e = 0, q_{i} \neq 0, i = 1, \dots, k - 1^{'} \\ (ii) \sum_{i = 1}^{k - 1} β_{i} = 1, 0 < β_{i} < 1 \end{matrix} & (22) \end{matrix}

where q_i, i=1, . . . , k−1 are indicating vectors for the local bipartite graphs. The clustering system can transform Equation 22 to a QCQP problem that is solved as a SDP problem.

[0037] FIG. 3 is a block diagram illustrating components of the clustering system in one embodiment. The clustering system 300 includes object relationships stores such as images/features store 311 and images/terms store 312. Each object relationships store indicates the relationship between objects of a base object type (e.g., images) and objects of another object type (e.g., features). The object relationships stores may be generated by various components (not illustrated) such as an image crawler that crawls the web for images and surrounding text. The image crawler then identifies low-level features of the images and stores the information in the images/features store. The image crawler may count the number of occurrences of terms of the surrounding text and store the number as weights in the images/terms store. The clustering system also includes a consistent bipartite graph co-partitioning component 321, a consistent bipartite graph co-partitioning by semi-definite programming component 322, a form Laplacian matrices component 323, and a generate extended matrices component 324. The CBGC component identifies clusters by solving the objective function of Equation 12. The CBGC by SDP component identifies clusters by solving the objective function of Equation 16 represented as a semi-definite programming problem. The form Laplacian matrices component is invoked to generate the Laplacian matrices for the bipartite graphs of object relationships. The generate extended matrices component is invoked to generate the extended matrices for reformulation of the objective function to an SDP problem.

[0038] The computing devices on which the clustering system may be implemented may include a central processing unit, memory, input devices (e.g., keyboard and pointing devices), output devices (e.g., display devices), and storage devices (e.g., disk drives). The memory and storage devices are computer-readable media that may contain instructions that implement the clustering system. In addition, the data structures and message structures may be stored or transmitted via a data transmission medium, such as a signal on a communications link. Various communications links may be used, such as the Internet, a local area network, a wide area network, or a point-to-point dial-up connection to connect the clustering system to other devices (e.g., web servers).

[0039] The clustering system may be used in various operating environments that include personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

[0040] The system may be described in the general context of computer-executable instructions, such as program modules, executed by one or more computers or other devices. Generally, program modules include routines, programs, objects, components, data structures, and so on that perform particular tasks or implement particular abstract data types. Typically, the functionality of the program modules may be combined or distributed as desired in various embodiments.

[0041] FIG. 4 is a flow diagram illustrating processing of the CBGC component of the clustering system in one embodiment. The component is passed information of the object relationships stores. In block 401, the component generates the matrix A representing the relationship between objects of a base object type (e.g., images) and objects of another object type (e.g., features). In block 402, the component generates the matrix B representing the relationship between objects of a base object type and objects of another object type (e.g., terms). In block 403, the component retrieves the weight for linearly combining the local objective functions. In block 404, the component invokes the form Laplacian matrices component to form the matrices D and L for matrices A and B. In block 405, the component solves Equation 12. In block 406, the component identifies the clusters based on the solution to the equation. The component then completes.

[0042] FIG. 5 is a flow diagram that illustrates the processing of the form Laplacian matrices component of the clustering system in one embodiment. The component is passed matrices A and B. In block 501, the component forms the diagonal matrix A as defined by Equation 3. In block 502, the component forms the diagonal matrix for matrix B as defined by Equation 3. In block 503, the component forms the Laplacian matrix for matrix A as defined by Equation 4. In block 504, the component forms the Laplacian matrix for matrix B as defined by Equation 4. The component then returns.

[0043] FIG. 6 is a flow diagram that illustrates the processing of the CBGC by SDP component of the clustering system in one embodiment. The component is passed the information of the object relationships stores. In block 601, the component retrieves a weight for linearly combining the local objective functions and parameters for the SDP problem. In block 602, the component invokes the form Laplacian matrices component. The invoked component generates the diagonal matrices and Laplacian matrices D^(f), D^(w), L^(f), and L^(w)for the relationship matrices A and B. In block 603, the component invokes the generate extended matrices component. The invoked component extends matrices D^(f), D^(w), L^(f), and L^(w)to matrices Π₁, Π₂, Γ₁, and Γ₂, and forms Γ, as defined by Equations 13 and 14. In block 604, the component solves Equation 16 using the interior-point method SDP. In block 605, the component extracts the vector ω. In block 606, the component performs a K-means clustering on the vector. The component then completes.

[0044] FIG. 7 is a flow diagram that illustrates the processing of the generate extended matrices component of the clustering system in one embodiment. In blocks 701-702, the component generates the extended matrices for the Laplacian transforms. In blocks 703-704, the component generates the extended matrices for the diagonals. The component then returns.

[0045] Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims. Accordingly, the invention is not limited except as by the appended claims.

Claims

What is claimed is:

1. A computing system with a processor and memory 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

where the cut-based objective function is represented as:

\min [β \frac{q^{T} L^{(1)} q}{q^{T} D^{(1)} q} + (1 - β) \frac{p^{T} L^{(2)} p}{p^{T} D^{(2)} p}]

s . t . (i) q^{T} D^{(1)} e = 0, q \neq 0

(ii) p^{T} D^{(2)} e = 0, p \neq 0

(iii) 0 < β < 1

where A is a matrix representing the first bipartite graph and a_ijis element i and j of A, B is a matrix representing the second bipartite graph and b_ijis element i and j of B, D⁽¹⁾is a diagonal matrix represented as

D⁽¹⁾_ii=Σ_ka_ik,

D⁽²⁾is a diagonal matrix represented as

D⁽²⁾_ii=Σ_kb_ik,

L⁽¹⁾is a Laplacian matrix represented as

L⁽¹⁾=D−A,

L⁽²⁾is a Laplacian matrix represented as

L⁽²⁾=D−B,

e is a column vector with all its elements equal to 1, q is a column vector with q_i=c₁when i is an object in one cluster and q_i=−c₂when i is an object in a secoid cluster, p_i=c₁when i is an object in one cluster and p_i=−c₂when i is an: object in a second cluster, and β represents a weight of the relationships of the first bipartite graph and the second bipartite graph.

2. The system of claim 1 wherein the cut-based objective function is a normalized cut objective function.

3. The system of claim 1 wherein the cut-based objective function is solved using semi-definite programming.

4. The system of claim 1 wherein vertices of the graphs represent objects and edges represent relationships between objects.

5. The system of claim 1 wherein the cut-based objective function is solved using semi-definite programming.

6. The system of claim 1 wherein the types of objects include images, visual features, and surrounding text.

7. The system of claim 1 wherein the types of objects include users, queries, and search results.

8. The system of claim 1 wherein the types of objects include documents, authors, and keywords.

9. The system of claim 1 including representing relationships between objects of the third type and objects of other types using bipartite graphs and extending the cut-based objective function to encompass the additional bipartite graphs.

10. A computing system with a processor and memory 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;

a component that identifies clusters of objects from the solution; and

wherein the objective function is represented as:

\min ⌊ β \frac{ω^{T} Γ_{1} ω}{ω^{T} Π_{1} ω} + (1 - β) \frac{ω^{T} Γ_{2} ω}{ω^{T} Π_{2} ω} ⌋

\begin{matrix} s . t . & (i) ω^{T} Π_{1} e = 0 \\ (ii) ω^{T} Π_{2} e = 0 \\ (iii) ω \neq 0, 0 < β < 1 \end{matrix}

where

Γ_{1} = {[\begin{matrix} L^{(1)} & 0 \\ 0 & 0 \end{matrix}]}_{s \times s}, Γ_{2} = {[\begin{matrix} 0 & 0 \\ 0 & L^{(2)} \end{matrix}]}_{s \times s}

Π_{1} = {[\begin{matrix} D^{(1)} & 0 \\ 0 & 0 \end{matrix}]}_{s \times s}, {Π_{2} [\begin{matrix} 0 & 0 \\ 0 & D^{(2)} \end{matrix}]}_{s \times s}

where A is a matrix representing the first bipartite graph and a_ijis element i and j of

A, B is a matrix representing the second bipartite graph and b_ijis element i and j of

B, D⁽¹⁾is a diagonal matrix represented as

D⁽¹⁾_ii=Σ_ka_ik,

D⁽²⁾is a diagonal matrix represented as

D⁽²⁾_ii=Σ_kb_ik,

L⁽¹⁾is a Laplacian matrix represented as

L⁽¹⁾=D−A,

L⁽²⁾is a Laplacian matrix represented as

L⁽²⁾=D−B,

e is a column vector with all its elements equal to 1, q is a column vector with q_i=c₁when i is an object in one cluster and q_i=−c₂when i is an object in a second cluster, p_i=c₁when i is an object in one cluster and p_i=−c₂when i is an object in a second cluster, and β represents a weight of the relationships of the first bipartite graph and the second bipartite graph.

11. The system of claim 10 wherein the component that solves the cut-based objective function does so by reformulating a quadratically constrained quadratic programming problem into a semi-definite programming problem.

12. The system of claim 11 wherein the reformulating includes relaxing the product terms w_iw_jto an element Ω_ijof a symmetric matrix Ω.

13. The system of claim 12 wherein the semi-definite programming problem is represented as follows:

\min_{ω, Ω} [\begin{matrix} 0 & 0 \\ 0 & Γ \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}]

s . t . (i) [\begin{matrix} - e^{T} Π_{1} e & 0 \\ 0 & Π_{1} \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] = 0

(ii) [\begin{matrix} - e^{T} Π_{2} e & 0 \\ 0 & Π_{2} \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] = 0

(iii) [\begin{matrix} 0 & e^{T} Π_{1} / 2 \\ Π_{1} e / 2 & 0 \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] = 0

(iv) [\begin{matrix} 0 & e^{T} Π_{2} / 2 \\ Π_{2} e / 2 & 0 \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] = 0

(v) [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] is positive semi - definite .

14. The system of claim 13 wherein approximating the semi-definite programming problems by relaxing the constraint of Ω=w_iw_jis represented as:

\min_{ω} [\begin{matrix} 0 & 0 \\ 0 & Γ \end{matrix}] \cdot W

s . t . (i) [\begin{matrix} - e^{T} Π_{1} e & 0 \\ 0 & Π_{1} \end{matrix}] \cdot W = 0

(ii) [\begin{matrix} - e^{T} Π_{2} e & 0 \\ 0 & Π_{2} \end{matrix}] \cdot W = 0

(iii) [\begin{matrix} 0 & e^{T} Π_{1} / 2 \\ Π_{1} e / 2 & 0 \end{matrix}] \cdot W = 0

(iv) [\begin{matrix} 0 & e^{T} Π_{2} / 2 \\ Π_{2} e / 2 & 0 \end{matrix}] \cdot W = 0

(v) [\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}] \cdot W = 1

(vi) [\begin{matrix} 0 & e \\ e & 0 \end{matrix}] \cdot W = θ_{1} (vii) [\begin{matrix} 0 & e \\ e & E \end{matrix}] \cdot W = θ_{2} (viii) W is positive semi - definite

where E is a matrix block with all the elements equal to one the constraint (v) ensures that W_ij=1, and the constraints (vi) and (vii) are bound controllers with some constants θ and θ₂.

15. The system of claim 10 wherein the types of objects include images, visual features, and surrounding text.

16. The system of claim 10 wherein the types of objects include users, queries, and search results.

17. A computer-readable storage medium containing instructions for controlling a computing device to co-cluster objects of heterogeneous types, by a method comprising:

representing relationships between objects of a first type and objects of a third type as a first bipartite graph;

representing relationships between objects of a second type and objects of the third type as a second bipartite graph;

providing a cut-based objective function representing relationships across cuts for both the first bipartite graph and the second bipartite graph;

solving the cut-based objective function using semi-definite programming;

identifying clusters of objects from the solution to the objective function; and

where the cut-based objective function is represented as:

\min ⌊ β \frac{q^{T} L^{(1)} q}{q^{T} D^{(1)} q} + (1 - β) \frac{p^{T} L^{(2)} p}{p^{T} D^{(2)} p} ⌋

\begin{matrix} s . t . & (i) q^{T} D^{(1)} e = 0, q \neq 0 \\ (ii) p^{T} D^{(2)} e = 0, p \neq 0 \\ (iii) 0 < β < 1 \end{matrix}

is where A is a matrix representing the first bipartite graph and a_ij.is element i and j of A, B a matrix representing the second bipartite graph and b_ij.is element i and j of B, DO) is a diagonal matrix represented as

D⁽¹⁾_ij=Σ_ka_ik,

D⁽²⁾is a diagonal matrix represented as

D⁽²⁾_ij=Σ_kb_ik,

L⁽¹⁾is a Laplacian matrix represented as

L⁽¹⁾=D−A,

L⁽²⁾is a Laplacian matrix represented as

L⁽²⁾=D−B,

18. The computer-readable storage medium of claim 17 wherein the cut-based objective function is a normalized cut objective function.

Patent Citations (15)

Patent	Date	Inventor	Cited By
US6263334(B1)	2001-07-01	Fayyad et al.	Applicant
US6269376(B1)	2001-07-01	Dhillon et al.	Applicant
US6560597(B1)	2003-05-01	Dhillon et al.	Applicant
US6581058(B1)	2003-06-01	Fayyad et al.	Applicant
US6976020(B2)	2005-12-01	Anthony et al.	Examiner
US7039638(B2)	2006-05-01	Zhang et al.	Applicant
US7072891(B2)	2006-07-01	Lee et al.	Applicant
US7272543(B2)	2007-09-01	Estevez-Schwarz et al.	Examiner
US2003/0069908(A1)	2003-04-01	Anthony et al.	Examiner
US2003/0084421(A1)	2003-05-01	Estevez-Schwarz et al.	Examiner
US2003/0154181(A1)	2003-08-01	Liu et al.	Applicant
US2003/0204484(A1)	2003-10-01	Charpiot et al.	Applicant
US2005/0015366(A1)	2005-01-01	Carrasco et al.	Examiner
US2005/0203889(A1)	2005-09-01	Okubo et al.	Examiner
US2006/0242093(A1)	2006-10-01	Richardson et al.	Examiner

Non-Patent Literature (53)

“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.Examiner
“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).Examiner
“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).Examiner
U.S. Appl. No. 11/621,848, Liu et al.Applicant
“SDP Semidefinite Programming,” 2 pages, http://www-user.tu-chemnitz.de/˜helmberg/semidef.html [last accessed Nov. 29, 2006].Applicant
“SDPA Online Introduction,” 5 pages, http://grid.r.dendai.ac.jp/sdpa/intro.html [last accessed Jan. 9, 2006].Applicant
Bach, Francis R. and Michael I. Jordan, “Learning Spectral Clustering,” Neural Info. Processing Systems 16, NIPS 2003, 8 pages.Applicant
Baeza-Yates, R. and B. Ribeiro-Neto, “Chapter 2 Modeling,” Modern Information Retrieval, © 1999 by the ACM Press, pp. 19-71.Applicant
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.Applicant
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.Applicant
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.Applicant
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.Applicant
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.Applicant
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.Applicant
Chen, Yixin, James Z. Wang and Robert Krovetz, “Content-Based Image Retrieval by Clustering,” MIR'03, Berkeley, California, © 2003 ACM Press, pp. 193-200.Applicant
Dhillon, Inderjit S., “Co-clustering documents and words using Bipartite Spectral Graph Partitioning,” In KDD'01, San Francisco, California, pp. 269-274, © 2001 ACM.Applicant
Dhillon, Inderjit S., Subramanyam Mallela and Dharmendra S. Modha, “Information-Theoretic Co-clustering,” SIGKDD'03, Aug. 2003, Washington, DC, pp. 89-98, © 2003 ACM.Applicant
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.Applicant
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.Applicant
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.Applicant
El-Yaniv, Ran and Oren Souroujon, “Iterative Double Clustering for Unsupervised and Semi-Supervised Learning,” In Proceedings of ECML'01, pp. 121-132, 2001.Applicant
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.Applicant
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].Applicant
Fujisawa, Katsuki et al., “Numerical Evaluation of SDPA (SemiDefinite Programming Algorithm),” Revised Sep. 1998, 29 pages.Applicant
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.Applicant
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.Applicant
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.Applicant
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.Applicant
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.Applicant
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.Applicant
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.Applicant
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.Applicant
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.Applicant
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 Society, pp. 173-188.Applicant
Pothen, Alex et al., “Partitioning Sparse Matrices with Eigenvectors of Graphs,” Dec. 27, 1989, Siam J. Matrix Anal. Appl., vol. 11, No. 3, Jul. 1990, © 1990 Society for Industrial and Applied Mathematiocs, pp. 430-452.Applicant
Qiu, Guoping, “Image and Feature Co-Clustering,” ICPR 4, 2004, pp. 991-994.Applicant
Rodden, Kerry et al., “Does Organisation by Similarity Assist Image Browsing?,” SIGCHI'01, Seattle, © 2001 ACM, 8 pages.Applicant
Shi, Jianbo and Jitendra Malik, “Normalized Cuts and Image Segmentation,” Nov. 16, 1999, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, No. 8, Aug. 2000, © 2000 IEEE, pp. 888-905.Applicant
Slonim, Noam and Naftali Tishby, “Document Clustering using Word Clusters via the Information Bottleneck Method,” SIGIR 2000, 7/00, Athens, Greece, pp. 208-215, © 2000 ACM.Applicant
Taeprasartsit, Pinyo and Liang Guo, “Texture Analysis and Classification with Tree-Structured Wavelet Transform,” May 2, 2004, CSE/EE 585 Final Project, Spring 2004, pp. 1-24.Applicant
Wang, Jidong et al., “ReCoM: Reinforcement Clustering of Multi-Type Interrelated Data Objects,” SIGIR'03, Jul. 28-Aug. 1, 2003, Toronto, Canada, pp. 274-281, © 2003 ACM.Applicant
Weisstein, Eric W., “Complex Conjugate,” From MathWorld—A Wolfram Web Ressource, 3 pages, http://mathworld.wolfram.com/ComplexConjugate.html [last accessed Jan. 8, 2006].Applicant
Weisstein, Eric W., “Complex Number,” From MathWorld—A Wolfram Web Resource, 4 pages, http://mathworld.wolfram.com/ComplexNumber.html [last accessed Nov. 30, 2006].Applicant
Weisstein, Eric W., “Conjugate Matrix,” From MathWorld—A Wolfram Web Resource, 1 page, http://mathworld.wolfram.com/ConjugateMatrix.html [last accessed Jan. 8, 2006].Applicant
Weisstein, Eric W., “Conjugate Transpose,” From MathWorld—A Wolfram Web Resource, 2 pages, http://mathworld.wolfram.com/ConjugateTranspose.html [last accessed Jan. 8, 2006].Applicant
Weisstein, Eric W., “Eigenvalue,” From MathWorld—A Wolfram Web Resource, 3 pages, http://mathworld.wolfram.com/Eigenvalue.html [last accessed Jan. 8, 2006].Applicant
Weisstein, Eric W., “Eigenvector,” From MathWorld—A Wolfram Web Resource, 3 pages, http://mathworld.wolfram.com/Eigenvector.html [last accessed Jan. 8, 2006].Applicant
Weisstein, Eric W., “Hermitian Matrix,” From MathWorld—A Wolfram Web Resource, 2 pages, http://mathworld.wolfram.com/HermitianMatrix.html [last accessed Jan. 8, 2006].Applicant
Weisstein, Eric W., “Laplacian Matrix,” From MathWorld—A Wolfram Web Resource, 1 page, http://mathworld.wolfram.com/LaplacianMatrix.html [last accessed Jan. 8, 2006].Applicant
Weisstein, Eric W., “Positive Semidefinite Matrix,” From MathWorld—A Wolfram Web Resource, 1 page, http://mathworld.wolfram.com/PositiveSemidefiniteMatrix.html [last accessed Jan. 8, 2006].Applicant
Weisstein, Eric W., “Self-Adjoint Matrix,” From MathWorld—A Wolfram Web Resource, 1 page, http://mathworld.wolfram.com/Self-AdjointMatrix.html [last accessed Jan. 8, 2006].Applicant
Zha, Hongyuan et al., “Bipartite Graph Partitioning and Data Clustering,” In proceedings of CIKM'01, Atlanta, Georgia, © 2001 ACM, pp. 25-32.Applicant
Zhao, Rong and William I. Grosky, “Narrowing the Semantic Gap—Improved Text-Based Web Document Retrieval Using Visual Features,” IEEE Transactions on Multimedia, vol. 4, No. 2, Jun. 2002, © 2002 IEEE, pp. 189-200.Applicant

Abstract

Description

Background

Summary

Brief Description of the Drawings

[0006] FIG. 1 is a diagram representing a tripartite graph illustrating relationships between low-level features, images, and text.

[0007] FIG. 2 illustrates the transforming of a tripartite graph into two bipartite graphs.

[0008] FIG. 3 is a block diagram illustrating components of the clustering system in one embodiment.

[0009] FIG. 4 is a flow diagram illustrating processing of the CBGC component of the clustering system in one embodiment.

[0010] FIG. 5 is a flow diagram that illustrates the processing of the form Laplacian matrices component of the clustering system in one embodiment.

[0011] FIG. 6 is a flow diagram that illustrates the processing of the CBGC by SDP component of the clustering system in one embodiment.

[0012] FIG. 7 is a flow diagram that illustrates the processing of the generate extended matrices component of the clustering system in one embodiment.

Detailed Description

[0016]

\begin{matrix} \min \frac{q^{T} Lq}{q^{T} Dq}, s . t . q^{T} De = 0, q \neq 0 & (1) \end{matrix}

where G=(V, E) represents a graph G with vertices V and edges E, the weights of the relationships are represented as:

[0017]

\begin{matrix} M_{ij} = {\begin{matrix} E_{ij}, & if < i, j > \in E \\ 0, & otherwise, \end{matrix} & (2) \end{matrix}

[0021]

\begin{matrix} \min \frac{q^{T} L^{(f)} q}{q^{T} D^{(f)} q} \min \frac{p^{T} L^{(w)} p}{p^{T} D^{(w)} p} s . t . (i) q^{T} D^{(f)} e = 0, q \neq 0 (ii) p^{T} D^{(w)} e = 0, p \neq 0 & (11) \end{matrix}

The clustering system models the consistent co-partitioning problem by linearly combining the multiple local objective functions into a global objective function subject to constraints as follows:

[0022]

\begin{matrix} \min [β \frac{q^{T} L^{(f)} q}{q^{T} D^{(f)} q} + (1 - β) \frac{p^{T} L^{(w)} p}{p^{T} D^{(w)} p}] s . t . (i) q^{T} D^{(f)} e = 0, q \neq 0 (ii) p^{T} D^{(w)} e = 0, p \neq 0 (iii) 0 < β < 1 & (12) \end{matrix}

where β is a weighting parameter indicating the relative weight to be given the relationships of the bipartite graphs.

[0024]

\begin{matrix} Γ_{1} = {[\begin{matrix} L^{(f)} & 0 \\ 0 & 0 \end{matrix}]}_{s \times s}, Γ_{2} = {[\begin{matrix} 0 & 0 \\ 0 & L^{(w)} \end{matrix}]}_{s \times s} & (13) \end{matrix}

[0025]

\begin{matrix} Π_{1} = {[\begin{matrix} D^{(f)} & 0 \\ 0 & 0 \end{matrix}]}_{s \times s}, Π_{2} = {[\begin{matrix} 0 & 0 \\ 0 & D^{(w)} \end{matrix}]}_{s \times s} & (14) \end{matrix}

The objective function can be written subject to constraints as follows:

[0026]

\begin{matrix} \min [β \frac{ω^{T} Γ_{1} ω}{ω^{T} Π_{1} ω} + (1 - β) \frac{ω^{T} Γ_{2} ω}{ω^{T} Π_{2} ω}] s . t . (i) ω^{T} Π_{1} e = 0 (ii) ω^{T} Π_{2} e = 0 (iii) ω \neq 0, 0 < β < 1 & (15) \end{matrix}

[0027]

\begin{matrix} Γ = \frac{β}{e^{T} Π_{1} e} Γ_{1} + \frac{1 - β}{e^{T} Π_{2} e} Γ_{2}, 0 < β < 1 & (17) \end{matrix}

[0029]

\begin{matrix} C •W = \sum_{i, j} C_{ij} W_{ij} & (19) \end{matrix}

[0030] The clustering system reformulates this QCQP problem as an SDP problem by relaxing the product terms w_iw_jto an element Ω_ijof a symmetric matrix Ω:

[0031]

\begin{matrix} \min_{ω, Ω} [\begin{matrix} 0 & 0 \\ 0 & Γ \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] s . t . (i) [\begin{matrix} - e^{T} Π_{1} e & 0 \\ 0 & Π_{1} \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] = 0 (ii) [\begin{matrix} - e^{T} Π_{2} e & 0 \\ 0 & Π_{2} \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] = 0 (iii) [\begin{matrix} 0 & e^{T} Π_{1} / 2 \\ Π_{1} e / 2 & 0 \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] = 0 (iv) [\begin{matrix} 0 & e^{T} \prod_{2} / 2 \\ \prod_{2} e / 2 & 0 \end{matrix}] \cdot [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] = 0 (v) [\begin{matrix} 1 & ω^{T} \\ ω & Ω \end{matrix}] is positive semi - definite & (20) \end{matrix}

[0033]

\begin{matrix} \min_{ω} [\begin{matrix} 0 & 0 \\ 0 & Γ \end{matrix}] \cdot W s . t . (i) [\begin{matrix} - e^{T} Π_{1} e & 0 \\ 0 & Π_{1} \end{matrix}] \cdot W = 0 (ii) [\begin{matrix} - e^{T} Π_{2} e & 0 \\ 0 & Π_{2} \end{matrix}] \cdot W = 0 (iii) [\begin{matrix} 0 & e^{T} Π_{1} / 2 \\ Π_{1} e / 2 & 0 \end{matrix}] \cdot W = 0 (iv) [\begin{matrix} 0 & e^{T} Π_{2} / 2 \\ Π_{2} e / 2 & 0 \end{matrix}] \cdot W = 0 (v) [\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}] \cdot W = 1 (vi) [\begin{matrix} 0 & e \\ e & 0 \end{matrix}] \cdot W = θ_{1} (vii) [\begin{matrix} 0 & e \\ e & E \end{matrix}] \cdot W = θ_{2} (viii) W is positive semi - definite & (21) \end{matrix}

where E is a matrix block with all the elements equal to one, the constraint (v) ensures that W_ij=1, and the constraints (vi) and (vii) are bound controllers with some constants θ₁and θ₂.

[0036]

\begin{matrix} {\begin{matrix} \min \sum_{i = 1}^{k - 1} β_{i} \frac{q_{i}^{T} L^{(i)} q_{i}}{q_{i}^{T} D^{(i)} q_{i}} \\ s . t . (i) q_{i}^{T} D^{(i)} e = 0, q_{i} \neq 0, i = 1, \dots, k - 1^{'} \\ (ii) \sum_{i = 1}^{k - 1} β_{i} = 1, 0 < β_{i} < 1 \end{matrix} & (22) \end{matrix}

where q_i, i=1, . . . , k−1 are indicating vectors for the local bipartite graphs. The clustering system can transform Equation 22 to a QCQP problem that is solved as a SDP problem.

Claims

What is claimed is:

1. A computing system with a processor and memory 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

where the cut-based objective function is represented as:

\min [β \frac{q^{T} L^{(1)} q}{q^{T} D^{(1)} q} + (1 - β) \frac{p^{T} L^{(2)} p}{p^{T} D^{(2)} p}]

s . t . (i) q^{T} D^{(1)} e = 0, q \neq 0

(ii) p^{T} D^{(2)} e = 0, p \neq 0

(iii) 0 < β < 1