Clustering and Non-negative Matrix
Factorization
Presented by Mohammad Sajjad Ghaemi
DAMAS LAB,
Computer Science and Software Engineering Department,
Laval University

12 April 2013

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

1/36

Outline

I What is clustering ?

I NMF overview

I Cost functions and multiplicative algorithms

I A geometric interpretation of NMF

I r-separable NMF

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

2/36

What is clustering ?

According to the label information we have 3 categories of learning
I Supervised learning

Learning from labeled data.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

3/36

What is clustering ?

According to the label information we have 3 categories of learning
I Supervised learning

Learning from labeled data.
I Semi-supervised learning

Learning from both labeled and unlabeled data.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

3/36

What is clustering ?

According to the label information we have 3 categories of learning
I Supervised learning

Learning from labeled data.
I Semi-supervised learning

Learning from both labeled and unlabeled data.
I Unsupervised learning

Learning from unlabeled data.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

3/36

Label information

Taken from [Jain,2010][Jain,2010] Jain, A.K., 2010. Data clustering : 50 years beyond
k-means. Pattern Recognition Letters 31, 651666.
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

4/36

Semi-supervised learning and manifold assumption

Taken from [Jain,2010]
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

5/36

Unsupervised learning or clustering

Taken from [Jain,2010]
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

6/36

What is clustering ?
I Clustering is grouping similar objects together.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

7/36

What is clustering ?
I Clustering is grouping similar objects together.
I Clusterings are usually not ”right” or ”wrong”, different

clusterings/clustering criteria can reveal different things about
the data.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

7/36

What is clustering ?
I Clustering is grouping similar objects together.
I Clusterings are usually not ”right” or ”wrong”, different

clusterings/clustering criteria can reveal different things about
the data.
I There is no objectively ”correct” clustering algorithm, but”clustering is in the eye of the beholder”.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

7/36

What is clustering ?
I Clustering is grouping similar objects together.
I Clusterings are usually not ”right” or ”wrong”, different

clusterings/clustering criteria can reveal different things about
the data.
I There is no objectively ”correct” clustering algorithm, but”clustering is in the eye of the beholder”.
I Clustering algorithms :I

Employ some notion of distance between objects.

I

Have an explicit or implicit criterion defining what a goodcluster is.

I

Heuristically optimize that criterion to determine theclustering.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

7/36

Comparing various clustering algorithms

Taken from [Jain,2010]
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

8/36

Outline

I What is clustering ?

I NMF overview

I Cost functions and multiplicative algorithms

I A geometric interpretation of NMF

I r-separable NMF

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

9/36

Matrix factorization
I NMF (Non-negative Matrix Factorization)

Question :Given a non-negative matrix V , find non-negative matrix
factors W and H,
V ≈ WH

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

10/36

Matrix factorization
I NMF (Non-negative Matrix Factorization)

Question :Given a non-negative matrix V , find non-negative matrix
factors W and H,
V ≈ WH
Answer :Non-negative Matrix Factorization (NMF)
Advantage of non-negativity Interpretability
I NMF is NP-hardPresented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

10/36

Matrix factorization

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

11/36

Matrix factorization
I Generally, factorization of matrices is not uniqueI

Principal Component Analysis

I

Singular Value Decomposition

I

Nyström Method

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

12/36

Matrix factorization
I Generally, factorization of matrices is not uniqueI

Principal Component Analysis

I

Singular Value Decomposition

I

Nyström Method

I Non-negative Matrix Factorization differs from the above

methods.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

12/36

Matrix factorization
I Generally, factorization of matrices is not uniqueI

Principal Component Analysis

I

Singular Value Decomposition

I

Nyström Method

I Non-negative Matrix Factorization differs from the above

methods.
I NMF enforces the constraint that the factors must be

non-negative.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

12/36

Matrix factorization
I Generally, factorization of matrices is not uniqueI

Principal Component Analysis

I

Singular Value Decomposition

I

Nyström Method

I Non-negative Matrix Factorization differs from the above

methods.
I NMF enforces the constraint that the factors must be

non-negative.
I All elements must be equal to or greater than zero.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

12/36

Matrix factorization

I Is there any unique solution to the NMF problem ?

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

13/36

Matrix factorization

I Is there any unique solution to the NMF problem ?

I

V ≈ WD −1 DH
I NMF has the drawback of being highly ill-posed.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

13/36

NMF is interesting because it does data clustering
Data Clustering = Matrix Factorizations

Many unsupervised learning methods are closely related in a simple
way (Ding, He, Simon, SDM 2005).

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

14/36

Numerical example

taken from Katsuhiko Ishiguro, et al. Extracting Essential Structurefrom Data.
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

15/36

Heat map of NMF on the gene expression data

The left is the gene expression data where each column
corresponds to a sample, the middle is the basis matrix, and theright is the coefficient matrix.
taken from Yifeng Li, et al. The Non-Negative Matrix
Factorization Toolbox for Biological Data Mining
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

16/36

Heat map of NMF clustering on a yeast metabolic

The left is the gene expression data where each column
corresponds to a gene, the middle is the basis matrix, and the rightis the coefficient matrix.
taken from Yifeng Li, et al. The Non-Negative Matrix
Factorization Toolbox for Biological Data Mining
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

17/36

Outline

I What is clustering ?

I NMF overview

I Cost functions and multiplicative algorithms

I A geometric interpretation of NMF

I r-separable NMF

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

18/36

How to solve it
Two conventional and convergent algorithms
I Square of the Euclidean distance||A − B||2 =X(Aij − Bij )2

ij

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

19/36

How to solve it
Two conventional and convergent algorithms
I Square of the Euclidean distance||A − B||2 =X(Aij − Bij )2

ij

I Generalized Kullback-Leibler divergence

D(A||B) =X
Aij(Aij log− Aij + Bij )Bij
ij

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

19/36

How to minimize it
I Minimize ||V − WH||2 or D(V ||WH)

I Convex in W only or H only (not convex in both variables)

I Goal-finding local minima (tough to get global minima)
I Gradient descent ?
I

Slow convergenceI

Sensitive to the step sizeI

inconvenient for large data

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

20/36

Cost functions and gradient based algorithm for square
Euclidean distanceI Minimize ||V − WH||2
I W new = Wik − µik 5W
ikwhere 5W is the gradient of the approximation objectivefunction with respect to W .
I Without loss of generality, we can assume that 5W consistsof 5+ and 5− , positive and unsigned negative terms,

respectively. That is,
5W = 5+ − 5−
I According to the steepest gradient descent method−
Wiknew = Wik − µik (5+ik − 5ik ) can minimize the NMF

objectives.
I By assuming that each matrix element has its own learningik
rate µik = W
we have,
5+
ik
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMAS−Clustering and Non-negative Matrix Factorization

21/36

Multiplicative vs. Additive rules
By taking the gradient of the cost function with respect to W wehave,
5W = WHH T − VH T
Wiknew = Wik − µik ((WHH T )ik − (VH T )ik )
Wik
µik =
(WHH T )ik(VH T )ik
Wiknew = Wik(WHH T )ik
Similar for H,
Hiknew = Hik

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMAS(W T V )ik(W T WH)ik

Clustering and Non-negative Matrix Factorization

(1)

22/36

Cost functions and gradient based algorithm for square
Euclidean distance
I The provided justification for multiplicative update rule does

not have any theoretical guarantee that the resulting updates
will monotonically decrease the objective function !
I Currently, the auxiliary function technique is the most widely

accepted approach for monotonicity proof of multiplicative
updates.
I Given an objective function J (W ) to be minimized,
G(W , W t ) is called an auxiliary function if it is a tight upperbound of J (W ), that is,I
I

G(W , W t ) ≥ J (W )G(W , W ) = J (W )for any W and W t .
I Then iteratively applying the rule
W new = arg minW t G (W t , W ), results in a monotonicallydecrease of J (W ).
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

23/36

Auxiliary function

Paraboloid function J (W ) and its corresponding auxiliary function
G(W , W t ), where G(W , W t ) ≥ J (W ) and G(W t , W t ) = J (W t )taken from Zhaoshui He, et al. IEEE TRANSACTIONS ON
NEURAL NETWORKS 2011
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

24/36

Auxiliary function

Using an auxiliary function G(W , W t ) to minimize an objectivefunction J (W ). The auxiliary function is constructed around thecurrent estimate of the minimizer ; the next estimate is found by
minimizing the auxiliary function, which provides an upper boundon the objective function. The procedure is iterated until it
converges to a stationary point (generally, a local minimum) of theobjective function.
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

25/36

Updates for H of Euclidean distance
If K (ht ) is the diagonal matrix
Kii (ht ) =(W t Wht )i
hit

then
1
G (h, ht ) = J(ht ) + (h − ht )T 5 J(ht ) + (h − ht )T K (ht )(h − ht )2
is an auxiliary function for
J(h) =

X
1X(vi −Wik hi )2
i

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASkClustering and Non-negative Matrix Factorization

26/36

Proof
I The update rule can be obtained by taking the derivative of
the G (h, ht ) w.r.t h and then set it to zero,

5J(ht ) + (h − ht )K (ht ) = 0
h = ht − K (ht )−1 5 J(ht )I Since J(ht ) is non-increasing under this auxiliary function, by

writing the components of this equation explicitly, we obtain,
hit+1 = hit(W t V )i(W t Wht )i

I Can be shown similarly for W of Euclidean distance.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

27/36

Outline

I What is clustering ?

I NMF overview

I Cost functions and multiplicative algorithms

I A geometric interpretation of NMF

I r-separable NMF

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

28/36

A geometric interpretation of NMF
I Given M and its NMF M ≈ UV one can scale M and U suchthat they become column stochastic implying that V iscolumn stochastic :M ≈ UV ⇐⇒ M 0 = MDm = (UDu )(Du−1 VDm ) = U 0 V 0M(:, j) =kX

U(:, i)V (i, j)

i=1Presented by Mohammad Sajjad Ghaemi, Laboratory DAMAS

with

k
X

V (i, j) = 1

i=1

Clustering and Non-negative Matrix Factorization

29/36

A geometric interpretation of NMF
I Given M and its NMF M ≈ UV one can scale M and U suchthat they become column stochastic implying that V iscolumn stochastic :M ≈ UV ⇐⇒ M 0 = MDm = (UDu )(Du−1 VDm ) = U 0 V 0M(:, j) =kX

U(:, i)V (i, j)

i=1

with

k
X

V (i, j) = 1

i=1

I Therefore, the columns of M are convex combination of thecolumns of U.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

29/36

A geometric interpretation of NMF
I Given M and its NMF M ≈ UV one can scale M and U suchthat they become column stochastic implying that V iscolumn stochastic :M ≈ UV ⇐⇒ M 0 = MDm = (UDu )(Du−1 VDm ) = U 0 V 0M(:, j) =kX

U(:, i)V (i, j)

i=1

with

k
X

V (i, j) = 1

i=1

I Therefore, the columns of M are convex combination of thecolumns of U.
I In other terms, conv (M) ⊂ conv (U) ⊂ ∆m where ∆m is theunit simplex.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

29/36

A geometric interpretation of NMF
I Given M and its NMF M ≈ UV one can scale M and U suchthat they become column stochastic implying that V iscolumn stochastic :M ≈ UV ⇐⇒ M 0 = MDm = (UDu )(Du−1 VDm ) = U 0 V 0M(:, j) =kX

U(:, i)V (i, j)

i=1

with

k
X

V (i, j) = 1

i=1

I Therefore, the columns of M are convex combination of thecolumns of U.
I In other terms, conv (M) ⊂ conv (U) ⊂ ∆m where ∆m is theunit simplex.
I Solving exact NMF is equivalent to finding a poltyope
conv (U) between conv (M) and ∆m with minimum number ofvertices.
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

29/36

A geometric interpretation of NMF

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

30/36

Outline

I What is clustering ?

I NMF overview

I Cost functions and multiplicative algorithms

I A geometric interpretation of NMF

I r-separable NMF

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

31/36

Separability Assumption
I If matrix V satisfies separability condition, it is possible tocompute optimal solutions in polynomial time.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

32/36

Separability Assumption
I If matrix V satisfies separability condition, it is possible tocompute optimal solutions in polynomial time.

I r-separable NMF

There exists an NMF (W , H) of rank r with V = WH where
each column of W is equal to a column of V .

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

32/36

Separability Assumption
I If matrix V satisfies separability condition, it is possible tocompute optimal solutions in polynomial time.

I r-separable NMF

There exists an NMF (W , H) of rank r with V = WH where
each column of W is equal to a column of V .

I V is r-separable⇐⇒ V ≈ WH = W [Ir , H 0 ]Π = [W , WH 0 ]ΠFor some H 0 ≥ 0 with columns sum to one, some permutation
matrix Π, and Ir is the r-by-r identity matrix.
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

32/36

A geometric interpretation of separability

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

33/36

Separability Assumption
I Under separability, NMF reduces to the following problem :Given a set of points (the normalized columns of V ), identify
the vertices of its convex hull.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

34/36

Separability Assumption
I Under separability, NMF reduces to the following problem :Given a set of points (the normalized columns of V ), identify
the vertices of its convex hull.
I We are still very far from knowing the best ways to computethe convex hull for general dimensions, despite the variety
methods proposed for convex hull problem.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

34/36

Separability Assumption
I Under separability, NMF reduces to the following problem :Given a set of points (the normalized columns of V ), identify
the vertices of its convex hull.
I We are still very far from knowing the best ways to computethe convex hull for general dimensions, despite the variety
methods proposed for convex hull problem.
I However, we want to design algorithms which are
I

Fast : they should be able to deal with large-scale real-world
problems where n is 106 – 109 .

I

Robust : if noise is added to the separable matrix, they shouldbe able to identifying the right set of columns.

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

34/36

Separability Assumption
I For a separable matrix V , we have,V≈ WH= W [Ir , H 0 ]Π= [W , WH 0 ]Π
0= [W , WH ]Ir

H00(n−r )×r0(n−r )×(n−r )


Π

= VX
where Π is a permutation matrix, the columns of H 0 ≥ 0 sum
to one.
I Therefore for r-separable NMF, we need to solve the following

optimization problem according to some constraints,||V (:, i) − VX (:, i)||2 ≤  for all i.
Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

35/36

Question

Question ?

Presented by Mohammad Sajjad Ghaemi, Laboratory DAMASClustering and Non-negative Matrix Factorization

36/36