Chapter|Chapter 2 - Classifying with k-Nearest Neighbors Chapter2-Classifyingwithk-NearestNei

Classifying with distance measurements

k-Nearest Neighbors

Pros: High accuracy, insensitive to outliers, no assumptions about data

Cons: Computationally expensive, requires a lot of memory

Works with: Numeric values, nominal values

The first machine-learning algorithm is k-Nearest Neighbors (kNN). When given a new piece of data, we compare the new piece of data with our training set. We look at the k most similar pieces of data and take a majority vote from the k pieces of data, and the majority is the new class we assign to the data we were asked to classify.
Prepare: importing data with Python

Create a Python module: kNN.py

from numpy import * import operatordef createDataSet(): group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]]) labels = ['A', 'A', 'B', 'B'] return group, labels

Putting the kNN classification algorithm into action

Function classify0()

def classify0(inX, dataSet, labels, k): dataSetSize = dataSet.shape[0] diffMat = tile(inX, (dataSetSize, 1)) - dataSet sqDiffMat = diffMat ** 2 sqDistances = sqDiffMat.sum(axis = 1) distances = sqDistances ** 0.5 sortedDistIndicies = distances.argsort() classCount = {} for i in range(k): voteIlabel = labels[sortedDistIndicies[i]] classCount[voteIlable] = classCount.get(voteIlable, 0) + 1 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0]

How to test a classifier
Calculate error rate using test set.
Example: improving matches from a dating site with kNN Prepare: parsing data from a text file

Function file2matrix()

def file2matrix(filename): fr = open(filename) numberOfLines = len(fr.readlines()) returnMat = zeros((numberOfLines, 3)) classLabelVector = [] fr = open(filename) index = 0 labels = {'didntLike': 1, 'smallDoses': 2, 'largeDoses': 3} for line in fr.readlines(): line = line.strip() listFromLine = line.split('\t') returnMat[index, :] = listFromLine[0:3] # value is converted to integer in the book, it doesn't work on my system classLabelVector.append(labels[listFromLine[-1]]) index += 1 return returnMat, classLabelVector

Analyze: creating scatter plot with Matplotlib

Plot the data in Python console

>>> import matplotlib >>> import matplotlib.pyplot as plt >>> fig = plt.figure() >>> ax = fig.add_subplot(111) >>> ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2]) >>> plt.show()
Customize the markers

ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0*array(datingLabels), 15.0*array(datingLabels))

Chapter|Chapter 2 - Classifying with k-Nearest Neighbors

文章图片
Visualizing Data Prepare: normalizing numeric values
When dealing with values that lie in different ranges, it's common to normalize them. Common ranges to normalize them to are 0 to 1 or -1 to 1.

Function autoNorm()

def autoNorm(dataSet): minVals = dataSet.min(0) maxVals = dataSet.max(0) ranges = maxVals - minVals normDataSet = zeros(shape(dataSet)) m = dataSet.shape[0] normDataSet = dataSet - tile(minVals, (m, 1)) normDataSet = normDataSet/tile(ranges, (m, 1)) # element-wise division return normDataSet, ranges, minVals

In Numpy, / operator stands for element-wise division. You need to use linalg.solve(matA, matB) for matrix division.

Test: testing the classifier as a whole program
To test the accuracy of the algorithm, we take 90% of the existing data to train the classifier. Then we take the remaining 10% to test the classifier and see how accurate it is. The 10% should be randomly selected. Our data isn't stored in a specific sequence, so you can take the first 10%.

Function datingClassTest()

def datingClassTest(): hoRatio = 0.10 datingDataMat, datingLabels = file2matrix('datingTestSet.txt') normMat, ranges, minVals = autoNorm(datingDataMat) m = normMat.shape[0] numTestVecs = int(m*hoRatio) errorCount = 0.0 for i in range(numTestVecs): classifierResult = classify0(normMat[i, :], normMat[numTestVecs: m, :], datingLabels[numTestVecs: m], 3) print('The classifier came back with: {:d}, the real answer is: {:d}'.format(classifierResult, datingLabels[i])) if classifierResult != datingLabels[i]: errorCount += 1.0 print("The total error rate is: {:f}".format(errorCount / float(numTestVecs)))
Sample output

>>> kNN.datingClassTest() The classifier came back with: 3, the real answer is: 3 The classifier came back with: 2, the real answer is: 2 The classifier came back with: 1, the real answer is: 1 The classifier came back with: 1, the real answer is: 1 The classifier came back with: 1, the real answer is: 1 ... The classifier came back with: 2, the real answer is: 2 The classifier came back with: 3, the real answer is: 3 The classifier came back with: 2, the real answer is: 2 The classifier came back with: 1, the real answer is: 1 The classifier came back with: 3, the real answer is: 3 The total error rate is: 0.050000

Use: putting together a useful system
Now that we've tested the classifier on our data, it's time to use it to actually classify people for Hellen. Hellen will find someone on the dating site and enter his information. The program predicts how much she'll like this person.

Function classifyPerson()

def classifyPerson(): resultList = ['not at all', 'in small doses', 'in large doses'] percentTats = float(input('percentage of time spent playing video games?')) ffMiles = float(input('frequent flier miles earned per year?')) iceCream = float(input('liters of ice cream consumed per year?')) datingDataMat, datingLabels = file2matrix('datingTestSet.txt') normMat, ranges, minVals = autoNorm(datingDataMat) inArr = array([ffMiles, percentTats, iceCream]) classifierResult = classify0((inArr-minVals)/ranges, normMat, datingLabels, 3) print("You will probably like this person: ", resultList[classifierResult - 1])

Example: a handwriting recognition system Prepare: converting images into test vectors
【Chapter|Chapter 2 - Classifying with k-Nearest Neighbors】We'll take the 32x32 matrix that is each binary image and make it a 1x1024 vector. After this, we can apply it to the existing classifier.

Function img2vector()

def img2vector(filename): returnVect = zeros((1, 1024)) fr = open(filename) for i in range(32): lineStr = fr.readline() for j in range(32): returnVect[0, 32*i+j] = int(lineStr[j]) return returnVect

Test: kNN on handwriting digits

Function handwritingClassTest()

def handwritingClassTest(): hwLabels = [] trainingFileList = listdir('trainingDigits') m = len(trainingFileList) trainingMat = zeros((m, 1024)) for i in range(m): fileNameStr = trainingFileList[i] fileStr = fileNameStr.split('.')[0] classNumStr = int(fileStr.split('_')[0]) hwLabels.append(classNumStr) trainingMat[i, :] = img2vector('trainingDigits/{:s}'.format(fileNameStr)) testFileList = listdir('testDigits') errorCount = 0 mTest = len(testFileList) for i in range(mTest): fileNameStr = testFileList[i] fileStr = fileNameStr.split('.')[0] classNumStr = int(fileStr.split('_')[0]) vectorUnderTest = img2vector('testDigits/{:s}'.format(fileNameStr)) classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) print("The classifier came back with: {:d}, the real answer is: {:d}".format(classifierResult, classNumStr)) if classifierResult != classNumStr: errorCount += 1 print("\nThe total number of errors is: {:d}".format(errorCount)) print("\nThe total error rate is: {:f}".format(errorCount/float(mTest)))
Sample output

>>> kNN.handwritingClassTest() The classifier came back with: 4, the real answer is: 4 The classifier came back with: 4, the real answer is: 4 The classifier came back with: 3, the real answer is: 3 The classifier came back with: 9, the real answer is: 9 The classifier came back with: 0, the real answer is: 0 .. The classifier came back with: 1, the real answer is: 1 The classifier came back with: 5, the real answer is: 5 The classifier came back with: 4, the real answer is: 4 The classifier came back with: 3, the real answer is: 3 The classifier came back with: 3, the real answer is: 3The total number of errors is: 11The total error rate is: 0.011628

So many calculations make this algorithm pretty slow. This is a modification to kNN, called kD-trees, that allow us to reduce the number of calculations.
Summary The k-Nearest Neighbors algorithm is a simple and effective way to classify data. kNN is an example of instance-based learning, where you need to have instances of data close at hand to perform the machine learning algorithm. In addition, you need to calculate the distance measurement for every piece of data in the database, and this can be cumbersome.
And additional drawback is that kNN doesn't give you any idea of the underlying structure of the data; you have no idea what an "average" or "examplar" instance from each class looks like. In the next chapter, we'll address this issue by exploring ways in which probability measurements can help you do classification.