SoF: Soft-Cluster Matrix Factorization forProbabilistic Clustering
†

†‡

†

Han Zhao , Pascal Poupart , Yongfeng Zhang and Martin Lysy†‡
{han.zhao, ppoupart, mlysy}@uwaterloo.ca, zhangyf07@gmail.com†‡
University of Waterloo, Tsinghua University

Introduction

Soft-Cluster Matrix Factorization• Probabilistic clustering without making

explicit assumptions on data density
distributions.
• Axiomatic approach to define 4 properties
that the probability of co-clustered pairs ofpoints should satisfy.
• Establish a connection between probabilisticclustering and constrained symmetricNonnegative Matrix Factorization (NMF).
• Sequential minimization algorithm using
penalty method to convert the constrained
optimization problem into an unconstrained
problem and solve it using gradient descent.

Co-cluster Probability pC (v1, v2) induced by distance function L : Rd × Rd 7→ R+ should satisfy the following 4 properties:• Boundary property: ∀v1, v2 ∈ Rd, if L(v1, v2) = 0, then pC (v1, v2) = 1; if L(v1, v2) → ∞, then pC (v1, v2) → 0.
• Symmetry property: ∀v1, v2 ∈ Rd, pC (v1, v2) = pC (v2, v1).
• Monotonicity property: ∀v1, v2, v3 ∈ Rd, pC (v1, v2) ≤ pC (v1, v3) ⇔ L(v1, v2) ≥ L(v1, v3).
∂pC (v1,v2)∂pC (v1,v3)
d• Tail property: ∀v1, v2, v3 ∈ R , ∂L(v ,v ) ≤ ∂L(v ,v ) ⇔ L(v1, v2) ≥ L(v1, v3).
1 2
1 3−cL(v1,v2)

Given a distance function L, there exists a family of co-cluster probability functions pC (v1, v2) = e
which satisfy
the boundary, symmetry, monotonicity and tail properties simultaneously for any constant c > 0.
Empirical co-cluster probability: Pij , pC (vi, vj ) = e−L(vi,vj )KT
True co-cluster probability: Pr(vi ∼ vj ) = Σk=1 Pr(ci = k|vi) × Pr(cj = k|vj ) = pvipvj
Let Wij = Pr(ci = j|vi), learning paradigm:
T 2minimizeW ||P − W W T ||2F
minimize||P−WW||F − λ1Σij min{0, Wij }P enaltyM ethodW=========⇒
(1)
N ×K2
subject to W ∈ R+ , W 1K = 1N+λ2||W 1K − 1N ||2
Sequential minimization: For each fixed pair (λ1, λ2) solve the unconstrained problem and then increase (λ1, λ2) iteratively
until convergence.
Kernel Kmeans
Spectral Clustering
SymNMF
SoFT 2
T 2
T 2
T 2
Objective min ||K − W W ||F
min ||L − W W ||F
min ||A − W W ||F
min ||P − W W ||FProperty
K is S.P.D.
L is graph Laplacian, S.P.D. A is similarity matrix P is nonnegative, S.P.D.
TT
Constraint W W = I, W  0
W W =IW 0W  0, W 1 = 1

Experiments

Figure 1: Synthetic experiments on 6 data sets. Different colors for different clusters found by SoF.
15

15

15

0.035
100.0350.025
0.02

0

0.8
10

0.7
0.6

5

0.4
0.3

−5
0.01

−10
−15
−15

0.005
−10

−50

5

10

15

0

−10
−15
−15

0.1
−10

−5

0

5

10

15

1.4
10

1.2
1

5

0.8

0

0.7

5

0.6
0.5

00.4
−5

0.3

0.2

15

15

0.8

0.5
00.015
−50.9
100.2

−10

0.1

0

−15
−15

1.5

15

−10

−505

10

150.910105100.80.7

50.60.500.60.4−5−50.5−50.30.4−10−15−150.2−10−505101500−100.2−100.1−15−15−10−50510150−15−15−10−50510150Figure 2: Entropy graph of probabilistic assignment. Brighter colors correspond to higher entropy
and hence the uncertainty in clustering.

PurityRand Index
Accuracy
BL BT GL IRIS ECO IMG DIG BL BT GL IRIS ECO IMG DIG BL BT GL IRIS ECO IMG DIG
K-means 0.76 0.43 0.56 0.87 0.80 0.70 0.71 0.60 0.71 0.69 0.86 0.81 0.81 0.91 0.73 0.34 0.51 0.86 0.60 0.63 0.68
S-means 0.76 0.43 0.57 0.92 0.76 0.63 0.71 0.52 0.76 0.69 0.92 0.78 0.81 0.91 0.61 0.39 0.52 0.90 0.56 0.61 0.67
GMM 0.77 0.46 0.52 0.89 0.81 0.74 0.70 0.57 0.76 0.64 0.88 0.85 0.83 0.91 0.66 0.43 0.46 0.86 0.68 0.69 0.67
SP-NC 0.78 0.42 0.38 0.86 0.81 0.30 0.11 0.64 0.74 0.43 0.85 0.81 0.32 0.11 0.73 0.41 0.37 0.85 0.61 0.28 0.11
SP-NJW 0.76 0.40 0.38 0.59 0.80 0.48 0.13 0.51 0.71 0.53 0.60 0.80 0.74 0.41 0.56 0.42 0.33 0.56 0.58 0.37 0.12
NMF 0.76 0.43 0.58 0.79 0.73 0.57 0.47 0.56 0.65 0.71 0.81 0.81 0.80 0.86 0.68 0.39 0.50 0.79 0.66 0.53 0.44
RNMF 0.76 0.28 0.52 0.84 0.70 0.56 0.45 0.59 0.38 0.65 0.85 0.78 0.79 0.86 0.71 0.27 0.51 0.84 0.59 0.52 0.41
GNMF 0.76 0.44 0.55 0.85 0.77 0.71 0.71 0.60 0.68 0.70 0.85 0.80 0.77 0.91 0.72 0.36 0.44 0.81 0.56 0.54 0.67
SymNMF 0.76 0.47 0.60 0.88 0.81 0.77 0.76 0.62 0.77 0.70 0.88 0.83 0.83 0.91 0.76 0.42 0.46 0.87 0.66 0.68 0.67
SoF
0.76 0.51 0.64 0.95 0.85 0.75 0.82 0.64 0.79 0.73 0.93 0.85 0.86 0.94 0.76 0.48 0.47 0.94 0.74 0.71 0.82
abaAlgorithm which achieves best score is highlighted using bold font.
b
Algorithm which achieves best score and is significantly better than other algorithms under Wilcoxon signed-rank test is highlighted in bold and blue color.

Data sets # Objects # Attributes # Classes
BL748
42BT
106
96GL
214
96IRIS
150
43ECO
336
78IMG
4435
366DIG
10992
1610Analysis• P nonnegative and S.P.D., an approximation

to completely positive matrix.
• The optimization problem is constrained
version of completely positive matrix
factorization.
• Optimal solution not unique, label switching.

Conclusion• A novel probabilistic clustering algorithm

derived from a set of properties
characterizing the co-cluster probability interms of pairwise distances.
• A relaxation of C.P. programming, revealinga close relationship between probabilisticclustering and symmetric NMF-basedalgorithms.
• A sequential minimization framework to finda local minimum solution.

References[1] Dhillon, I. S.; Guan, Y.; and Kulis, B. Kernel k-means: spectral clusteringand normalized cuts. In Proceedings of the tenth ACM SIGKDD
international conference on Knowl- edge discovery and data mining.
[2] Dickinson, P. J., and Gijben, L. On the computational complexity ofmembership problems for the completely positive cone and its dual.
Computational Optimization and Applications.