Probabilistic Distance Clustering: Algorithm and Applications - Clustering Challenges in Biological Network - page 35

is

d 1 ( i ) p 1 ( i ) 2
q 1

N

+ d 2 ( i ) p 2 ( i ) 2
q 2

min (2.15)

i =1

s.t. p 1 ( i )+ p 2 ( i )=1 ,
p 1 ( i ) ,p 2 ( i ) ≥ 0 ,i =1 , ··· ,N ,

where p 1 ( i ) ,p 2 ( i ) are the cluster probabilities at x i and d 1 ( i ) ,d 2 ( i ) are the cor-
responding distances. The problem separates into N problems like (2.12), and its
optimal value is

N

d 1 ( i ) d 2 ( i ) /q 1 q 2
d 1 ( i ) /q 1 + d 2 ( i ) /q 2

(2.16)

i =1

the sum of the joint distance functions of all points.

2.2.4. An Extremal Principle for the Cluster Sizes

Taking the cluster sizes as variables in the extremal principle (2.15),

d 1 ( i ) p 1 ( i ) 2
q 1

N

+ d 2 ( i ) p 2 ( i ) 2
q 2

min (2.17)

i =1

s.t. q 1 + q 2 = N
q 1 ,q 2 ≥ 0

with p 1 ( i ) ,p 2 ( i ) assumed known, we have the Lagrangian

d 1 ( i ) p 1 ( i ) 2
q 1

+ λ ( q 1 + q 2 −

N

+ d 2 ( i ) p 2 ( i ) 2
q 2

L ( q 1 ,q 2 ,λ )= N ) (2.18)

i =1

Zeroing the partials ∂L/∂q k gives,

N

d k ( i ) p k ( i ) 2 ,k =1 , 2 , q k = 1

λ

(2.19)

i =1

and since q 1 + q 2 = N ,

N

d k ( i ) p k ( i ) 2 1 / 2

i =1

q k
N =

i =1 d 2 ( i ) p 2 ( i ) 2 1 / 2 ,k =1 , 2 .

(2.20)

N

i =1 d 1 ( i ) p 1 ( i ) 2 1 / 2

+ N