Spectral clustering for multi-type relational data

• US 8,185,481 B2
• Filed: 05/22/2008
• Issued: 05/22/2012
• 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: Long, Bo, Zhang, Zhongfei
• Primary Examiner(s): Chen, Alan
• Assistant Examiner(s): Kim, David H
• Application Number:
  US12/125,804
• Publication Number:
  US 20080294686A1
• Time in Patent Office: 1,461 Days
• Field of Search: 706/12
• US Class Current: 706/12
• 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) a plurality of multi-type data objects, each data object including a vector with a plurality of elements of a corresponding respective type, having hidden structures relating the different data object types;

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

(iii) relationship matrices describing pairwise relationships between at least two different types of 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 that relate to more than one type of data object, 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

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.

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

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:

11. The method of claim 10, wherein

12. The method of claim 10, wherein

7. 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,

wherein the clustering comprises iteratively embedding each type of data object into at least one low dimensional space, and

wherein clustering comprises achieving a dimensionality having an order less than a number of elements in a data object, a vigorous cluster indicator matrix being updated as the leading k eigenvectors of the matrix product, where k is a number of clusters sought.

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 and hidden structures relating the different object types;

(b) automatically iteratively processing a symmetric matrix comprising a set of weights with respect to the plurality of object types for each respective object, which maximizes an objective function of the orthonormal matrices, multi-type 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 dependent on at least the hidden structures relating the different object types.

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

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

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 having hidden structures relating the different object types, each object having a set of features and a set of respective multi-type relations with respect to at least objects of differing types;

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

(c) automatically transforming each second matrix into a cluster indicator matrix dependent on at least the hidden structures relating the different object types.

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 having hidden structures relating the different object types 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, a number of said matrices corresponding to an order of the reduced dimensionality;

(b) iteratively processing each matrix as the leading eigenvectors that relate to more than one type of object 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 multi-type relationship/cluster matrix that is a joint function of a multi-type relationship matrix, a precursor to a cluster matrix, the transpose of the precursor to the cluster matrix; and

the transpose of the multi-type relationship matrix, wherein after said iteratively processing, resulting cluster indicator matrices indicate clusters dependent on at least the hidden structures relating the different object types.

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.