Data classifier using proximity graphs, edge weights, and propagation labels

1. A data classifier device, comprising:

a data storage; and

at least one processor configured to predict classification labels for test data by:

determining a relationship between the test data and training data, the training data having associated training classification labels, the determining comprising generating a proximity graph in which test data and training data members are represented by nodes of the proximity graph;

assigning initial edge weights to the edges between the nodes in the proximity graph that correspond to a similarity between the nodes;

performing a first propagation of labels from training data nodes in the proximity graph to test data nodes in the proximity graph based on the initial edge weights;

modifying the initial edge weights based on the first propagation of labels;

performing a second propagation of labels from training data nodes in the proximity graph to test data nodes in the proximity graph based on the modified edge weights; and

adding, after the second propagation of labels, a member of the test data that is part of the proximity graph and its associated label to the training data based on the associated label.

2. The device of claim 1 , wherein the processor:

sorts a plurality of the labels of the test data nodes from the second propagation to identify one of the labels that satisfies a preselected criterion; and

selects the test data member having the identified label as the data member to add to the training data.

3. The device of claim 2 , wherein the preselected criterion corresponds to a label having a minimum magnitude of the labels from the second propagation.

4. The device of claim 1 , wherein the processor is configured to, if some of the test data nodes have a 0-value label:

determine a sum of weights between the nodes having the 0-value labels and corresponding graph neighbors, respectively,

determine which of the determined sums is larger than the other determined sums, and

select the test data member corresponding to the node having the sum that is larger than the other determined sums as the data member to add to the training data.

5. A method of classifying data, comprising:

using at least one processor for predicting classification labels for test data by:

determining a relationship between the test data and training data that has associated training classification labels, the determining comprising generating a proximity graph in which test data and training data members are represented by nodes of the proximity graph;

assigning initial edge weights to the edges between the nodes in the proximity graph that correspond to a similarity between the nodes;

performing a first propagation of labels from training data nodes in the proximity graph test data nodes in the proximity graph based on the initial edge weights;

modifying the initial edge weights based on the first propagation of labels;

performing a second propagation of labels from training data nodes in the proximity graph to test data nodes in the proximity graph based on the modified edge weights; and

adding, after the second propagation of labels, a member of the test data that is part of the proximity graph and its associated label, to the training data based on the associated label.

6. The method of claim 5 , comprising

sorting a plurality of the labels of the test data nodes from the second propagation to identify one of the labels that satisfies a preselected criterion; and

selecting the test data member having the identified label as the data member to add to the training data.

7. The method of claim 6 , wherein the preselected criterion corresponds to a label having a minimum magnitude of the labels from the second propagation.

8. The method of claim 7 , comprising, if some of the test data nodes have 0-value predicted labels;

determining a sum of weights between the nodes having the 0-value labels and corresponding graph neighbors, respectively,

determining which of the determined sums is larger than the other determined sums, and

selecting the test data member having the sum that is larger than the other determined sums as the data member to add to the training data.

9. The device of claim 1 , wherein if any of the training data nodes have a 0-value label, said adding a member of the test data that is part of the proximity graph and its associated label to the training data is further based on and the modified weights.

10. The device of claim 1 , wherein the processor assigns the initial edge weights between two nodes based on the following equation:

w

i

⁢

⁢

j

=

e

-



X

i

-

X

j



2

σ

1

where:

w ij is an edge weight;

Xi and Xj are data points corresponding to two nodes in the proximity graph that a given edge is between; and

σ 1 is a user defined parameter.

11. The device of claim 10 , the processor modifies the initial edge weights based on the following equation:

w

i

⁢

⁢

j

=

e

-



X

i

-

X

j



2

σ

1

⨯

e

-



v

i

-

v

j



σ

2

where:

v i and v j are labels for Xi and Xj, respectively, resulting from the first propagation of labels; and

σ 2 is a user defined parameter.

12. The method of claim 5 , wherein if any of the training data nodes have a 0-value label, said adding a member of the test data that is part of the proximity graph and its associated label to the training data is further based on and the modified weights.

13. The method of claim 5 , wherein said assigning initial edge weights is performed based on the following equation:

w

i

⁢

⁢

j

=

e

-



X

i

-

X

j



2

σ

1

where:

w ij is an edge weight;

Xi and Xj are data points corresponding to two nodes in the proximity graph that a given edge is between; and

σ 1 is a user defined parameter.

14. The method of claim 13 , wherein said modifying the initial edge weights based on the propagated labels is performed using the following equation:

w

i

⁢

⁢

j

=

e

-



X

i

-

X

j



2

σ

1

⨯

e

-



v

i

-

v

j



σ

2

where:

v i and v j are labels for Xi and Xj, respectively, resulting from the first propagation of labels; and

σ 2 is a user defined parameter.