Clustering using non-negative matrix factorization on sparse graphs

Patent metadata

Field	Value
Publication number	US-9727532-B2
Application number	US-10949608-A
Country	US
Kind code	B2
Filing date	Apr 25, 2008
Priority date	Apr 25, 2008
Publication date	Aug 8, 2017
Grant date	Aug 8, 2017

Abstract

Object clustering techniques are disclosed. A nonnegative sparse similarity matrix is constructed for a set of objects. Nonnegative factorization of the nonnegative sparse similarity matrix is performed. Objects of the set of objects are allocated to clusters based on factor matrices generated by the nonnegative factorization of the nonnegative sparse similarity matrix.

First claim

The invention claimed is:

1. A clustering method comprising:
constructing a nonnegative sparse similarity matrix for a set of objects wherein the elements of the nonnegative sparse similarity matrix comprise similarity measures s(d i ,d j ) where {d i , d j } is a pair of objects of the set of objects and wherein the constructing includes performing a sparsification operation;
performing nonnegative factorization of the nonnegative sparse similarity matrix wherein the performing comprises:
approximating the nonnegative sparse similarity matrix by a product A×B of factor matrices A and B where the factor matrix A has R columns and the factor matrix B has R rows where R is a preselected number of clusters, and
initializing parameters of the factor matrices A and B based on the preselected number of clusters R and a set of cluster centroids wherein the initializing comprises initializing parameters of the factor matrices A and B based on distances between nodes of the nonnegative sparse similarity matrix and the cluster centroids; and

allocating objects of the set of objects to clusters based on factor matrices generated by the nonnegative factorization of the nonnegative sparse similarity matrix;
wherein the constructing, performing, and allocating are performed by a processor executing software or firmware.

2. The clustering method as set forth in claim 1 , wherein the initializing comprises:
receiving the set of cluster centroids via a graphical user interface.

3. The A clustering method as set forth in claim 1 , comprising:
constructing a nonnegative sparse similarity matrix for a set of objects wherein the elements of the nonnegative sparse similarity matrix comprise similarity measures s(d i ,d j ) where {d i , d j } is a pair of objects of the set of objects and wherein the constructing includes performing a sparsification operation;
performing nonnegative factorization of the nonnegative sparse similarity matrix wherein the performing comprises:
approximating the nonnegative sparse similarity matrix by a product A×B of factor matrices A and B where the factor matrix A has R columns and the factor matrix B has R rows where R is a preselected number of clusters, and
initializing parameters of the factor matrices A and B based on the preselected number of clusters R and a set of cluster centroids wherein the initializing comprises selecting the set of cluster centroids as local density maxima; and

allocating objects of the set of objects to clusters based on factor matrices generated by the nonnegative factorization of the nonnegative sparse similarity matrix;
wherein the constructing, performing, and allocating are performed by a processor executing software or firmware.

4. The clustering method as set forth in claim 1 , wherein the objects are images, and the constructing comprises:
extracting features from the image objects;
measuring similarity between image objects based on the features; and
constructing the nonnegative sparse similarity matrix based on the measured similarities.

5. The clustering method as set forth in claim 1 , wherein the constructing including performing a sparsification operation comprises one of:
constructing an ∈ graph defining the nonnegative sparse similarity matrix, the ∈ graph including nodes for object pairs conditional upon a similarity measure of the object pair exceeding a threshold ∈,
constructing a K-nearest neighbors (K-NN) directed graph defining the nonnegative sparse similarity matrix, the K-NN directed graph including a node for first and second objects of the set of objects conditional upon the second object being one of K nearest neighbors of the first object, and
constructing an adjacency matrix having matrix elements corresponding to object pairs, the matrix element values being nonnegative values indicative of similarity of the corresponding object pairs, and deriving a commute time matrix from the adjacency matrix.

Assignees

• Perronnin Florent
• Bouchard Guillaume
• Xerox Corp

Inventors

• Perronnin Florent
• Bouchard Guillaume

Classifications

• G06F18/2323

  based on graph theory, e.g. minimum spanning trees [MST] or graph cuts · CPC title

• G06F17/16 Primary

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• G06K9/6224

  Physics · mapped topic