-1

I'm looking for implementation for K-Nearest Neighbor algorithm in Java for unstructured data. I found many implementation for numeric data, however how I can implement it and calculate the Euclidean Distance for text (Strings).

Here is one example for double:

public static double EuclideanDistance(double [] X, double []Y)
{
    int count = 0;
    double distance = 0.0;
    double sum = 0.0;
    if(X.length != Y.length)
    {
        try {
            throw new Exception("the number of elements" + 
                      " in X must match the number of elements in Y");
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
    else
    {
        count = X.length;
    }
    for (int i = 0; i < count; i++)
    {
        sum = sum + Math.pow(Math.abs(X[i] - Y[i]),2);
    }
    distance = Math.sqrt(sum);
    return distance;
}

How I can implement it for Strings (unstructured data)? For example,

Class 1: 
"It was amazing. I loved it"
"It is perfect movie"

Class 2:
"Boring. Boring. Boring."
"I do not like it"

How can we implement KNN on such type of data and calculate Euclidean Distance?

desertnaut
  • 57,590
  • 26
  • 140
  • 166
F. Fo
  • 123
  • 6
  • 18
  • What is your definition of "distance" when it comes to strings? Is it character by character? – ostrichofevil Feb 09 '16 at 00:16
  • no, it is word by word. – F. Fo Feb 09 '16 at 00:17
  • I can't really answer this if I don't know what you want to do. What are the dimensions of your data? How do you want to convert the Strings into numerical values? – ostrichofevil Feb 09 '16 at 00:20
  • 1
    you have to assign numerical value to it! "boring" 0.9, "dont like it": 0.8......its a long long way because then you will ask "but how will assign numerical value to it?" and goes on and on .................. – gpasch Feb 09 '16 at 00:20
  • when we apply the ML algorithm for text, each word become a dimension. So, here the dimension is each word in the training set. – F. Fo Feb 09 '16 at 00:31
  • Using one dimension for each word in the training set means that you don't care about order or frequency of words, is that correct? – TilmannZ Feb 09 '16 at 08:35
  • yes the order and frequency does not matter. We only care about the occurrence of the words in a string – F. Fo Feb 09 '16 at 23:57

1 Answers1

0

You correctly noticed that the only thing you have to do is to define the notion of distance between your strings. The problem is that it is task dependent. It can be anything from let's assign the distance to 1 if both strings have a world 'data' in it and 0 otherwise to something more complex like Okapi BM25.

Take a look at various string metrics or may be python implementation of tf-idf.

Community
  • 1
  • 1
Salvador Dali
  • 214,103
  • 147
  • 703
  • 753