Clustering and classification via localized diffusion folders
View Patent ↗A method for hierarchical clustering comprises multi-level partitioning of data points into non-overlapping LDFs and formation of sets of such LDFs, wherein original data points may reside in different LDFs. The sets of LDFs are then hierarchically processed into sets of super-LDFs, which are further processed up the hierarchy. In some embodiments, the further processing ends with the construction of a single super-LDF at the root of the hierarchy. The partitioning of the data points and the hierarchical processing of the sets of LDFs and super-LDFs uses respective local affinity matrices.
1. A method of hierarchical clustering of multi-dimensional data which includes a plurality of data points, the method comprising the steps of:
a) at a lowest level in a hierarchical clustering structure, partitioning the data points into at least two sets of non-overlapping local diffusion folders (LDFs); and
b) at a higher level in the hierarchical clustering structure, processing all LDFs in the sets into at least one super-LDF, wherein each super-LDF represents a cluster.
2. The method of claim 1 , wherein the step of partitioning includes constructing an initial local affinity matrix (LAM) which is further used to construct a respective set of non-overlapping LDFs.
3. The method of claim 2 , wherein the constructing an initial LAM includes processing the plurality of data points into a Markov transition matrix.
4. The method of claim 3 , wherein the constructing a Markov transition affinity matrix includes:
i. building a matrix C of size m×n of data points, where m is the number of data points and n is the number of features in each data point,
ii. normalizing matrix C to obtain a normalized matrix A,
iii. processing normalized matrix A to construct a similarity matrix Ã,
iv. processing similarity matrix à to construct a Gaussian kernel K, and
v. normalizing the Gaussian kernel K into the Markov transition matrix.
5. The method of claim 1 , wherein the step of processing all LDFs includes:
i. using all LDFs obtained in step (a) to construct a folder LAM, and
ii. using the folder LAM to construct the at least one super-LDF.
6. The method of claim 1 , further comprising the step of:
c) checking whether the at least one super-LDF is a single super-LDF and if not, processing all super-LDFs into a single root super-LDF.
7. The method of claim 1 , wherein the constructing a respective set of non-overlapping LDFs includes:
i. randomly selecting an initial data point,
ii. building a diffusion folder around the initial data point, and
iii. repeating (i) and (ii) with different randomly selected initial data points to construct a Voronoi diagram of LDFs.
8. The method of claim 1 , wherein a data point is a record of a data network activity.
9. The method of claim 1 , wherein a data point is a vector of wine constituents.
10. The method of claim 1 , wherein a data point is a vector of plant variables.
11. The method of claim 1 , wherein a data point is an image pixel.
12. A digital computer system comprising:
a) a storage area for storing multi-dimensional data which includes a plurality of data points; and
b) a program of instructions executable by a central processing unit to perform steps of:
i. at a lowest level in a hierarchical clustering structure, partitioning the data points into at least two sets of non-overlapping local diffusion folders (LDFs) and,
ii. at a higher level in the hierarchical clustering structure, processing all LDFs in the sets into at least one super-LDF, wherein each super-LDF represents a respective cluster.
13. The method of claim 12 , wherein the step of partitioning includes constructing an initial local affinity matrix (LAM) which is further used to construct a respective set of non-overlapping LDFs.
14. The system of claim 13 , wherein the constructing an initial LAM includes processing the plurality of data points into a Markov transition matrix.
15. The system of claim 14 , wherein the constructing a Markov transition affinity matrix includes:
i. building a matrix C of size m×n of data points, where m is the number of data points and n is the number of features in each data point,
ii. normalizing matrix C to obtain a normalized matrix A,
iii. processing normalized matrix A to construct a similarity matrix Ã,
iv. processing similarity matrix à to construct a Gaussian kernel K, and
v. normalizing the Gaussian kernel K into the Markov transition matrix.
16. The system of claim 12 , wherein the step of processing all LDFs includes:
A. using all LOPS obtained in step (a) to construct to folder LAM, and
B. using the folder LAM to construct the at least one super-LDF.
17. The system of claim 12 , further comprising the step of:
iii. checking whether the at least one super-LDF is a single super-LDF and if not, processing all super-LDFs into a single root super-LDF.
18. The system of claim 13 , wherein the constructing a respective set of non-overlapping LDFs includes:
A. randomly selecting an initial data point,
B. building a diffusion folder around the initial data point, and
C. repeating (A) and (B) with different randomly selected initial data points to construct a Voronoi diagram of LDFs.
19. The system of claim 12 , wherein a data point is selected from the group consisting of a record of a data network activity, a vector of wine constituents, a vector of plant variables and an image pixel.