mariuszprzydatek.com

k-Nearest Neighbors (kNN) is an easy to grasp algorithm (and quite effective one), which:

• finds a group of k objects in the training set that are closest to the test object, and
• bases the assignment of a label on the predominance of a particular class in this neighborhood.

There are three key elements of this approach:

• a set of labeled objects, e.g., a set of stored records (data),
• a distance or similarity metric to compute distance between objects,
• and the value of k, the number of nearest neighbors.

To classify an unlabeled object/item:

• the distance of this object to the labeled objects is computed,
• its k-nearest neighbors are identified,
• and the class labels of these nearest neighbors are then used to determine the class label of the object.

Figure below provides a high-level summary of the nearest-neighbor classification algorithm.

Distances are calculated using the Euclidian distance, where the distance between two vectors, xA and xB, with two elements, is given by:

k-Nearest Neighbors Pros vs. Cons:

• Pros – High accuracy, insensitive to outliers, no assumptions about data
• Cons – Computationally expensive, requires a lot of memory
• Works with – Numeric values, nominal values

Prior to starting coding, here’s what we assume we have: (details in Peter Harrington’s exceptional “Machine Learning in Action”)

• We have the training data (an existing set of example data)
• We have labels for all of this data
• We know what class each piece of the data should fall into
• When we’re given a new piece of data without a label, we compare that new piece of data to the existing data (every piece of existing data)
• We then take the most similar pieces of data (the nearest neighbors) and look at their labels
• We look at the top k most similar pieces of data from our known dataset; this is where the k comes from
• Lastly, we take a majority vote from the k most similar pieces of data, and the majority is the new class we assign to the data we were asked to classify

I’ll be using Python (v3.3.5) programming language for code examples:

1. Create a text file named “test_data.txt” that will contain our test data set (x,y coordinates/pairs of points in a 2D space together with labels (3rd column))

       0.2    1.3    top-left
       0.1    1.1    top-left
       0.9    0.1    bottom-right
       1.0    0.2    bottom-right
   

2. Create a new python file called knn_example.py
3. Import NumPy (package for scientific computing) and the Operator module (sorting tuples). NumPy requires previous installation from here.

       from numpy import *
       import operator
   

4. Add a function to prepare the data set (load it from the file and transform into data(matrix) and labels(vector) components)

       def prepareData(fname):
           file = open(fname)
           lines = len(file.readlines())
           data = zeros((lines,2))
           labels = []
           file = open(fname)
           i = 0
           for line in file.readlines():
               line = line.strip()
               list = line.split('\t')
               data[i,:] = list[0:2]
               labels.append(list[-1])
               i += 1
           return data,labels
   

5. Add a function to classify the data

       def classify(x, data, labels, k):
           size = data.shape[0]
           diff = tile(x, (size,1)) - data
           sqDiff = diff**2
           sqDist = sqDiff.sum(axis=1)
           dist = sqDist**0.5
           sortedDist = dist.argsort()
           count={}
           for i in range(k):
               label = labels[sortedDist[i]]
               count[label] = count.get(label,0) + 1
           sCount = sorted(count.items(), key=operator.itemgetter(1), reverse=True)
           return sCount[0][0]
   

6. Save the file
7. Execute (from Python CLI or IDLE):

       >>> import knn_example
       >>> group,labels = knn_example.prepareData('test_data.txt')
       >>> knn_example.classify([1,0], group, labels, 2)
   

What you should see after executing the above, is following:

    'bottom-right'

Voila, you just created your first classifier (which successfully classified a point with x,y coordinates of 1,0 by assigning it the ‘bottom-right’ label)

Resources:

• Top 10 algorithms in data mining; SURVEY PAPER (http://www.cs.uvm.edu/~icdm/algorithms/10Algorithms-08.pdf)
• Machine Learning in Action; Peter Harrington (http://www.manning.com/pharrington/)
• NumPy scientific computing with Python (http://www.numpy.org/)

Some time ago while reading the journal of Knowledge and Information Systems (KAIS; vol. Dec24, 2007) i came across a paper titled “Top 10 Algorithms in Data Mining”.

This paper was presented at the IEEE International Conference on Data Mining (ICDM; 2006 Hong Kong), and a companion book was published in 2009; edited by the authors of the mentioned paper (Xindong Wu, Vipin Kumar et al).

It was “the paper” that attracted me to the field of Machine Learning, and with this post i’m starting a series of articles related to this exciting area 🙂

Below you’ll find my rough notes (which you still may find useful) as well as my descriptions of some of the Top 10 Algorithms presented in the aforementioned paper.

Basics:

• Machine Learning – “making sense of the data”
• Supervised learning – we specify a target variable and the machine learns from our data (by identifying patterns) to eventually get the target variable. (“You know what you are looking for”)
  • Sample tasks:
    • Classification – predicting what class an instance of data should fall into
    • Regression – prediction of a numeric value
• Unsupervised learning – in case of which you don’t know what you’re looking for, and ask the machine to tell you this instead. (“what do these data have in common?”)
  • Sample tasks:
    • Clustering – grouping similar items together
    • Density Estimation – finding statistical values that describe the data

Examples of supervised learning algorithms:

• k-Nearest Neighbors (kNN) – uses a distance metric to classify items
• Decision Trees – map observations about an item to conclusions about the item’s target value
• Naïve Bayes – uses probability distributions for classification
• Logistic Regression – finds best parameters to properly classify data
• Support Vector Machines – construct a hyperplane or set of hyperplanes in a high- or infinite-dimensional space
• AdaBoost – is made up of a collection of classifiers (a meta-algorithm)

Examples of unsupervised learning algorithms:

• k-Means clustering
• Apriori algorithm
• FP-Growth

Classification:

• In classification, the target variable (“class”) can take:
  • nominal values (true, false, car, plane, human, animal, etc.)
  • infinite number of numeric values (in this case we’re talking about regression)
• Classification Imbalance – a real-world problem where you have more data from one class than other classes

Overview of the classification algorithms based on their design (Haralambos Marmanis)

Steps in developing a machine learning application:

• Data collection – using publicly available sources, API’s, RSS feeds, sensors, etc.
• Input data preparation – algorithm-specific data formatting
• Input data Analysis – it’s important to “understand the data”
• Algorithm training – extraction of knowledge or information (this step does not apply to unsupervised learning)
• Algorithm testing – putting to use information learned in the previous step (evaluating the algorithm)
• Algorithm usage – solving a problem

Take care.

Resources:

• Knowledge and Information Systems, An International Journal (http://www.cs.uvm.edu/~kais/)
• Top 10 algorithms in data mining; SURVEY PAPER (http://www.cs.uvm.edu/~icdm/algorithms/10Algorithms-08.pdf)
• “The Top Ten Algorithms in Data Mining”, Companion Book (http://www.crcpress.com/product/isbn/9781420089646)
• Top 10 Algorithms in Data Mining (http://www.cs.uvm.edu/~icdm/algorithms/index.shtml)
• Statistical classification (http://en.wikipedia.org/wiki/Classification_(machine_learning))
• Regression analysis (http://en.wikipedia.org/wiki/Regression_analysis)
• Cluster analysis (http://en.wikipedia.org/wiki/Cluster_analysis)
• Density estimation (http://en.wikipedia.org/wiki/Density_estimation)