Neuro/fuzzy hybrid approach to clustering data

• US 6,904,420 B2
• Filed: 05/17/2001
• Issued: 06/07/2005
• Est. Priority Date: 05/17/2001
• Status: Expired due to Fees

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Kumar, Ashwin, Shetty, Ravindra K.
• Primary Examiner(s): Knight, Anthony
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US09/860,165
• Publication Number:
  US 20030046253A1
• Time in Patent Office: 1,482 Days
• Field of Search: 706/1
• US Class Current: 706/1
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06N 3/043 based on fuzzy logic, fuzzy membership or fuzzy inference, e.g. adaptive neuro-fuzzy inference systems [ANFIS]

Abstract

A technique for clustering input data includes receiving data and reading a sample of the received data having a predetermined window length. The technique further includes checking the read sample of data for uncertainty and/or robustness and determining the clustering approach to be used to cluster the received data based on the outcome of the checking.

Claims

1. A computer-implemented method for clustering input data, comprising:

receiving data;

reading a sample of the received data having a predetermined window length;

checking the read data for uncertainty and/or robustness; and

determining the clustering approach to be used to cluster the received data based on the outcome of the checking.

2. The method of claim 1, wherein input data comprises data selected from the group consisting of static data and real-time data.

3. The method of claim 2, wherein reading the sample of data further comprises:

if the received data is static data, then reading a sample of the received static data using a predetermined window length; and

if the received data is real-time data, then reading a sample of the received real-time data using a dynamically varying window of predetermined window length.

4. The method of claim 3, further comprising:

normalizing the read sample of the received data based on attributes in the read sample of data.

5. The method of claim 3, wherein checking the data for uncertainty and/or robustness comprises:

selecting multiple blocks of data from the read sample of data;

computing dispersions for each of the selected blocks;

computing a sum of variance from the computed dispersions; and

comparing variation in the computed sum of variance to a predetermined variance threshold value.

6. The method of claim 5, wherein determining the clustering approach comprises:

determining the clustering approach to be used to cluster the read data based on the outcome of the comparison.

7. The method of claim 6, wherein determining the clustering approach to be used to cluster the read data comprises:

if the variation in the computed sum of variance is less than or equal to the predetermined variance threshold value, then clustering the read sample of the data using a fuzzy logic approach for data mining applications; and

if the variation in the computed sum of variance is greater than the predetermined variance threshold value, then clustering the read sample of the data using an unsupervised learning approach for data mining applications.

8. The method of claim 7, wherein the unsupervised learning approach comprises:

an unsupervised learning approach of the input data based on unsupervised learning methods selected from the group consisting of the parametric approach involving combined classification and parameterization and the non-parametric approach involving partitioning the unclassified data into subsets using Adaptive Resonance Theory.

9. The method of claim 7, wherein clustering the data comprises:

clustering the data based on input data characteristics selected from the group consisting of linearity, non-linearity, uncertainty, and robustness.

10. The method of claim 7, wherein the data mining applications comprise:

applications selected from the group consisting of pattern recognition, pattern prediction, and supervised machine learning systems.

11. The method of claim 7, further comprising:

if the received data is real-time data, then repeating the reading of the sample of the received real-time data using a dynamically varying window of predetermined window length.

12. The method of claim 7, wherein clustering the data using the fuzzy logic approach comprises:

forming a compatibility relationship matrix including the input data using a distance function such that values obtained using the distance function is between 0 and 1

finding a transitive closure of the formed compatibility relationship matrix; and

forming a binary tree including hierarchical clusters from the found transitive closure.

13. The method of claim 7, wherein clustering the data using the unsupervised learning approach comprises:

initializing the input data using random weights

forming initial clusters using input data;

computing Euclidian distances between the data and the formed initial clusters;

determining a minimum Euclidian distance from the computed Euclidian distances;

computing a threshold value from the sampled data to set granularity of clustering;

comparing the minimum Euclidian distance with the computed threshold value;

if the determined minimum Euclidian distance is less than or equal to the computed threshold value, then assigning a current input to a cluster corresponding to the minimum Euclidian distance;

if the determined minimum Euclidian distance is greater than the computed threshold value, forming a new cluster for the current input;

updating cluster weights based on formed new clusters.

14. A computer readable medium having instructions stored thereon to cause a computer to implement a method for clustering input data, comprising:

receiving data;

reading a sample of the received data having a predetermined window length;

checking the read data for uncertainty and/or robustness; and

determining the clustering approach to be used to cluster the received data based on the outcome of the checking.

15. The computer readable medium of claim 14, wherein the input data comprises data selected from the group consisting of static data and real-time data.

16. The computer readable medium of claim 15, wherein reading the sample of the data further comprises:

if the received data is static data, then reading a sample of the received static data using a predetermined window length; and

if the received data is real-time data, then reading a sample of the received real-time data using a dynamically varying window of predetermined window length.

17. The computer readable medium of claim 16, further comprising:

normalizing the read sample of the received data based on attributes in the read sample of data.

18. The computer readable medium of claim 16, wherein checking the data for uncertainty and/or robustness comprises:

computing dispersion and sum of variance from the read sample of data; and

comparing variation in the computed sum of variance to a predetermined variance threshold value.

19. The computer readable medium of claim 18, wherein determining the clustering approach comprises:

determining the clustering approach to be used to cluster the read data based on the outcome of the comparison.

20. The computer readable medium of claim 19, wherein determining the clustering approach to be used to cluster the read data comprises:

if the variation in the computed sum of variance is less than or equal to the predetermined variance threshold value, then clustering the read sample of the data using a fuzzy logic approach for data mining applications; and

if the variation in the computed sum of variance is greater than the predetermined variance threshold value, then clustering the read sample of the data using an unsupervised learning approach for data mining applications.

21. The computer readable medium of claim 20, wherein the unsupervised learning approach comprises:

an unsupervised learning approach of the input data based on unsupervised learning methods selected from the group consisting of the parametric approach involving combined classification and parameterization and the non-parametric approach involving partitioning the unclassified data into subsets using Adaptive Resonance Theory.

22. The computer readable medium of claim 21, wherein clustering the data comprises:

clustering the data based on input data characteristics selected from the group consisting of linearity, non-linearity, uncertainty, and robustness.

23. The computer readable medium of claim 22, wherein the data mining applications comprise:

applications selected from the group consisting of pattern recognition, pattern prediction, and supervised machine learning systems.

24. The computer readable medium of claim 21, further comprising:

if the received data is real-time data, then repeating the reading of the sample of the received real-time data using a dynamically varying window of predetermined window length.

25. The computer readable medium of claim 21, wherein clustering the data using the fuzzy logic approach comprises:

forming a compatibility relationship matrix including the input data using a distance function such that values obtained using the distance function is between 0 and 1

finding a transitive closure of the formed compatibility relationship matrix; and

forming a binary tree including hierarchical clusters from the found transitive closure.

26. The computer readable medium of claim 21, wherein clustering the data using an unsupervised learning approach comprises:

initializing random weights;

forming initial clusters using the input data;

computing Euclidian distances between clusters;

determining a minimum Euclidian distance from the computed Euclidian distances;

computing a threshold value from the sampled data to set granularity of clustering;

comparing the minimum Euclidian distance with the computed threshold value;

forming new clusters based on the outcome of the comparison; and

updating cluster weights based on formed new clusters.

27. A computer-implemented system for clustering input data, comprising:

a receive module to receive data;

a reading module to read a sample of the received data having a predetermined window length; and

an analyzer to check the read data for uncertainty and/or robustness, and determine the clustering approach to be used to cluster the received data based on the outcome of the checking.

28. The system of claim 27, wherein the data comprises data selected from the group consisting of static data and real-time data.

29. The system of claim 28, wherein the reading module reading the sample of data further comprises:

if the received data is static data, then reading a sample of the received static data using a predetermined window length; and

if the received data is real-time data, then reading a sample of the received real-time data using a dynamically varying window of predetermined window length.

30. The system of claim 29, wherein the analyzer normalizes the read sample of the received data based on attributes in the read sample of data.

31. The system of claim 30, wherein the analyzer checking the data for uncertainty and/or robustness further computes dispersion and sum of variance from the read sample of data to check for uncertainty and/or robustness.

32. The system of claim 31, further comprising:

a comparator to compare variation in the computed sum of variance to a predetermined variance threshold value.

33. The system of claim 32, wherein the analyzer determines the clustering approach to be used to cluster the read data based on the outcome of the comparison from the comparator.

34. The system of claim 33, wherein the analyzer determining the clustering approach to be used to cluster the read data comprises:

clustering the read data of data using a fuzzy logic approach for data mining application, if the variation in the computed sum of variance is less than or equal to the predetermined variance threshold value; and

clustering the read sample of data using an unsupervised learning approach for data mining applications, if the variation in the computed sum of variance is greater than the predetermined variance threshold value.

35. The system of claim 34, wherein the unsupervised learning approach comprises:

an unsupervised learning approach of the input data based on unsupervised learning methods selected from the group consisting of the parametric approach involving combined classification and parameterization and the non-parametric approach involving partitioning the unclassified data into subsets using Adaptive Resonance Theory.

36. The system of claim 34, wherein clustering the data comprises:

clustering the data based on input data characteristics selected from the group consisting of linearity, non-linearity, uncertainty, and robustness.

37. The system of claim 34, wherein the data mining applications comprise:

data mining applications selected from the group consisting of pattern recognition, pattern prediction, and supervised machine learning systems.

38. The system of claim 34, wherein the analyzer repeats the reading of the sample of the received data using a dynamically varying window of predetermined window length when the received data is real-time data.

39. The system of claim 34, wherein the analyzer clusters the read sample of data using a fuzzy logic approach by forming a compatibility relationship matrix including the input data using a distance function such that values obtained using the distance function is between 0 and 1,

wherein the analyzer finds a transitive closure of the formed compatibility relations matrix, and

wherein the analyzer further forms a binary tree including hierarchical clusters from the found transitive closure, builds clusters based on the formed binary tree.

40. The method of claim 34, wherein the analyzer clusters the read sample of data using an unsupervised learning approach by initializing the read data using random weights, forming clusters using the initialized data, and computing Euclidian distances between the formed clusters and the data,

wherein the analyzer determines a minimum Euclidian distance from the computed Euclidian distances, wherein the analyzer computes a threshold value from the sampled data to set granularity of clustering,

wherein the comparator compares the determined minimum Euclidian distance with the computed threshold value, and forms new clusters based on the outcome of the comparison, and updates cluster weights based on formed new clusters, and

wherein the analyzer re-arranges data based on cluster index.