Method and device for clustering categorical data and identifying anomalies, outliers, and exemplars

1 . A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform operations for assigning categorical data to a plurality of clusters, the operations comprising:

identifying a plurality of categories associated with the data;

for each category in the plurality of categories, identifying at least one element associated with the category;

specifying a number of clusters to which the data may be assigned;

assigning at least some of the data, wherein each assigned datum is assigned to a respective one of the clusters; and

for at least one of the clusters, determining, for at least one category, the frequency in data assigned to the cluster of at least one element associated with the category.

2 . The signal-bearing medium of claim 1 , wherein the operation of, for at least one of the clusters, determining, for at least one category, the frequency in data assigned to the cluster of at least one element associated with the category, comprises ascertaining a first count, for each of a plurality of the categories, for at least one element associated with the category, of instances of the element in the data assigned to the cluster.

3 . The signal-bearing medium of claim 2 , wherein the plurality of the categories includes each category, and wherein the at least one element associated with the category includes each element associated with the category.

4 . The signal-bearing medium of claim 2 , wherein the operations further comprise, for each of a plurality of the categories, for at least one element associated with the category, ascertaining a first tally of instances of the element in the data.

5 . The signal-bearing medium of claim 4 , wherein the plurality of the categories includes each category, and wherein the at least one element associated with the category includes each element associated with the category.

6 . The signal-bearing medium of claim 5 , wherein the first count and the first tally are ascertained using only a portion of the data, wherein the portion of the data used is selected based on the number of instances of elements in respective categories.

7 . The signal-bearing medium of claim 5 , wherein a portion of the data is excluded when ascertaining the first count and the first tally, wherein the portion of the data that is excluded is selected based on the number of instances of elements in respective categories.

8 . The signal-bearing medium of claim 4 , wherein the operations further comprise, for at least one cluster, computing a first fraction for at least one element, wherein the first fraction is the first count for the element in the cluster divided by the first tally for the element.

9 . The signal-bearing medium of claim 8 , wherein the operations further comprise, for at least one element, computing a measure of the difference between the first fraction for the element corresponding with a first cluster and the first fraction for the element corresponding with a second cluster.

10 . The signal-bearing medium of claim 9 , wherein the operations of computing a first fraction and a measure of the difference are performed for each of a plurality of the categories, for each element associated with the respective category.

11 . The signal-bearing medium of claim 9 , wherein the measure of the difference is a squared difference between the first fraction for the element corresponding with the first cluster and the first fraction for the element corresponding with the second cluster.

12 . The signal-bearing medium of claim 9 , wherein the measure of the difference is a weighted squared difference between the first fraction for the element corresponding with the first cluster and the first fraction for the element corresponding with the second cluster.

13 . The signal-bearing medium of claim 1 , wherein the at least one of the clusters includes a first cluster, and wherein the operations further comprise:

ascertaining a measure of similarity of data assigned to the first cluster, wherein the measure of similarity is a function, for at least one element, of the frequency in data assigned to the first cluster of the element.

14 . The signal-bearing medium of claim 1 , wherein the at least one of the clusters includes a first cluster and a second cluster, and wherein the operations further comprise:

ascertaining a measure of dissimilarity between data assigned to the first cluster and data assigned to the second cluster, wherein the measure of dissimilarity is a function, for at least one element, of the frequency of the element in the data assigned to the first cluster, and the frequency of the element in the data assigned to the second cluster.

15 . The signal-bearing medium of claim 1 , wherein the operations further comprise computing a measure of quality of clustering associated with a particular assignment of data to the plurality of clusters, wherein the measure of quality is a function, for at least one of the categories, for at least one element associated with the category, of the frequency of the element in the assigned data.

16 . The signal-bearing medium of claim 8 , wherein the operations further comprise computing a first measure of quality of clustering corresponding with a particular assignment of data to clusters, wherein the first measure of quality is a function of the difference between the first fractions computed for corresponding elements in different clusters.

17 . The signal-bearing medium of claim 8 , wherein the operations further comprise, for at least one element, subtracting the first fraction for the element computed for a first cluster, from the first fraction for the element computed for a second cluster to ascertain a first cluster-second cluster difference for the element.

18 . The signal-bearing medium of claim 17 , wherein the difference is ascertained for each element.

19 . The signal-bearing medium of claim 17 , wherein the operations further comprise, adding together each first cluster-second cluster difference to form a sum representing a first measure of quality of clustering associated with a particular assignment of data to clusters.

20 . The signal-bearing medium of claim 17 , wherein the operations further comprise, multiplying together each first cluster-second cluster difference to form a product representing a first measure of quality of clustering associated with a particular assignment of data to clusters.

21 . The signal-bearing medium of claim 17 , wherein the operations further comprise:

squaring each ascertained first cluster-second cluster difference; and

adding together each squared ascertained first cluster-second cluster difference to form a sum representing a first measure of quality of clustering associated with a particular assignment of data to clusters.

22 . The signal-bearing medium of claim 21 , wherein the operations further comprise, for at least one element, subtracting the first fraction for the element computed for the second cluster, from the first fraction for the element computed for a third cluster to ascertain a second cluster-third cluster difference for the element.

23 . The signal-bearing medium of claim 22 , wherein the operations further comprise:

squaring each ascertained second cluster-third cluster difference; and

adding together each squared ascertained second cluster-third cluster difference to form a sum representing a second measure of quality of clustering.

24 . The signal-bearing medium of claim 23 , wherein the operations further comprise:

adding the first measure of quality of clustering to the second measure of quality of clustering to form a sum representing a third measure of quality of the clustering.

25 . The signal-bearing medium of claim 16 , wherein the operations further comprise:

changing the cluster assignment of at least one datum to a different cluster;

computing an updated measure of quality of clustering;

comparing the updated measure of quality of clustering to a measure of quality of clustering previously computed; and

choosing a cluster assignment that results in a better measure of quality of clustering.

26 . The signal-bearing medium of claim 25 , wherein the better measure of quality of clustering is the largest measure of quality of clustering.

27 . The signal-bearing medium of claim 25 , wherein the operations further comprise iteratively adjusting the cluster assignment of at least one datum to a different cluster to improve the measure of quality of clustering, using an evolutionary algorithm.

28 . The signal-bearing medium of claim 27 , wherein the iterative adjustment is performed using simulated annealing.

29 . The signal-bearing medium of claim 27 , wherein the iterative adjustment is performed using a TABU search.

30 . The signal-bearing medium of claim 27 , wherein the iterative adjustment is performed using hill-climbing.

31 . The signal-bearing medium of claim 27 , wherein the iterative adjustment is performed using meta-heuristics.

32 . The signal-bearing medium of claim 27 , wherein the iterative adjustment is performed using combinations of meta-heuristics.

33 . The signal-bearing medium of claim 1 , wherein the categorical data are described in terms of fuzzy membership functions.

34 . The signal-bearing medium of claim 16 , wherein the operations further comprise:

removing a first datum that has been initially assigned to a first cluster from the first cluster, and assigning the first datum to an alternative cluster, to create a first alternative assignment of the data records;

ascertaining a first alternative measure of quality of clustering corresponding with the first alternative assignment of the data records; and

computing and recording a first difference score, wherein the first difference score is a difference between the first measure of quality of clustering and the first alternative measure of quality of clustering.

35 . The signal-bearing medium of claim 34 , wherein the alternative cluster is a cluster determined to provide the best effect on the first alternative measure of quality of clustering in comparison to other clusters.

36 . The signal-bearing medium of claim 34 , wherein the operations further comprise:

removing a second datum that has been initially assigned to the first cluster from the first cluster, and assigning the second datum to an alternative cluster, to create a second alternative assignment of the data records;

ascertaining a second alternative measure of quality of clustering corresponding with the second alternative assignment of the data records; and

computing and recording a second difference score, wherein the second difference score is a difference between the first measure of quality of clustering and the second alternative measure of quality of clustering.

37 . The signal-bearing medium of claim 36 , wherein the operations further comprise, for at least one cluster, generating a frequency distribution of difference scores for corresponding datum that were initially assigned to the cluster.

38 . The signal-bearing medium of claim 37 , wherein the operations further comprise identifying statistical relationships of difference scores to identify outliers.

39 . The signal-bearing medium of claim 37 , wherein the operations further comprise identifying statistical relationships of difference scores to identify exemplars.

40 . The signal-bearing medium of claim 37 , wherein the operations further comprise identifying statistical relationships of difference scores to identify anomalies.

41 . The signal-bearing medium of claim 1 , wherein the operations further comprise:

for at least one of the clusters, determining the frequency in data assigned to the cluster of datum having both a first specified element associated with a first category and a second specified element associated with a second category.

42 . The signal-bearing medium of claim 1 , wherein the operations further comprise:

ascertaining a measure of similarity of data assigned to a first cluster, wherein the measure of similarity is a function of the frequency in data assigned to the first cluster of datum having both a first specified element associated with a first category and a second specified element associated with a second category.

43 . The signal-bearing medium of claim 1 , wherein the operations further comprise:

ascertaining a measure of dissimilarity between data assigned to a first cluster and data assigned to a second cluster, wherein the measure of dissimilarity is a function of the frequency in data assigned to the first cluster, and of the frequency in data assigned to the second cluster, of datum having both a first specified element associated with a first category and a second specified element associated with a second category.

44 . The signal-bearing medium of claim 1 , wherein elements associated with a first category are called first-category elements and wherein elements associated with a second category are called second-category elements, and wherein the operations further comprise:

for each of a plurality of the clusters, for each first category element, and for each second category element, ascertaining a second count of instances in the data assigned to the cluster that a datum has both the first-category element and the second-category element.

45 . The signal-bearing medium of claim 1 , wherein elements associated with a first category are called first-category elements, and wherein elements associated with a second category are called second-category elements, and wherein the operations further comprise:

for each first category element, and for each second category element, ascertaining a second tally of the instances in the data that a datum has both the first-category element and the second-category element.

46 . The signal-bearing medium of claim 1 , wherein elements associated with a first category are called first-category elements, and wherein elements associated with a second category are called second-category elements, and wherein the operations further comprise:

for each of a plurality of the clusters, for each first category element, and for each second category element, ascertaining a second count of instances in the data assigned to the cluster that a datum has both the first-category element and the second category element; and

for each first category element, and for each second category element, ascertaining a second tally of the instances in the data that a datum has both the first-category element and the second-category element.

47 . The signal-bearing medium of claim 46 , wherein the second count and the second tally are ascertained using only a portion of the data, wherein the portion of the data used is selected based on the number of instances of combinations of elements in respective categories.

48 . The signal-bearing medium of claim 46 , wherein a portion of the data is excluded when ascertaining the second count and the second tally, wherein the portion of the data that is excluded is selected based on the number of instances of combinations of elements in respective categories.

49 . The signal-bearing medium of claim 46 , wherein the operations further comprise:

for each of the plurality of clusters, computing a plurality of second fractions, wherein each second fraction is one of the ascertained second counts for the cluster divided by the second tally.

50 . The signal-bearing medium of claim 49 , wherein the operations further comprise, for a plurality of second fractions computed for a first cluster and a plurality of corresponding second fractions computed for a second cluster, computing a measure of the difference between the second fraction computed for the first cluster and a corresponding second fraction computed for the second cluster, wherein corresponding second fractions are computed for a same first-category element and a same second-category element.

51 . The signal-bearing medium of claim 50 , wherein each measure of the difference is added together to form a sum representing a measure of quality of clustering associated with a particular assignment of data to clusters.

52 . The signal-bearing medium of claim 50 , wherein each measure of the difference is multiplied together to form a product representing a measure of quality of clustering associated with a particular assignment of data to clusters.

53 . The signal-bearing medium of claim 50 , wherein the measure of the difference is a squared difference between corresponding second fractions.

54 . The signal-bearing medium of claim 50 , wherein the measure of the difference is a weighted squared difference between corresponding second fractions.

55 . The signal-bearing medium of claim 50 , wherein the operations further comprise:

changing the cluster assignment of at least one element to a different cluster;

computing an updated measure of quality of the clustering;

comparing the updated measure of quality of the clustering to a measure of quality of the clustering previously computed; and

choosing a cluster assignment that results in a better updated measure of quality of clustering.

56 . The signal-bearing medium of claim 50 , wherein the operations further comprise, for a plurality of second fractions computed for the second cluster and a plurality of corresponding second fractions computed for a third cluster, computing a measure of the difference between the second fraction computed for the second cluster and the corresponding second fraction computed for the third cluster, wherein corresponding second fractions are computed for a same first-category element and a same second-category element.

57 . The signal-bearing medium of claim 56 , wherein each measure of the difference between second fractions associated with the first cluster and second fractions associated with the second cluster, and between second fractions associated with the second cluster and second fractions associated with the third cluster, is added together to form a sum representing a measure of the quality of clustering associated with a particular assignment of data to clusters.

58 . The signal-bearing medium of claim 56 , wherein each measure of the difference between second fractions associated with the first cluster and second fractions associated with the second cluster, and between second fractions associated with the second cluster and second fractions associated with the third cluster, is multiplied together to form a product representing a measure of the quality of clustering associated with a particular assignment of data to clusters.

59 . The signal-bearing medium of claim 51 , wherein the operations further comprise:

removing a first datum that has been initially assigned to the first cluster from the first cluster, and assigning the first datum to an alternative cluster, to create a first alternative assignment of the data records;

ascertaining a first alternative measure of quality of clustering corresponding with the first alternative assignment of the data records; and

computing and recording a first difference score, wherein the first difference score is a difference between the first measure of quality of clustering and the first alternative measure of quality of clustering.

60 . The signal-bearing medium of claim 59 , wherein the alternative cluster is a cluster determined to provide the best effect on the first alternative measure of quality of clustering in comparison to other clusters.

61 . The signal-bearing medium of claim 59 , wherein the operations further comprise:

removing a second datum that has been initially assigned to the first cluster from the first cluster, and assigning the second datum to an alternative cluster, to create a second alternative assignment of the data records;

ascertaining a second alternative measure of quality of clustering corresponding with the second alternative assignment of the data records; and

computing and recording a second difference score, wherein the second difference score is a difference between the first measure of quality of clustering and the second alternative measure of quality of clustering.

62 . The signal-bearing medium of claim 61 , wherein the operations further comprise, for at least one cluster, generating a frequency distribution of difference scores for corresponding datum that were initially assigned to the cluster.

63 . The signal-bearing medium of claim 62 , wherein the operations further comprise identifying statistical relationships of difference scores to identify outliers and exemplars.

64 . The signal-bearing medium of claim 62 , wherein the operations further comprise identifying statistical relationships of difference scores to identify anomalies.

65 . The signal-bearing medium of claim 1 , wherein the operations further comprise, for at least one of the clusters, determining the frequency in data assigned to the cluster of datum having a first specified element associated with a first category and a second specified element associated with a second category and a third specified element associated with a third category.

66 . The signal-bearing medium of claim 1 , wherein elements associated with a first category are called first-category elements, and wherein elements associated with a second category are called second-category elements, and wherein elements associated with a third category are called third-category elements, and wherein the operations further comprise:

for each of a plurality of the clusters, for each first category element, and for each second category element, and for each third category element, ascertaining a third count of instances in the data assigned to the cluster that a datum has both the first-category element and the second-category element and the third category element; and

for each first category element, and for each second category element, and for each third category element, ascertaining a third tally of instances in the data that a datum has the first-category element and the second-category element and the third category element; and

for each of the plurality of clusters, computing a plurality of third fractions, wherein each third fraction is one of the ascertained third counts for the cluster divided by the third tally.

67 . The signal-bearing medium of claim 66 , wherein the operations further comprise:

for a plurality of third fractions computed for a first cluster and a plurality of corresponding third fractions computed for a second cluster, computing a measure of the difference between the third fraction computed for the first cluster and the corresponding third fraction computed for the second cluster, wherein corresponding third fractions are computed for a same first-category element and a same second-category element and a same third category element; and

calculating a measure of quality of clustering, wherein the measure of quality of clustering is a function of each computed measure of the difference between the third fraction computed for the first cluster and the corresponding third fraction computed for the second cluster.

68 . A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform operations for assigning categorical data to a plurality of clusters, the operations comprising:

identifying a plurality of categories associated with the data;

for each category in the plurality of categories, identifying at least one element associated with the category;

specifying a number of clusters to which the data may be assigned;

assigning at least some of the data, wherein each assigned datum is assigned to a respective one of the clusters;

for at least one of the clusters, ascertaining a first count, for each of a plurality of categories, for at least one element associated with the category, of instances of the element in the data assigned to the cluster;

for each of a plurality of categories, for at least one element associated with the category, ascertaining a first tally of instances of the element in the data;

for at least one cluster, computing a first fraction for at least one element, wherein the first fraction is the first count for the element in the cluster divided by the first tally for the element;

for each of a plurality of elements, computing a measure of the difference between the first fraction for an element corresponding with a first cluster and the first fraction for the element corresponding with a second cluster;

wherein elements associated with a first category are called first-category elements, and wherein elements associated with a second category are called second-category elements, and for each of a plurality of clusters, for each first category element, and for each second category element, ascertaining a second count of instances in the data assigned to the cluster that a datum has both the first-category element and the second category element;

for each first category element, and for each second category element, ascertaining a second tally of the instances in the data that a datum has both the first-category element and the second category element;

for each of the plurality of clusters, computing a plurality of second fractions, wherein each second fraction is one of the ascertained second counts for the cluster divided by the second tally;

for a plurality of second fractions computed for a first cluster and a plurality of corresponding second fractions computed for a second cluster, computing a measure of the difference between the second fraction computed for the first cluster and the corresponding second fraction computed for the second cluster, wherein corresponding second fractions are computed for a same first-category element and a same second category element; and

computing a measure of quality of clustering corresponding with a particular assignment of data to clusters, wherein the measure of quality of clustering is a function, for each of a plurality of elements, of the measure of the difference between the first fraction for an element corresponding with a first cluster and the first fraction for the element corresponding with a second cluster, and is a function of the measure of the difference between each of a plurality of second fractions computed for the first cluster and each of a plurality of corresponding second fractions computed for the second cluster.

69 . The signal-bearing medium of claim 68 , wherein the operations further comprise:

changing the cluster assignment of at least one element to a different cluster;

computing an updated measure of quality of the clustering;

comparing the updated measure of quality of the clustering to a measure of quality of the clustering previously computed; and

choosing a cluster assignment that results in a better updated measure of quality of the clustering, wherein the better updated measure of quality of clustering is defined as the measure of quality that is the largest.

70 . A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform operations for assigning categorical data to a plurality of clusters, the operations comprising:

identifying a plurality of categories associated with the data;

for each category in the plurality of categories, identifying a plurality of elements associated with the category;

specifying a number of clusters to which the data may be assigned;

assigning the data, wherein each assigned datum is assigned to a respective one of the clusters;

for each cluster, for each category, for each element associated with the category, ascertaining a count of the instances of the element in data assigned to the cluster, to ascertain a count for each element;

for each category, ascertaining a tally for each element associated with the category of the instances in the data of the element in the category; and

for each cluster, computing a fraction for each element, wherein the fraction is the count for the element in the cluster divided by the tally for the element.

71 . A computer data signal embodied in a carrier wave embodying a program of machine-readable instructions executable by a digital processing apparatus to perform operations for assigning categorical data to a plurality of clusters, the operations comprising:

identifying a plurality of categories associated with the data;

for each category in the plurality of categories, identifying at least one element associated with the category;

specifying a number of clusters to which the data may be assigned;

assigning at least some of the data, wherein each assigned datum is assigned to a respective one of the clusters; and

for at least one of the clusters, ascertaining a first count, for each of a plurality of the categories, for at least one element associated with the category, of instances of the element in the data assigned to the cluster.

72 . A computing system, comprising:

a memory; and

a processing device coupled to the memory, wherein the processing device is programmed to perform operations for assigning categorical data to a plurality of clusters, the operations comprising:

identifying a plurality of categories associated with the data;

for each category in the plurality of categories, identifying at least one element associated with the category;

specifying a number of clusters to which the data may be assigned;

assigning at least some of the data, wherein each assigned datum is assigned to a respective one of the clusters; and

for at least one of the clusters, ascertaining a first count, for each of a plurality of the categories, for at least one element associated with the category, of instances of the element in the data assigned to the cluster.

73 . The computing system of claim 72 , wherein the operations further comprise, for each of a plurality of the categories, for at least one element associated with the category, ascertaining a first tally of instances of the element in the data.

74 . The computing system of claim 73 , wherein the operations further comprise, for at least one cluster, computing a first fraction for at least one element, wherein the first fraction is the first count for the element in the cluster divided by the first tally for the element.

75 . A computing system for assigning categorical data to a plurality of clusters, comprising:

means for identifying a plurality of categories associated with the data;

means for, for each category in the plurality of categories, identifying at least one element associated with the category;

means for specifying a number of clusters to which the data may be assigned;

means for assigning at least some of the data, wherein each assigned datum is assigned to a respective one of the clusters; and

means for, for at least one of the clusters, ascertaining a first count, for each of a plurality of the categories, for at least one element associated with the category, of instances of the element in the data assigned to the cluster;

means for, for each of a plurality of the categories, for at least one element associated with the category, ascertaining a first tally of instances of the element in the data; and

means for, for at least one cluster, computing a first fraction for at least one element, wherein the first fraction is the first count for the element in the cluster divided by the first tally for the element.

76 . A method for assigning categorical data to a plurality of clusters, comprising the following operations:

identifying a plurality of categories associated with the data;

for each category in the plurality of categories, identifying at least one element associated with the category;

specifying a number of clusters to which the data may be assigned;

assigning at least some of the data, wherein each assigned datum is assigned to a respective one of the clusters; and

for at least one of the clusters, determining, for at least one category, the frequency in data assigned to the cluster of at least one element associated with the category.

77 . The method of claim 76 , wherein the operation of, for at least one of the clusters, determining, for at least one category, the frequency in data assigned to the cluster of at least one element associated with the category, comprises ascertaining a first count, for each of a plurality of the categories, for at least one element associated with the category, of instances of the element in the data assigned to the cluster.

78 . The method of claim 77 , wherein the operations further comprise, for each of a plurality of the categories, for at least one element associated with the category, ascertaining a first tally of instances of the element in the data.

79 . The method of claim 78 , wherein the operations further comprise, for at least one cluster, computing a first fraction for at least one element, wherein the first fraction is the first count for the element in the cluster divided by the first tally for the element.

80 . The method of claim 79 , wherein the operations further comprise, for at least one element, computing a measure of the difference between the first fraction for the element corresponding with a first cluster and the first fraction for the element corresponding with a second cluster.

81 . The method of claim 80 , wherein the measure of the difference is a weighted squared difference between the first fraction for the element corresponding with the first cluster and the first fraction for the element corresponding with the second cluster.

82 . The method of claim 80 , wherein the operations further comprise computing a first measure of quality of clustering corresponding with a particular assignment of data to clusters, wherein the first measure of quality is a function of the difference between the first fractions computed for corresponding elements in different clusters.

83 . The method of claim 82 , wherein the operations further comprise:

changing the cluster assignment of at least one datum to a different cluster;

computing an updated measure of quality of clustering;

comparing the updated measure of quality of clustering to the first measure of quality; and

choosing a cluster assignment that results in a better measure of quality of clustering, wherein the better measure of quality of clustering is defined to be a larger measure of quality of clustering.

84 . The method of claim 82 , wherein the operations further comprise:

removing a first datum that has been initially assigned to a first cluster from the first cluster, and assigning the first datum to an alternative cluster, to create a first alternative assignment of the data records;

ascertaining a first alternative measure of quality of clustering corresponding with the first alternative assignment of the data records; and

computing and recording a first difference score, wherein the first difference score is a difference between the first measure of quality of clustering and the first alternative measure of quality of clustering.

85 . The method of claim 84 , wherein the operations further comprise:

removing a second datum that has been initially assigned to the first cluster from the first cluster, and assigning the second datum to an alternative cluster, to create a second alternative assignment of the data records;

ascertaining a second alternative measure of quality of clustering corresponding with the second alternative assignment of the data records;

computing and recording a second difference score, wherein the second difference score is a difference between the first measure of quality of clustering and the second alternative measure of quality of clustering;

for at least one cluster, generating a frequency distribution of difference scores for corresponding datum that were initially assigned to the cluster; and

identifying statistical relationships of difference scores to identify outliers, exemplars, and anomalies.

86 . A method for assigning categorical data to a plurality of clusters, the method comprising the following operations:

identifying a plurality of categories associated with the data;

for each category in the plurality of categories, identifying at least one element associated with the category;

specifying a number of clusters to which the data may be assigned;

assigning at least some of the data, wherein each assigned datum is assigned to a respective one of the clusters;

for at least one of the clusters, ascertaining a first count, for each of a plurality of categories, for at least one element associated with the category, of instances of the element in the data assigned to the cluster;

for each of a plurality of categories, for at least one element associated with the category, ascertaining a first tally of instances of the element in the data;

for at least one cluster, computing a first fraction for at least one element, wherein the first fraction is the first count for the element in the cluster divided by the first tally for the element;

for each of a plurality of elements, computing a measure of the difference between the first fraction for an element corresponding with a first cluster and the first fraction for the element corresponding with a second cluster;

wherein elements associated with a first category are called first-category elements, and wherein elements associated with a second category are called second-category elements, and for each of a plurality of clusters, for each first category element, and for each second category element, ascertaining a second count of instances in the data assigned to the cluster that a datum has both the first-category element and the second category element;

for each first category element, and for each second category element, ascertaining a second tally of the instances in the data that a datum has both the first-category element and the second category element;

for each of the plurality of clusters, computing a plurality of second fractions, wherein each second fraction is one of the ascertained second counts for the cluster divided by the second tally;

for a plurality of second fractions computed for a first cluster and a plurality of corresponding second fractions computed for a second cluster, computing a measure of the difference between the second fraction computed for the first cluster and the corresponding second fraction computed for the second cluster, wherein corresponding second fractions are computed for a same first-category element and a same second category element; and

computing a measure of quality of clustering corresponding with a particular assignment of data to clusters, wherein the measure of quality of clustering is a function, for each of a plurality of elements, of the measure of the difference between the first fraction for an element corresponding with a first cluster and the first fraction for the element corresponding with a second cluster, and is a function of the measure of the difference between each of a plurality of second fractions computed for the first cluster and each of a plurality of corresponding second fractions computed for the second cluster.

87 . The method of claim 86 , wherein the operations further comprise:

changing the cluster assignment of at least one element to a different cluster;

computing an updated measure of quality of the clustering;

comparing the updated measure of quality of the clustering to a measure of quality of the clustering previously computed; and

choosing a cluster assignment that results in a better updated measure of quality of the clustering.