System and method for probabilistic relational clustering
View Patent ↗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.
1. A method of relational analysis of data, comprising:
receiving a data set {{F (j) } j=1 m , {S (j) } j=1 m , {R (ij) } i,j=1 m } having a plurality of types of data objects which are interrelated to each other, the data objects having attributes of respective data objects {Θ (j) } j=1 m , homogeneous relations {Γ (j) } j=1 m between objects of the same type, and heterogeneous relations {γ (ij) } i,j=1 m between objects of different types, each type of object having latent classes;
formulating a relational mixed membership model {Λ (j) } j=1 m representing data objects and respective relationships of data objects based on latent classifications, the model comprising an expectation having a latent indicator {C (j) } j=1 m for each respective object generated based on a multinomial distribution, with the class memberships of the respective data objects as parameters;
automatically initializing the parameters of a likelihood function
{tilde over (Ω)}={{{tilde over (Λ)} (j) } j=1 m ,{{tilde over (Θ)} (j) } j=1 m ,{{tilde over (Γ)} (j) } j=1 m ,{{tilde over (γ)} (ij) } i,j=1 m ,
and computing the posterior
Pr ({ C (j) }|F (j) } j=1 m ,{S (j) } j=1 m ,{R (ij) } i,j=1 m ,{tilde over (Ω)})
using the Gibbs sampler, and
maximizing the likelihood function by iteratively updating {tilde over (Ω)}=Ω over the range of i and j, until convergence is achieved, where the update is computed by at least one of:
Method I
Λ
hp
(
1
)
=
Pr
(
C
hp
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
,
Θ
·
g
=
∑
p
=
1
n
1
F
·
p
Pr
(
C
gp
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
∑
p
=
1
n
1
Pr
(
C
gp
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
Γ
gh
=
∑
p
,
q
=
1
n
1
S
pq
Pr
(
C
gp
(
1
)
=
1
,
C
hq
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
∑
p
,
q
=
1
n
1
Pr
(
C
gp
(
1
)
=
1
,
C
hq
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
,
and
Method II
update {C (j) } j=1 m , to maximize the objective function
log
⌊
(
Ω
❘
Ψ
)
=
∑
p
=
1
n
1
∑
g
=
1
k
1
C
gp
(
1
)
log
Λ
gp
(
1
)
+
∑
q
=
1
n
2
∑
h
=
1
k
2
C
hq
(
2
)
log
Λ
gp
(
2
)
-
D
ϕ
1
(
F
,
Θ
C
(
1
)
)
-
D
ϕ
2
(
S
,
(
C
(
1
)
)
T
Γ
C
(
1
)
)
-
D
ϕ
3
(
R
,
C
(
1
)
)
T
Υ
C
(
2
)
+
τ
,
wherein
Θ
·
g
(
j
)
=
∑
p
:
C
gp
(
j
)
=
1
F
·
p
(
j
)
∑
p
=
1
n
j
C
gp
(
j
)
,
Γ
gh
(
j
)
=
∑
p
:
C
gp
(
i
)
=
1
,
q
:
C
hq
(
j
)
=
1
S
pq
(
j
)
∑
p
=
1
n
j
C
gp
(
j
)
∑
q
=
1
n
j
C
hq
(
j
)
,
and
Υ
gh
(
ij
)
=
∑
p
:
C
gp
(
i
)
=
1
,
q
:
C
hq
(
j
)
=
1
R
pq
(
ij
)
∑
p
=
1
n
i
C
gp
(
i
)
∑
q
=
1
n
j
C
hq
(
j
)
,
to estimate unknown parameters of a joint probability distribution equation over the observations and latent indicators; and
storing in a memory at least the maximized expectations associated with the model.
2. The method according to claim 1 , further comprising using at least the maximized expectations associated with the model to partition a graph.
3. The method according to claim 1 , further comprising using at least the maximized expectations associated with the model to determine a clustering of data objects.
4. The method according to claim 1 , further comprising clustering the data objects on relational data of one heterogeneous relation matrix.
5. A system for relational clustering of data, comprising:
an input adapted to receive a data set {{F (j) } j=1 m , {S (j) } j=1 m , {R (ij) } i,j=1 m }, having a plurality of types of data objects which are interrelated to each other, the data objects having attributes {Θ (j) } j=1 m of respective data objects, homogeneous relations {Γ (j) } j=1 m between objects of the same type, and heterogeneous relations {γ (ij) } i,j=1 m between objects of different types, each type of object having latent classes;
an automated processor, having associated memory, configured to:
formulate a relational mixed membership model {Λ (j) } j=1 m representing data objects and respective relationships of data objects based on latent classifications, the model comprising an expectation having a latent indicator for each respective object generated based on a multinomial distribution, with the class memberships of the respective data objects as parameters;
initializing the parameters of a likelihood function
{tilde over (Ω)}={{{tilde over (Λ)} (j) } j=1 m ,{{tilde over (Θ)} (j) } j=1 m ,{{tilde over (Γ)} (j) } j=1 m ,{{tilde over (γ)} (ij) } i,j=1 m ,
and computing the posterior
Pr ({ C (j) }|F (j) } j=1 m ,{S (j) } j=1 m ,{R (ij) } i,j=1 m ,{tilde over (Ω)})
using the Gibbs sampler, and
maximize a likelihood function by iteratively updating {tilde over (Ω)}=Ω over the range of i and j, until convergence is achieved, where the update is computed by at least one of:
Method I
Λ
hp
(
1
)
=
Pr
(
C
hp
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
,
Θ
·
g
=
∑
p
=
1
n
1
F
·
p
Pr
(
C
gp
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
∑
p
=
1
n
1
Pr
(
C
gp
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
Γ
gh
=
∑
p
,
q
=
1
n
1
S
pq
Pr
(
C
gp
(
1
)
=
1
,
C
hq
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
∑
p
,
q
=
1
n
1
Pr
(
C
gp
(
1
)
=
1
,
C
hq
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
,
and
Method II
update {C (j) } j=1 m , to maximize the objective function
log
⌊
(
Ω
❘
Ψ
)
=
∑
p
=
1
n
1
∑
g
=
1
k
1
C
gp
(
1
)
log
Λ
gp
(
1
)
+
∑
q
=
1
n
2
∑
h
=
1
k
2
C
hq
(
2
)
log
Λ
gp
(
2
)
-
D
ϕ
1
(
F
,
Θ
C
(
1
)
)
-
D
ϕ
2
(
S
,
(
C
(
1
)
)
T
Γ
C
(
1
)
)
-
D
ϕ
3
(
R
,
C
(
1
)
)
T
Υ
C
(
2
)
+
τ
,
wherein
Θ
·
g
(
j
)
=
∑
p
:
C
gp
(
j
)
=
1
F
·
p
(
j
)
∑
p
=
1
n
j
C
gp
(
j
)
,
Γ
gh
(
j
)
=
∑
p
:
C
gp
(
i
)
=
1
,
q
:
C
hq
(
j
)
=
1
S
pq
(
j
)
∑
p
=
1
n
j
C
gp
(
j
)
∑
q
=
1
n
j
C
hq
(
j
)
,
and
Υ
gh
(
ij
)
=
∑
p
:
C
gp
(
i
)
=
1
,
q
:
C
hq
(
j
)
=
1
R
pq
(
ij
)
∑
p
=
1
n
i
C
gp
(
i
)
∑
q
=
1
n
j
C
hq
(
j
)
,
to estimate unknown parameters of a joint probability distribution equation over the observations and latent indicators; and
an output adapted to transfer at least the maximized expectations associated with the model.
6. The system according to claim 5 , wherein the automated processor uses at least the maximized expectations associated with the model to partition a graph.
7. The method according to claim 5 , wherein the automated processor uses at least the maximized expectations associated with the model to determine a clustering of data objects.
8. The method according to claim 5 , wherein the automated processor determines a clustering the data objects on relational data of one type of heterogeneous relation.
9. A method for relational analysis of data, comprising:
(a) receiving an input data set is represented as a set of exponential family distributions {{F (j) } j=1 m , {S (j) } j=1 m , {R (ij) } i,j=1 m };
(b) storing an initial estimate of a set of matrices {tilde over (Ω)}, comprising:
membership matrices {Λ (j) } j=1 m ,
attribute expectation matrices {Θ (j) } j=1 m for attribute matrices F (j) ,
homogeneous relation expectation matrices {Γ (j) } j=1 m for homogeneous relation matrices S (j) , and
heterogeneous relation expectation matrices {γ (ij) } i,j=1 m , for heterogeneous relation matrices R (ij) ;
(c) with an automated processor, iteratively computing, for each respective value of i and j, a posterior function , wherein Pr({C (j) }|F (j) } j=1 m ,{S (j) } j=1 m ,{R (ij) } i,j=1 m ,{tilde over (Ω)}), wherein C (j) is a cluster indicator matrix:
Λ
(
j
)
using
Λ
hp
(
1
)
=
Pr
(
C
hp
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
,
Θ
(
j
)
using
Θ
·
g
=
∑
p
=
1
n
1
F
·
p
Pr
(
C
gp
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
∑
p
=
1
n
1
Pr
(
C
gp
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
,
Γ
(
j
)
using
Γ
gh
=
∑
p
,
q
=
1
n
1
S
pq
Pr
(
C
gp
(
1
)
=
1
,
C
hq
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
∑
p
,
q
=
1
n
1
Pr
(
C
gp
(
1
)
=
1
,
C
hq
(
1
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
,
Υ
(
ij
)
using
Υ
gh
=
∑
p
=
1
n
1
∑
q
=
1
n
2
R
pq
Pr
(
C
gp
(
1
)
=
1
,
C
hq
(
2
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
∑
p
=
1
n
1
∑
q
=
1
n
2
Pr
(
C
gp
(
1
)
=
1
,
C
hq
(
2
)
=
1
❘
F
,
S
,
R
,
Ω
~
)
;
(d) comparing the stored set of matrices {tilde over (Ω)} with a resulting set of matrices Ω of an iteration of said computing to determine a convergence; and
(e) outputting a converged result Ω.
10. The method according to claim 9 , further comprising using at least the converged result Ω to partition a graph.
11. The method according to claim 9 , further comprising using at least the converged result Ω to determine a clustering of objects represented in the input data set.
12. The method according to claim 1 , further comprising clustering the input data set on relational data of one heterogeneous relation matrix R (j) .
13. A method for processing data, comprising:
storing a relational data set {{F (j) } j=1 m , {S (j) } j=1 m , {R (ij) } i,j=1 m }, comprising a set of exponential family distributions of attribute matrices F (j) , homogeneous relation matrices S (j) , and heterogeneous relation matrices R (ij) ;
initializing a set of matrices {tilde over (Ω)}={{{tilde over (Λ)} (j) } j=1 m ,{{tilde over (Θ)} (j) } j=1 m ,{{tilde over (Γ)} (j) } j=1 m ,{{tilde over (γ)} (ij) } i,j=1 m , comprising:
membership matrices {Λ (j) } j=1 m ,
attribute expectation matrices {Θ (j) } j=1 m ,
homogeneous relation expectation matrices {Γ (j) } j=1 m , and
heterogeneous relation expectation matrices {γ (ij) } i,j=1 m ;
updating cluster indicator matrices {C (j) } j=1 m , to maximize the objective function
log
⌊
(
Ω
❘
Ψ
)
=
∑
p
=
1
n
1
∑
g
=
1
k
1
C
gp
(
1
)
log
Λ
gp
(
1
)
+
∑
q
=
1
n
2
∑
h
=
1
k
2
C
hq
(
2
)
log
Λ
gp
(
2
)
-
D
ϕ
1
(
F
,
Θ
C
(
1
)
)
-
D
ϕ
2
(
S
,
(
C
(
1
)
)
T
Γ
C
(
1
)
)
-
D
ϕ
3
(
R
,
C
(
1
)
)
T
Υ
C
(
2
)
+
τ
where
Ψ={{ C (j) } j=1 m ,{F (j) } j=1 m ,{R (ij) } i,j=1 m },
τ=log ƒ φ 1 ( F )+log ƒ φ 2 ( S )+log ƒ φ 3 ( R ),
D φ 1 is a Bregman divergence for the attributes,
D φ 2 is a Bregman divergence for the homogeneous relations,
D φ 3 is a Bregman divergence for heterogeneous relations, and
ƒ φ n represents a uniquely determined function for each respective exponential family distribution;
for each respective combination of i and j, computing with an automated processor:
Θ
(
j
)
using
Θ
·
g
(
j
)
=
∑
p
:
C
gp
(
j
)
=
1
F
·
p
(
j
)
∑
p
=
1
n
j
C
gp
(
j
)
Γ
(
j
)
using
Γ
gh
(
j
)
=
∑
p
:
C
gp
(
i
)
=
1
,
q
:
C
hq
(
j
)
=
1
S
pq
(
j
)
∑
p
=
1
n
j
C
gp
(
j
)
∑
q
=
1
n
j
C
hq
(
j
)
Υ
(
ij
)
using
Υ
gh
(
ij
)
=
∑
p
:
C
(
i
)
gp
=
1
,
q
:
C
hq
(
j
)
=
1
R
pq
(
ij
)
∑
p
=
1
n
i
C
gp
(
i
)
∑
q
=
1
n
j
C
hq
(
j
)
;
and
updating the set of matrices {tilde over (Ω)} with the computed values Ω, iterating said updating and computing until at least one convergence criterion is satisfied.
14. The method according to claim 13 , further comprising using at least the computed values Ω to partition a graph.
15. The method according to claim 9 , further comprising using at least the computed values Ω to determine a clustering of objects represented in the input data set.
16. The method according to claim 1 , further comprising clustering the relational data set on relational data of one heterogeneous relation matrix R (j) .