Multi-center canopy clustering
A canopy clustering process merges at least one set of multiple single-center canopies together into a merged multi-center canopy. Multi-center canopies, as well as the single-center canopies, can then be used to partition data objects in a dataset. The multi-center canopies allow a canopy assignment condition constraint to be relaxed without risk of leaving any data objects in a dataset outside of all canopies. Approximate distance calculations can be used as similarity metrics to define and merge canopies and to assign data objects to canopies. In one implementation, a distance between a data object and a canopy is represented as the minimum of the distances between the data object and each center of a canopy (whether merged or unmerged), and the distance between two canopies is represented as the minimum of the distances for each pairing of the center(s) in one canopy and the center(s) in the other canopy.
1. A method executed by a processor comprising:
mapping data objects of a dataset defined in memory to individual single center canopies according to a tight mapping condition, each center corresponding to one of the mapped data objects;
merging using a processor at least two of the single center canopies into a multi-center canopy according to a tight merger condition, each multi-center canopy having at least two separate centers each corresponding to a different mapped data object;
assigning each data object of the dataset to one or more of the multi-center canopies and unmerged single center canopies; and
partitioning the data objects of the dataset by clustering the data objects that share the same canopy.
2. The method of claim 1 wherein the mapping operation comprises:
mapping different data objects to the individual single center canopies using independent canopy mapping operations for at least two of the single center canopies.
3. The method of claim 1 wherein the merging operation comprises:
merging the at least two of the single center canopies into a multi-center canopy, if the at least two single center canopies satisfy the tight merger condition.
4. The method of claim 3 where in the tight merger condition is satisfied if a similarity metric representing a distance between the at least two canopies is less than a tight merger threshold.
5. The method of claim 3 wherein the tight merger condition is satisfied if the similarity metric between two canopies satisfies the tight merger condition, and the similarity metric between two canopies is determined by finding a minimum pairwise distance between any center of a first canopy and any center of a second canopy.
6. The method of claim 1 wherein the assigning operation comprises:
assigning a data object of the dataset to a canopy if the data object and the canopy satisfy a loose assignment condition.
7. The method of claim 6 wherein the loose assignment condition is satisfied if a similarity metric representing a distance between the data object and the canopy is less than a loose assignment threshold.
8. The method of claim 6 wherein the loose assignment condition is satisfied if the similarity metric between the data object and the canopy satisfies the loose assignment condition and the similarity metric is determined by finding a minimum pairwise distance between the data object and any center of a canopy.
9. A system comprising:
a processor;
one or more canopy mappers configured to map data objects of a dataset to individual single center canopies according to a tight mapping condition, each center corresponding to one of the mapped data objects;
a canopy merger configured to merge at least two of the single center canopies into a multi-center canopy according to a tight merger condition, each multi-center canopy having at least two separate centers each corresponding to a different mapped data object; and
a canopy assigner configured to assign each data object of the dataset to one or more of the multi-center canopies and unmerged single center canopies.
10. The system of claim 9 wherein the canopy merger is configured to merge the at least two of the single center canopies into a multi-center canopy, if a similarity metric computed between at least two single center canopies satisfy the tight merger condition, the similarity metric between two canopies being determined by finding a minimum pairwise distance between any center of a first canopy and any center of a second canopy.
11. The system of claim 9 wherein the canopy assigner is configured to assign a data object of the dataset to a canopy if the similarity metric between the data object and the canopy satisfies a loose assignment condition, the similarity metric being determined by finding a minimum pairwise distance between the data object and any center of a canopy.
12. One or more computer-readable storage hardware device encoding computer-executable instructions for executing on a computer system a computer process, the computer process comprising:
mapping data objects of a dataset to individual single center canopies according to a tight mapping condition, each center corresponding to one of the mapped data objects;
merging at least two of the single center canopies into a multi-center canopy according to a tight merger condition, each multi-center canopy having at least two separate centers each corresponding to a different mapped data object; and
assigning each data object of the dataset to one or more of the multi-center canopies and unmerged single center canopies.
13. The one or more computer-readable storage hardware device of claim 12 wherein the mapping operation comprises:
mapping different data objects to the individual single center canopies using independent canopy mapping operations for at least two of the single center canopies.
14. The one or more computer-readable storage hardware device of claim 12 wherein the merging operation comprises:
merging the at least two of the single center canopies into a multi-center canopy, if the at least two single center canopies satisfy the tight merger condition.
15. The one or more computer-readable storage hardware device of claim 14 where in the tight merger condition is satisfied if a similarity metric representing a distance between the at least two canopies is less than a tight merger threshold.
16. The one or more computer-readable storage hardware device of claim 14 wherein the tight merger condition is satisfied if the similarity metric between two canopies satisfies the tight merger condition, and the similarity metric between two canopies is determined by finding a minimum pairwise distance between any center of a first canopy and any center of a second canopy.
17. The one or more computer-readable storage hardware device of claim 12 wherein the assigning operation comprises:
assigning a data object of the dataset to a canopy if the data object and the canopy satisfy a loose assignment condition.
18. The one or more computer-readable storage hardware device of claim 17 wherein the loose assignment condition is satisfied if a similarity metric representing a distance between the data object and the canopy is less than a loose assignment threshold.
19. The one or more computer-readable storage hardware device of claim 17 wherein the loose assignment condition is satisfied if the similarity metric between the data object and the canopy satisfies the loose assignment condition and the similarity metric is determined by finding a minimum pairwise distance between the data object and any center of a canopy.
20. The one or more computer-readable storage hardware device of claim 12 wherein the computer process further comprises:
partitioning the data objects of the dataset by clustering the data objects that share the same canopy.