US 8,285,719 B1Granted

System and method for probabilistic relational clustering

AssigneeThe Research Foundation of State University of New York

InventorsBo Long, Zhongfei (Mark) Zhang

Life of this patent

Estimating the term…

Loading patent…

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.

Claims16

Dependent claims

A method of relational analysis of data, comprising:

receiving a data set {{F(j)}j=1m, {S(j)}j=1m, {R(ij)}i,j=1m} 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=1m, homogeneous relations {Γ(j)}j=1m between objects of the same type, and heterogeneous relations {γ(ij)}i,j=1m between objects of different types, each type of object having latent classes;
formulating a relational mixed membership model {Λ(j)}j=1m 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=1m 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=1m,{{tilde over (Θ)}(j)}j=1m,{{tilde over (Γ)}(j)}j=1m,{{tilde over (γ)}(ij)}i,j=1m,
and computing the posterior
Pr({C(j)}|F(j)}j=1m,{S(j)}j=1m,{R(ij)}i,j=1m,{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=1m, 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.

484 more elements

A system for relational clustering of data, comprising:

an input adapted to receive a data set {{F(j)}j=1m, {S(j)}j=1m, {R(ij)}i,j=1m}, having a plurality of types of data objects which are interrelated to each other, the data objects having attributes {Θ(j)}j=1m of respective data objects, homogeneous relations {Γ(j)}j=1m between objects of the same type, and heterogeneous relations {γ(ij)}i,j=1m 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=1m 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=1m,{{tilde over (Θ)}(j)}j=1m,{{tilde over (Γ)}(j)}j=1m,{{tilde over (γ)}(ij)}i,j=1m,
and computing the posterior
Pr({C(j)}|F(j)}j=1m,{S(j)}j=1m,{R(ij)}i,j=1m,{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=1m, 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.

489 more elements

A method for processing data, comprising:

storing a relational data set {{F(j)}j=1m, {S(j)}j=1m, {R(ij)}i,j=1m}, 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=1m,{{tilde over (Θ)}(j)}j=1m,{{tilde over (Γ)}(j)}j=1m,{{tilde over (γ)}(ij)}i,j=1m, comprising:
membership matrices {Λ(j)}j=1m,
attribute expectation matrices {Θ(j)}j=1m,
homogeneous relation expectation matrices {Γ(j)}j=1m, and
heterogeneous relation expectation matrices {γ(ij)}i,j=1m;
updating cluster indicator matrices {C(j)}j=1m, 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=1m,{F(j)}j=1m,{R(ij)}i,j=1m},
τ=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.

336 more elements

Dependencies are inferred from the claim text.