High-dimensional data clustering with the use of hybrid similarity matrices

• US 7,003,509 B2
• Filed: 07/21/2003
• Issued: 02/21/2006
• Est. Priority Date: 07/21/2003
• Status: Active Grant

• Current Assignee: Aido LLC (Endpoint IP LLC)
• Original Assignee: Leonid Andreev
• Inventors: Andreev, Leonid
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US10/622,542
• Publication Number:
  US 20050021528A1
• Time in Patent Office: 946 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-205, 716/1, 716/18, 715/721, 380/211, 725/116
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

This invention provides a method, apparatus and algorithm for compact description of objects in high-dimensional space of attributes for the purpose of cluster analysis by method of evolutionary transformation of similarity matrices. The proposed method comprises computation of monomeric similarity matrices based on each of parameters that describe a set of objects and the following hybridization of monomeric matrices into a hybrid similarity matrix, which allows for comparison of different attributes on a dimensionless basis. Individual monomeric matrices may be added to a hybrid matrix in any proportion, thus allowing for evaluation of significance of individual parameters. Two types of metrics are proposed for computation of monomeric matrices, depending on quantitative and qualitative nature of attributes used for description of objects under analysis.

Claims

1. A computer-based method for computation of similarity matrices of objects in a high-dimensional space of attributes with the purpose of clustering, allowing for fusion of different attributes (parameters) on a dimensionless basis, comprising the steps of:

a) computation of similarity matrices for each of attributes (parameters) individually, such matrices being monomer similarity matrices;

and

b) hybridization of all monomer similarity matrices into one hybrid matrix which is further used in clustering process.

2. The method of claim 1 wherein said hybridization of monomer similarity matrices is performed so that all similarity coefficients in monomer similarity matrices for one and the same pair of objects are averaged through computation of their geometric (arithmetic) means.

3. The method of claim 1 wherein each of monomer similarity matrices used in computation of a hybrid matrix is computed with the use of a metric that most optimally suits a respective attribute (parameter).

4. The method of claim 3 wherein a choice of metrics used in computation of monomer similarity matrices for further hybridization into a hybrid matrix depends on whether a respective attribute (parameter) describes a shape or power of an object.

5. The method of claim 4 wherein attributes (parameters) should be treated either as those describing a shape or as those describing a power, depending on a problem to be solved by clustering analysis.

6. The method of claim 4 wherein monomer similarity matrices based on attributes (parameters) describing shapes of objects are computed with the use of a metric representing a ratio of a lesser value to a greater value of exponential functions in which a base is a constant >

1 and an exponent is a value of a respective parameter.

7. The method of claim 4 wherein monomer matrices based on attributes (parameters) describing power of objects are computed with the use of a metric representing a ratio of a lower value of a parameter to a higher value of the same parameter.

8. The method of claim 1 wherein each and any of said monomer matrices may be multiplied and added to a hybrid matrix in an indefinite number of extra copies.