Method and System for Data Classification Using a Self-Organizing Map

• US 20080071708A1
• Filed: 08/25/2006
• Published: 03/20/2008
• Est. Priority Date: 08/25/2006
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Cort, Gary P., Dara, Rozita A., Cicchello, Orlando, Khan, Mohammad Tauseef, Azim, Jawad
• Granted Patent: US 7,672,915 B2
• Time in Patent Office: Days
• US Class Current: 706/20
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/2155 characterised by the incorporation of unlabelled data, e.g. multiple instance learning [MIL], semi-supervised techniques using expectation-maximisation [EM] or naïve labelling
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06N 3/08 Learning methods

Abstract

The described embodiments relate to methods and systems for data classification using a self-organizing map. Certain embodiments relate to a method of labeling data for training a classifier, comprising: obtaining data, the data comprising labeled data and unlabeled data; generating a self-organizing map of the data; and a labeling at least some of the unlabeled data based on proximity of the unlabeled data to labeled data within the self-organizing map to generate self-labeled data. The method may include training a classifier based on the labeled and self-labeled data. Other embodiments relate to systems and computer readable media configured to perform, or allow performance of, the method embodiments.

Claims

1. A method of labeling data for training a classifier, comprising:

obtaining data, the data comprising labeled data and unlabeled data;

generating a self-organizing map of the data; and

labeling at least some of the unlabeled data based on proximity of the unlabeled data to labeled data within the self-organizing map to generate self-labeled data.

2. The method of claim 1, further comprising training a classifier based on the labeled and self-labeled data.

3. The method of claim 1, wherein the labeling is based on a proximity relationship of unlabeled and labeled data within a neighborhood of nodes of the self-organizing map.

4. The method of claim 1, wherein the amount of labeled data is increased by adding the self-labeled data and the labeling is repeated.

5. The method of claim 4, wherein the generating and labeling are repeated until a predetermined termination condition is satisfied.

6. The method of claim 4, wherein the labeling is repeated until a predetermined termination condition is satisfied.

7. The method of claim 1, further comprising auto-completing a data field or a user selection using the classifier.

8. The method of claim 3, wherein the labeling comprises assigning a class to the self-labeled data based on the labeled data in the same neighborhood.

9. The method of claim 1, wherein the labeling comprises labeling unlabeled data associated with each of a plurality of nodes in the self-organizing map with a label of labeled data associated with the respective node.

10. The method of claim 9, wherein the labeling further comprises, for each neighborhood around a node associated with labeled data, determining whether data associated with nodes within a predetermined neighborhood depth have different labels and, if not, labeling all unlabeled data associated with nodes in the respective neighborhood with the label of the labeled data in that neighborhood.

11. The method of claim 10, wherein the predetermined neighborhood depth is two.

12. The method of claim 10, wherein the labeling further comprises, where nodes within a same neighborhood are determined to be associated with different labeled data, labeling unlabeled data associated with nodes in the same neighborhood that are adjacent only one node associated with labeled data, wherein the unlabeled data is assigned the label of the labeled data associated with the one adjacent node.

13. A system for labeling data for use in classification, comprising:

at least one processor;

a memory accessible to the at least one processor and storing program instructions executable by the at least one processor, the program instructions being arranged in a plurality of modules comprising a clustering module and a self-labeling module;

wherein the clustering module is configured to receive data comprising labeled data and unlabeled data and to generate a self-organizing map of the data; and

wherein the self-labeling module is configured to label at least some of the unlabeled data based on proximity of the unlabeled data to labeled data within the self-organizing map to thereby generate self-labeled data.

14. The system of claim 13, further comprising a classification module, wherein the classification module is configured train a classifier based on the labeled and self-labeled data.

15. The system of claim 13, wherein the labeling by the self-labeling module is based on a proximity relationship of unlabeled and labeled data within a neighborhood of nodes of the self-organizing map.

16. The system of claim 13, wherein the self-labeling module is configured to add the self-labeled data to the labeled data and to generate further self-labeled data from the unlabeled data.

17. The system of claim 16, wherein the self-labeling module is configured to iteratively add the self-labeled data to the labeled data and generate further self-labeled data until a predetermined termination condition is satisfied.

18. The system of claim 16, wherein the clustering module is configured to re-generate the self-organizing map based on the labeled data, the unlabeled data and the self-labeled data.

19. The system of claim 14, wherein the classifier is configured to auto-complete a data field or a user selection based on the labeled and self-labeled data.

20. The system of claim 15, wherein the self-labeling module is further configured to assign a class to the self-labeled data based on the labeled data in the same neighborhood.

21. The system of claim 15, wherein the self-labeling module is further configured to label unlabeled data associated with each of a plurality of nodes in the self-organizing map with a label of labeled data associated with the respective node.

22. The system of claim 21, wherein the self-labeling module is further configured, for each neighborhood around a node associated with labeled data to, determine whether data associated with nodes within a predetermined neighborhood depth have different labels and, if not, to label all unlabeled data associated with nodes in the respective neighborhood with the label of the labeled data in that neighborhood.

23. The system of claim 22, wherein the predetermined neighborhood depth is two.

24. The system of claim 22, wherein the self-labeling module is further configured, where nodes within a same neighborhood are determined to be associated with different labeled data, to label unlabeled data associated with nodes in the same neighborhood that are adjacent only one node associated with labeled data so that the unlabeled data is assigned the label of the labeled data associated with the one adjacent node.

25. Computer readable storage storing computer program instructions which, when executed by at least one processor, cause the at least one processor to perform the method comprising:

obtaining data, the data comprising labeled data and unlabeled data;

generating a self-organizing map of the data; and

labeling at least some of the unlabeled data based on proximity of the unlabeled data to labeled data within the self-organizing map to generate self-labeled data.

26. The computer readable storage of claim 25, wherein the method further comprises training a classifier based on the labeled and self-labeled data.