Data classification methods and apparatus for use with data fusion

• US 8,234,226 B2
• Filed: 07/30/2010
• Issued: 07/31/2012
• Est. Priority Date: 09/28/2004
• Status: Active Grant

• Current Assignee: Nielsen Company (US) LLC (RR Donnelley & Sons Company)
• Original Assignee: The Nielsen Company LLC (MOOD Media Corporation)
• Inventors: Samson, Jerome, McMillan, Francis Gavin
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US12/847,856
• Publication Number:
  US 20100299365A1
• Time in Patent Office: 732 Days
• Field of Search: 706/1
• US Class Current: 706/1
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Methods and apparatus for classifying data for use in data fusion processes are disclosed. An example method of classifying data selectively groups nodes of a classification tree so that each node is assigned to only one of a plurality of groups and so that at least one of the groups includes at least two of the nodes. Data is classified based on the classification tree and the selective grouping of the nodes, and the results displayed.

Claims

1. A method, comprising:

generating a classification tree having a plurality of terminal nodes, each of the terminal nodes having a frequency distribution related to a plurality of classes at the respective terminal node;

at each terminal node, combining the frequency distribution of the terminal node with an overall population frequency distribution to generate an index value for each of the classes at the terminal node such that each of the index values represents a difference between a corresponding portion of the frequency distribution and a corresponding portion of the overall population frequency distribution;

modifying the classification tree based on the index values; and

associating each data record of a first dataset with one of the terminal nodes based on the modified classification tree.

2. A method as defined in claim 1, wherein the first dataset is to be fused with a second dataset based on the associations of the data records with the terminal nodes.

3. A method as defined in claim 1, wherein modifying the classification tree comprises arranging the terminal nodes based on the index values.

4. A method as defined in claim 3, wherein arranging the terminal nodes based on the index values comprises identifying which of the terminal nodes has a greatest index value for a first one of the classes and is unassigned to the first class.

5. A method as defined in claim 4, further comprising, when the identified terminal node has been assigned to a second one of the classes different from the first class, determining whether a first index value of the identified terminal node for the first class is greater than a second index value of the identified terminal node for the second class.

6. A method as defined in claim 5, further comprising making the identified terminal node unavailable to be assigned to the first class when the first index value is less than or equal to the second index value.

7. A method as defined in claim 3, further comprising comparing a sum-of-weights of a weight of the identified terminal node and one or more weights of terminal nodes currently assigned to the first class to a total weight of the first class within an overall population.

8. A method as defined in claim 7, further comprising making the identified terminal node unavailable to be assigned to the first class when the sum-of-weights exceeds the total weight of the first class within the overall population.

9. A tangible machine readable storage medium comprising instructions that, when executed, cause a machine to at least:

generate a classification tree having a plurality of terminal nodes, the terminal nodes having respective frequency distributions related to a plurality of classes at the respective terminal node;

for each of the terminal nodes, combine the frequency distribution of the respective terminal node with an overall population frequency distribution to generate an index value for respective ones of the classes at the terminal node such that the index values respectively represent a difference between a corresponding portion of the frequency distribution and a corresponding portion of the overall population frequency distribution;

modify the classification tree based on the index values; and

associate data records of a first dataset with respective ones of the terminal nodes based on the modified classification tree.

10. A tangible machine readable medium as defined in claim 9, wherein the instructions, when executed, cause the machine to fuse the first dataset with a second dataset using the associations of the data records with the terminal nodes.

11. A tangible machine readable medium as defined in claim 9, wherein the instructions, when executed, cause the machine to modify the classification tree by arranging the terminal nodes based on the index values.

12. A tangible machine readable medium as defined in claim 11, wherein the instructions, when executed, cause the machine to arrange the terminal nodes based on the index values by identifying which of the terminal nodes has a greatest index value for a first one of the classes and is unassigned to the first class.

13. A tangible machine readable medium as defined in claim 12, wherein the instructions, when executed, cause the machine to, when the identified terminal node has been assigned to a second one of the classes different from the first class, determine whether a first index value of the identified terminal node for the first class is greater than a second index value of the identified terminal node for the second class.

14. A tangible machine readable medium as defined in claim 13, wherein the instructions, when executed, cause the machine to make the identified terminal node unavailable to be assigned to the first class when the first index value is less than or equal to the second index value.

15. A tangible machine readable medium as defined in claim 11, wherein the instructions, when executed, cause the machine to compare a sum-of-weights of a weight of the identified terminal node and one or more weights of terminal nodes currently assigned to the first class to a total weight of the first class within an overall population.

16. A tangible machine readable medium as defined in claim 15, wherein the instructions, when executed, cause the machine to make the identified terminal node unavailable to be assigned to the first class when the sum-of-weights exceeds the total weight of the first class within the overall population.

17. An apparatus, comprising:

a tree generator to generate a classification tree having a plurality of terminal nodes, the terminal nodes having respective frequency distributions related to a plurality of classes at the respective terminal node;

a node analyzer to combine the frequency distribution related to the classes at a first one of the terminal nodes with an overall population frequency distribution to generate an index value for each of the classes at the first terminal node such that each of the index values represents a difference between a corresponding portion of the frequency distribution and a corresponding portion of the overall population frequency distribution;

a node grouper to modify the classification tree based on the index values; and

an assignor to associate data records of a first dataset with respective ones of the terminal nodes.

18. An apparatus as defined in claim 17, further comprising a fuser to fuse the first dataset with a second dataset based on the associations of the data records with the terminal nodes.

19. An apparatus as defined in claim 17, wherein the node grouper is to modify the classification tree by arranging the terminal nodes based on the index values.

20. An apparatus as defined in claim 19, wherein the node grouper is to arrange the terminal nodes based on the index values by identifying which of the terminal nodes has a greatest index value for a first one of the classes and is unassigned to the first class.

21. An apparatus as defined in claim 20, wherein the node grouper is to, when the identified terminal node has been assigned to a second one of the classes different from the first class, determine whether a first index value of the identified terminal node for the first class is greater than a second index value of the identified terminal node for the second class.

22. An apparatus as defined in claim 21, wherein the node grouper is to make the identified terminal node unavailable to be assigned to the first class when the first index value is less than or equal to the second index value.

23. An apparatus as defined in claim 19, wherein the node grouper is to compare a sum-of-weights of a weight of the identified terminal node and one or more weights of terminal nodes currently assigned to the first class to a total weight of the first class within an overall population to determine whether the first class can accept the identified terminal node.

24. An apparatus as defined in claim 23, wherein the node grouper is to make the identified terminal node unavailable to be assigned to the first class when the sum-of-weights exceeds the total weight of the first class within the overall population.