SPECTRAL CLUSTERING FOR MULTI-TYPE RELATIONAL DATA

• US 20080294686A1
• Filed: 05/22/2008
• Published: 11/27/2008
• Est. Priority Date: 05/25/2007
• Status: Active Grant

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Zhang, Zhongfei, Long, Bo
• Granted Patent: US 8,185,481 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts

Abstract

A general model is provided which provides collective factorization on related matrices, for multi-type relational data clustering. The model is applicable to relational data with various structures. Under this model, a spectral relational clustering algorithm is provided to cluster multiple types of interrelated data objects simultaneously. The algorithm iteratively embeds each type of data objects into low dimensional spaces and benefits from the interactions among the hidden structures of different types of data objects.

Claims

1. A method comprising:

(a) embodying data structures on a computer readable medium, the data structures comprising;

(i) data objects, each data object including a vector with a plurality of elements of a corresponding respective type;

(ii) feature matrices, there being a feature matrix corresponding with each data object;

(iii) relationship matrices describing pairwise relationships between the data objects; and

(iv) weighting matrices;

(b) effecting a spectral clustering algorithm on at least one data processing device, the spectral clustering algorithm comprising;

(i) assigning, to each of a plurality of vigorous cluster indicator matrices, leading eigenvectors derived from a formula that is a function of the feature matrices, the relationship matrices, the weight matrices and at least one cluster indicator matrix other than the one receiving the assigning;

(ii) iteratively improving the vigorous cluster indicator matrices; and

(iii) transforming the vigorous cluster indicator matrices into a set of cluster indicator matrices comprising a cluster indicator matrix for each data object; and

(c) recognizing a clustering of the elements within a data object based on the cluster indicator matrices.

2. The method of claim 1, wherein the clustering comprises multi-type relational data clustering, and wherein the spectral clustering algorithm performs collective factorization on the relationship matrices and feature matrices.

3. The method of claim 2, wherein collective factorization comprises minimizing L, where

$L=\sum _{}$

1 ≤

i ≤

j ≤

m 

w a ( ij ) 



R ( ij ) - C ( i ) 

A ( ij ) 

( C ( j ) ) T 

2 + ∑

1 ≤

i ≤

m 

w b ( i ) 



F ( i ) - C ( i ) 

B ( i ) 

2

w.r.t. C^(p) ∈

{0,1}<sup>n→

i×

ki</sup>, A^(ij) ∈

<sup>ki×

kj</sup>, and B⁽ⁱ⁾ ∈

<sup>ki×

fi</sup> subject to the constraints;

$\underset{q=1}{\overset{k_i}{\sum <br><br>}}<br><br>C_{\mathrm{pq}}^{\left(i\right)}=1,$

where;

1≦

p≦

n_i, 1≦

i ≦

j≦

m,

∥

·

∥

denotes the Frobenius norm for a matrix;

C⁽ⁱ⁾ ∈

{0,1}<sup>ni×

ki</sup> is a cluster indicator matrix for data object χ

_i such that

$\underset{q=1}{\overset{k_i}{\sum <br><br>}}<br><br>C_{\mathrm{pq}}^{\left(i\right)}=1$

and C_pq⁽ⁱ⁾ denotes that the p^th object in χ

_i is associated with the q^th cluster;

A^(ij) ∈

<sup>ki×

kj</sup> is a cluster association matrix such that A_pq^ij denotes the association between cluster p of χ

_i and cluster q of χ

_j;

F⁽ⁱ⁾ ∈

<sup>ni×

fi</sup> is a feature matrix of χ

_i, the cluster structure of which being reflected in the factorization of F⁽ⁱ⁾ such that F⁽ⁱ⁾≈

C⁽ⁱ⁾B⁽ⁱ⁾; and

B⁽ⁱ⁾ ∈

<sup>ki×

fi</sup> is the feature basis matrix which consists of k_i basis vectors in the feature space, each a representing cluster center.

4. The method of claim 1, wherein the clustering comprises iteratively embedding each type of data object into at least one low dimensional space.

5. The method of claim 4, wherein the clustering benefits from interactions among hidden structures of different types of data objects, the interactions being characterizable by clusters.

6. The method of claim 4, wherein clustering comprises achieving a dimensionality having an order less than a number of elements in a data object, by taking a predetermined number of leading eigenvectors of a matrix including values that relate to more than one type of data.

7. The method of claim 1, wherein a vigorous cluster indicator matrix is updated as the leading k eigenvectors of the matrix product, where k is a number of clusters sought.

8. The method of claim 1, wherein the spectral clustering algorithm computes the following formula:

$\underset{{\left(C^{\left(p\right)}\right)}^T<br><br>C^{\left(p\right)}=I_{k_p}}{\max }<br><br>\mathrm{tr}\left({\left(C^{\left(p\right)}\right)}^T<br><br>M^{\left(p\right)}<br><br>C^{\left(p\right)}\right)$

M^(p) being a joint function of at least

$w_b^{\left(p\right)}\left({F^{\left(p\right)}<br><br>\left(F^{\left(p\right)}\right)}^T\right),<br><br>\underset{p<<br><br>j\le <br><br>m}{\sum <br><br>}<br><br>w_a^{\left(\mathrm{pj}\right)}(\left(R^{\left(\mathrm{pj}\right)}<br><br>{C^{\left(j\right)}<br><br>\left(C^{\left(j\right)}\right)}^T<br><br>\left(R^{{\left(\mathrm{pj}\right)}^T}\right)\right),<br><br>\mathrm{and}<br><br><br><br>\underset{1\le <br><br>j<<br><br>p}{\sum <br><br>}<br><br>w_a^{\left(\mathrm{pj}\right)}\left({\left(R^{\left(\mathrm{jp}\right)}\right)}^T<br><br>{C^{\left(j\right)}<br><br>\left(C^{\left(j\right)}\right)}^T<br><br>\left(R^{\left(\mathrm{pj}\right)}\right)\right)$

where

C^(p) is the vigorous cluster indicator matrix for cluster number p;

superscript T indicates the transpose of a matrix;

R^(ij) is a relationship matrix indicating a relationship between two data objects X_i and X_j;

j and p are index variables such that 1≦

j, p≦

m, j≠

p;

F^(p) is a feature matrix relating to data object p;

m is the number of data objects being considered;

w_b^(p) indicates an element of a weighting vector relating to the feature matrices; and

w_a^(jp) and w_a^(pj) indicate elements of weighting matrices relating to clustering, the weighting matrices being specified by a user

9. The method of claim 8, wherein M^(p) is further a joint function of w_s^(p)S^(p) where S^(p) is a symmetric matrix denoting intra-type relationships within a data object vector;

and w_s^(p) denotes a weight for S^(p).

10. The method of claim 1, wherein the spectral clustering algorithm comprises using the following algorithm:

Input;

Relation matrices {R^(ij) ∈

<sup>ni×

nj</sup>}<sub>1≦

i≦

j≦

m</sub>, feature matrices {F⁽ⁱ⁾ ∈

<sup>ni×

fi</sup>}<sub>1≦

i≦

j≦

m</sub>, numbers of clusters {k_i}<sub>1≦

i≦

m</sub>, weights {w_a^(ij), w_b⁽ⁱ⁾ ∈

R₊}<sub>1≦

i≦

j≦

m</sub>.. Output;

Cluster indicator matrices {C^(p)}<sub>1≦

p≦

m</sub>. Method;

a;

Initialize {C^(p)}<sub>1≦

p≦

m</sub> with othonormal matrices. b;

repeat  

 

c;

for p = 1 to m do  

 

 

 

d;

Compute the matrix M^(p)  

 

 

 

e;

Update C^(p) by the leading k_p eigenvectors of M^(p).  

 

f;

end for g;

until convergence h;

for p = 1 to m do  

 

i;

transform C^(p) into a cluster indicator matrix by k-means. j;

end for

where

n_i is a number of elements in data object i;

f_i is a number of features for data object i

M^(p) being a joint function of at least

$w_b^{\left(p\right)}\left({F^{\left(p\right)}<br><br>\left(F^{\left(p\right)}\right)}^T\right),<br><br>\underset{p<<br><br>j\le <br><br>m}{\sum <br><br>}<br><br>w_a^{\left(\mathrm{pj}\right)}(\left(R^{\left(\mathrm{pj}\right)}<br><br>{C^{\left(j\right)}<br><br>\left(C^{\left(j\right)}\right)}^T<br><br>\left(R^{{\left(\mathrm{pj}\right)}^T}\right)\right),<br><br>\mathrm{and}<br><br><br><br>\underset{1\le <br><br>j<<br><br>p}{\sum <br><br>}<br><br>w_a^{\left(\mathrm{pj}\right)}\left({\left(R^{\left(\mathrm{jp}\right)}\right)}^T<br><br>{C^{\left(j\right)}<br><br>\left(C^{\left(j\right)}\right)}^T<br><br>\left(R^{\left(\mathrm{pj}\right)}\right)\right)$

where

C^(p) is the vigorous cluster indicator matrix for cluster number p;

superscript T indicates the transpose of a matrix;

R^(ij) is a relationship matrix indicating a relationship between two data objects X_i and X_j;

j and p are index variables such that 1≦

j, p≦

m, j≠

p;

F^(p) is a feature matrix relating to data object p;

m is the number of data objects being considered;

w_b^(p) indicates an element of a weighting vector relating to the feature matrices; and

w_a^(jp) and w_a^(pj) indicate elements of weighting matrices relating to clustering, the weighting matrices being specified by a user.

11. The method of claim 10, wherein

$M^{\left(p\right)}=w_b^{\left(p\right)}({F^{\left(p\right)}}^{}$

( F ( p ) ) T ) + ∑

p <

j ≤

m 

w a ( pj ) ( ( R ( pj ) 

C ( j ) ( C ( j ) ) T 

( R ( pj ) T ) ) + ∑

1 ≤

j <

p 

w a ( pj ) ( ( R ( jp ) ) T 

C ( j ) 

( C ( j ) ) T 

( R ( pj ) ) ) + w y p 

Y ( p )

wherein w_y^(p)Y^(p) is an optional term wherein w_y^(p) is zero, and Y^(p) is a modification term.

12. The method of claim 10, wherein

$M^{\left(p\right)}=w_b^{\left(p\right)}$

( F ( p ) 

( F ( p ) ) T ) + ∑

p <

j ≤

m 

w a ( pj ) ( ( R ( pj ) 

C ( j ) 

( C ( j ) ) T 

( R ( pj ) T ) ) + ∑

1 ≤

j <

p 

w a ( jp ) ( ( R ( jp ) ) T 

C ( j ) 

( C ( j ) ) T 

( R ( jp ) ) ) + w s ( p ) 

S ( p )

where S^(p) is a symmetric matrix denoting intra-type relationships within a data object vector; and

w_s^(p) denotes a weight for S^(p).

13. A method of indicating clusters, comprising the steps of:

(a) initializing a set of matrices with orthonormal matrices representing multi-type objects, each object having a respective relation with other objects and a set of features;

(b) automatically iteratively processing a symmetric matrix comprising a set of weights, which maximizes an objective function of the orthonormal matrices, relations and the features, and then updating each orthonormal matrix by the leading eigenvectors of the symmetric matrix; and

(c) transforming each of a set of resulting updated orthonormal matrix into a cluster indicator matrix.

14. The method of claim 13, wherein the multi-type objects represent at least three types of objects.

15. The method of claim 13, further comprising the steps of performing a spectral clustering algorithm, computing at least one joint function of at least:

at least one vigorous cluster indicator matrix relating to clustering of elements in at least one of the objects; and

at least one relationship matrix relating at least two objects of different types.

16. The method of claim 15, further comprising the step of clustering multi-type relational data using collective factorization on the relationship matrices, wherein collective factorization comprises minimizing L, where

$L=\sum _{}$

1 ≤

i ≤

j ≤

m 

w a ( ij ) 



R ( ij ) - C ( i ) 

A ( ij ) 

( C ( j ) ) T 

2 + ∑

1 ≤

i ≤

m 

w b ( i ) 



F ( i ) - C ( i ) 

B ( i ) 

2

w.r.t. C⁽ⁱ⁾ ∈

{0,1}<sup>n→

i×

ki</sup>, A^(ij) ∈

<sup>ki×

kj</sup>, and B⁽ⁱ⁾ ∈

<sup>ki×

fi</sup> subject to the constraints;

$\underset{q=1}{\overset{k_i}{\sum <br><br>}}<br><br>C_{\mathrm{pq}}^{\left(i\right)}=1,$

where

1≦

p≦

n_i, 1≦

i≦

j≦

m,

∥

·

∥

denotes the Frobenius norm for a matrix;

C⁽ⁱ⁾ ∈

{0,1}<sup>ni×

ki</sup> is a cluster indicator matrix for data object χ

_i such that

$\underset{q=1}{\overset{k_i}{\sum <br><br>}}<br><br>C_{\mathrm{pq}}^{\left(i\right)}=1$

and C_pq⁽ⁱ⁾ denotes that the p^th object in χ

_i is associated with the q^th cluster;

A^(ij) ∈

<sup>ki×

kj</sup> is a cluster association matrix such that A_pq^ij denotes the association between cluster p of χ

_i and cluster q of χ

_j;

F⁽ⁱ⁾ ∈

<sup>ni×

fi</sup> is a feature matrix of χ

_i, the cluster structure of which being reflected in the factorization of F⁽ⁱ⁾ such that F⁽ⁱ⁾≈

C⁽ⁱ⁾B⁽ⁱ⁾; and

B⁽ⁱ⁾ ∈

<sup>ki×

fi</sup> is the feature basis matrix which consists of k_i basis vectors in the feature space, each a representing cluster center.

17. The method of claim 13, wherein the spectral clustering algorithm computes the following formula

$\underset{{\left(C^{\left(p\right)}\right)}^T}{\max }$

C ( p ) = I k p 

tr ( ( C ( p ) ) T 

M ( p ) 

C ( p ) )

M^(p) being a joint function of at least

$w_b^{\left(p\right)}\left({F^{\left(p\right)}<br><br>\left(F^{\left(p\right)}\right)}^T\right),<br><br>\underset{p<<br><br>j\le <br><br>m}{\sum <br><br>}<br><br>w_a^{\left(\mathrm{pj}\right)}(\left(R^{\left(\mathrm{pj}\right)}<br><br>{C^{\left(j\right)}<br><br>\left(C^{\left(j\right)}\right)}^T<br><br>\left(R^{{\left(\mathrm{pj}\right)}^T}\right)\right),<br><br>\mathrm{and}<br><br><br><br>\underset{1\le <br><br>j<<br><br>p}{\sum <br><br>}<br><br>w_a^{\left(\mathrm{pj}\right)}\left({\left(R^{\left(\mathrm{jp}\right)}\right)}^T<br><br>{C^{\left(j\right)}<br><br>\left(C^{\left(j\right)}\right)}^T<br><br>\left(R^{\left(\mathrm{pj}\right)}\right)\right)$

where

C^(p) is the vigorous cluster indicator matrix for cluster number p;

superscript T indicates the transpose of a matrix;

R^(ij) is a relationship matrix indicating a relationship between two data objects X_i and X_j;

j and p are index variables such that 1≦

j, p≦

m, j≠

p;

F^(p) is a feature matrix relating to data object p;

m is the number of data objects being considered;

w_b^(p) indicates an element of a weighting vector relating to the feature matrices; and

w_a^(jp) and w_a^(pj) indicate elements of weighting matrices relating to clustering, the weighting matrices being specified by a user.

18. A method of clustering data, comprising the steps of:

(a) providing a set of first matrices relating to at least three types of objects, each object having a set of features and a set of respective relations with respect to other objects;

(b) automatically generating a second matrix comprising a set of values, which maximizes an objective function of the sets of first matrices, features and relations; and

(c) automatically transforming each second matrix into a cluster indicator matrix.

19. The method of claim 18, wherein the matrices in the set of first matrices are orthonormal, the second matrix is symmetric, and the sets of features and relations are embodied as third and fourth sets of matrices respectively.

20. The method of claim 18, wherein the second matrix is a function of at least:

at least one relation matrix representing respective relations between distinct members of m sets to be clustered into k_p disjoint clusters, where p is an index running from 1 to m;

at least one feature matrix where each element denotes a feature value for an associated data object;

the tentative cluster characterization matrices; and

a set of weights for different types of relations and features.

21. The method of claim 18, further comprising the steps of:

collectively factorizing the set of matrices, to discover hidden structures of the objects based on both feature information and relation information; and

generating a symmetric matrix comprising a set of weights, which maximizes an objective function of the sets of orthonormal matrices, feature matrices and relation matrices;

wherein the cluster indicator matrix is derived from the collective factorization, to achieve adaptive dimensionality reduction for each type of data.

22. A computer implemented method for reducing dimensionality of data objects in a multi-type relational database, the method comprising executing operations in at least one data processing device, the operations comprising:

(a) initializing a set of matrices, which are precursors to cluster indicator matrices;

(b) iteratively processing each matrix as the leading eigenvectors of a linear combination of at least one of the following terms;

(i) at least one feature matrix product that is a feature matrix multiplied by its transpose; and

(ii) at least one relationship/cluster matrix that is a joint function of a relationship matrix, a precursor to a cluster matrix, the transpose of the precursor to the cluster matrix; and

the transpose of the relationship matrix.

23. The method of claim 22, wherein

the precursors to the cluster indicator matrices are denoted {C^(p)}_1≦

p≦

m;

the feature matrix product is denoted F^(p)(F^(p))^T;

the relationship/cluster matrix product is a function of two or more terms selected from the group ((R^(pj)C^(j)(C^(j))^T(R^(pj)T)) and ((R^(jp))^TC^(j)(C^(j))^T(R^(jp)));

j is an index variable running between p and m for the first term and between 1 and p for the second term, respectively;

R^(pj) ∈

<sup>np×

nj</sup> is a relation matrix representing a relation between data object vectors χ

_p and χ

_j, and R^(jp) ∈

<sup>nj×

np</sup> is a relation matrix representing a relation between χ

_j and χ

_p;

χ

_j and χ

_p are members of m sets to be clustered into k_j and k_p disjoint clusters, respectively; and

F^(p) ∈

<sup>np×

fj</sup> is a feature matrix where an element F_pq^(p) denotes the q^th feature value for the object χ

_p, and f_j is the number of features for χ

_i.

24. The method of claim 23, wherein the iterative processing is repeated until a convergence criterion is reached, and then transforming the iteratively processed precursors of the cluster indicator matrices into cluster indicator matrices by use of the k means algorithm.