k-means

Posted on   |   In

Project Address:

https://github.com/TheOneAC/ML.git

dataset in ML/ML_ation/knn

K近邻算法

  • 优点：精度高、异常不敏感、无数据输入假定
  • 缺点：计算复杂度高、空间复杂度高
  • 适用数据：数值型、标称型
  • 选择ｋ个最相似数据中次数出现最多的分类，作为新数据的分类

k-means 伪码

  • 计算当前点与已知分类点距离
  • 按距离递增排序，选取最近的前Ｋ个
  • 确定前ｋ个点所在类别的出现频率
  • 返回出现最高的频率最为当前点的分类返回

python code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def classify0(inX, dataSet,labels, k):
	dataSetSize = dataSet.shape[0]
	#print(dataSetSize)
	diffMat = tile(inX, (dataSetSize,1)) - dataSet
	#print(diffMat)
	sqDiffMat = diffMat ** 2
	sqDistance = sqDiffMat.sum(axis = 1)
	#print(sqDistance)
	distance = sqDistance ** 0.5
	sortedDistanceIndices = distance.argsort()
	#print (sortedDistanceIndices)
	classCount = {}
	for i  in range(k):
		voteIlabel = labels[sortedDistanceIndices[i]]
		classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
	sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1),
	reverse = True)
	#print(sortedClassCount)
	return sortedClassCount[0][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #get the number of lines in the file
    returnMat = zeros((numberOfLines,3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return   
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector

使用第二列和第三列数据形成散点图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import knn
group, labels = knn.creatdataset()
#print( knn.classify0([0,0],group,labels, 3) )
datingDatMat, datinglabels = knn.file2matrix('datingTestSet2.txt')
import matplotlib
import matplotlib.pyplot as plt 
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDatMat[:,1], datingDatMat[:,2])
plt.show()

./test.py

图片标题

修改，加入颜色

1
2
3
#ax.scatter(datingDatMat[:,1], datingDatMat[:,2])
->>>>> 
ax.scatter(datingDatMat[:,1], datingDatMat[:,2],15.0 *array(datinglabels), 15.0 *array(datinglabels))

图片标题

修改坐标参考，改为使用第一列和第二列数据

1
2
3
#ax.scatter(datingDatMat[:,1], datingDatMat[:,2],15.0 *array(datinglabels), 15.0 *array(datinglabels))
->>>>>>>
ax.scatter(datingDatMat[:,0], datingDatMat[:,1],15.0 *array(datinglabels), 15.0 *array(datinglabels))

图片标题

数值归一化

newValue = (oldValue - min)/(max - min)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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))
	return normDataSet,ranges, minVals
def datingClassTest():
	hoRatio = 0.05
	datingDatMat, datinglabels = file2matrix('datingTestSet2.txt')
	normSet,ranges, minVals = autoNorm(datingDatMat)
	m = normSet.shape[0]
	numTestVecs = int(m* hoRatio)
	errorCount = 0
	for i in range(numTestVecs):
		classifierResult = classify0(normSet[i,:],normSet[numTestVecs:m,:],datinglabels[numTestVecs:m],3)
		print "the classifier came back with: %d , the real answer is: %d" % (classifierResult, datinglabels[i])
		if(classifierResult != datinglabels[i]): errorCount += 1.0
	print "the total error rate is %f " % (errorCount/float(numTestVecs))

knn.datingClassTest()

图片标题

手写字符识别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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
from os import listdir 
def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')           #load the training set
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
    testFileList = listdir('testDigits')        #iterate through the test set
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr)
        if (classifierResult != classNumStr): errorCount += 1.0
    print "\nthe total number of errors is: %d" % errorCount
    print "\nthe total error rate is: %f" % (errorCount/float(mTest))

./test.py

1
2
3
4
#!/usr/bin/python
from numpy import *
import operator
knn.handwritingClassTest()

图片标题