System and method for probabilistic relational clustering

• US 9,984,147 B2
• Filed: 06/17/2016
• Issued: 05/29/2018
• Est. Priority Date: 08/08/2008
• 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 Mark
• Primary Examiner(s): Uddin, Mohammed R
• Application Number:
  US15/186,063
• Publication Number:
  US 20160364469A1
• Time in Patent Office: 711 Days
• Field of Search: 707737, 707739, 707754, 707749, 707999101
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Relational clustering has attracted more and more attention due to its phenomenal impact in various important applications which involve multi-type interrelated data objects, such as Web mining, search marketing, bioinformatics, citation analysis, and epidemiology. A probabilistic model is presented for relational clustering, which also provides a principal framework to unify various important clustering tasks including traditional attributes-based clustering, semi-supervised clustering, co-clustering and graph clustering. The model seeks to identify cluster structures for each type of data objects and interaction patterns between different types of objects. Under this model, parametric hard and soft relational clustering algorithms are provided under a large number of exponential family distributions. The algorithms are applicable to relational data of various structures and at the same time unify a number of state-of-the-art clustering algorithms: co-clustering algorithms, the k-partite graph clustering, and semi-supervised clustering based on hidden Markov random fields.

Claims

1. A method of clustering a set of objects having respective object types, respective object attributes, homogeneous relationships between respective objects of the same object type, and heterogeneous relationships between objects having a different object types, the method comprising:

iteratively optimizing a clustering of the set of objects within a plurality of latent classes, dependent on object type, object attributes, homogeneous relationships, and heterogeneous relationships, by performing;

in an expectation step, updating a set of posteriors to maximize a probability that an object is associated with a respective latent class comprising, for each object, individually fixing an assigned latent class for all other objects, and maximizing an objective function for the respective object, comprising minimizing a computed distance between an observation of the object attributes, homogeneous relationships, and heterogeneous relationships of a respective object and parameters of a corresponding expectation that the object is associated with the respective latent class, and repeating until no object changes in assigned latent class between successive repetition, and

in a minimization step, updating the plurality of latent classes based on the updated set of posteriors; and

storing the optimized clustering.

2. The method according to claim 1, wherein said computed distance comprises a Bregman distance.

3. The method according to claim 1, wherein the homogeneous and heterogeneous relationships between the members of the set of objects do not comply with an independent and identically distributed (IID) statistical presumption.

4. The method according to claim 1, wherein the posteriors are computed using a Gibbs sampler.

5. The method according to claim 1, wherein a clustering of at least one object is constrained by a clustering of at least one other object.

6. The method according to claim 1, wherein at least one object has at least one of the respective object attributes, homogeneous relationships, and heterogeneous relationships which are labelled, and at least one object has respective object attributes, homogeneous relationships, and heterogeneous relationships which are unlabeled, to provide a semi-supervised clustering.

7. An system for clustering a set of objects having object types, object attributes, homogeneous relationships between objects of the same object type, and heterogeneous relationships between objects having different object types, the system comprising:

a programmable processor configured to;

iteratively optimize a clustering of the set of objects within a plurality of latent classes, dependent on object types, object attributes, homogeneous relationships, and heterogeneous relationships, by performing,

in an expectation step, wherein the programmable processor is configured to;

update a set of posteriors to maximize a probability that an object is associated with a respective latent class, comprising, for each object, a substep to individually fix an assigned cluster for all other objects, and

maximize an objective function for the respective object, comprising a substep to minimize a computational distance between an observation of the object attributes, homogeneous relationships, and heterogeneous relationships of a respective object and parameters of a corresponding expectation that the object is associated with the respective latent class, and

repeat until no object changes in assigned cluster between successive repetition, and

in a minimization step, updating the plurality of latent classes based on the updated set of posteriors; and

store the optimized clustering in a memory; and

a communications port configured to communicate at least one of an object and clustering-related information.

8. The system according to claim 7, wherein the computational distance comprises a Bregman distance.

9. The system according to claim 7, wherein the homogeneous relationships and heterogeneous relationships between the members of the set of objects do not comply with an independent and identically distributed (IID) statistical presumption.

10. The system according to claim 7, wherein programmable processor is further configured to compute the posteriors a Gibbs sampler.

11. The system according to claim 7, wherein a clustering of at least one object is constrained by a clustering of at least one other object.

12. The system according to claim 7, wherein at least one object has at least one of respective object attributes, homogeneous relationships, and heterogeneous relationships which are labelled, and at least one object has at least one of respective object attributes, homogeneous relationships, and heterogeneous relationships which are unlabeled, to provide a semi-supervised clustering.

13. A method of clustering a plurality of objects, having object types, object attributes, homogeneous relationships between objects of the same object type, and heterogeneous relationships between objects having different object types which do not comply with an independent and identically distributed (IID) statistical presumption, the method comprising:

optimizing an object clustering of the plurality of objects in a plurality of latent object classes based on at least the object types, object attributes, homogeneous relationships, and heterogeneous relationships, by iteratively;

updating a set of posteriors to maximize an expectation probability that an object is associated with a respective latent object class comprising, iteratively maximizing an objective function for each respective object while an assigned latent object class for all other objects is fixed, until no object changes in assigned latent object class occurs, and maximizing an objective function for the respective object, comprising minimizing a computed distance between an observation of the object attributes, homogeneous relationships, and heterogeneous relationships of a respective object and parameters of the corresponding expectation probability, and repeating until no object changes in assigned latent object class occurs, and

updating the plurality of latent object classes based on the updated set of posteriors; and

at least one of;

communicating a latent object class associated with an object, communicating a set of objects within a latent object class, and responding to a query based on the optimized object clustering.

14. The method according to claim 13, wherein the posteriors are computed using a Gibbs sampler.

15. The method according to claim 13, wherein an association of an object with a latent object class is constrained by an association of at least one other object with a latent object class.

16. The method according to claim 13, wherein the object clustering is semi-supervised, and a portion of the set of object attributes, homogeneous relationships, and respective heterogeneous relationships are labelled.

17. The method according to claim 13, wherein the object clustering partitions an arbitrarily complex graph involving at least the data object attributes, the homogeneous relations and the heterogeneous relations.

18. The method according to claim 13, wherein the computed distance comprises a Bregman distance.

19. The method according to claim 13, wherein the plurality of objects comprise a set of hyperlinked objects, wherein the respective object attributes comprise an object information content and the relations between respective data objects comprise hyperlink information.

20. The method according to claim 13, wherein the object attributes, homogeneous relationships between objects of the same object type, and heterogeneous relationships between objects having different object types each have a statistical distribution independently selected from a normal distribution, a Bernoulli distribution, a multinomial distribution and an exponential distribution.