{"id":241,"date":"2017-01-19T20:45:21","date_gmt":"2017-01-19T12:45:21","guid":{"rendered":"http:\/\/www.mrtblog.cn\/?p=241"},"modified":"2023-03-05T14:41:05","modified_gmt":"2023-03-05T06:41:05","slug":"k-%e8%bf%91%e9%82%bbknn%e7%ae%97%e6%b3%95%e5%8f%8a%e5%ae%9e%e8%b7%b5","status":"publish","type":"post","link":"http:\/\/www.mrtblog.cn\/?p=241","title":{"rendered":"K-\u8fd1\u90bb(KNN)\u7b97\u6cd5\u53ca\u5b9e\u8df5"},"content":{"rendered":"
<\/span> 1,444<\/span> Views<\/span><\/div>

\u53c2\u8003\u4e66\u7c4d\u300a\u673a\u5668\u5b66\u4e60\u5b9e\u6218\u300b<\/em><\/p>\n

K-\u8fd1\u90bb\u7b97\u6cd5\u6982\u8ff0<\/h3>\n

\u7b80\u5355\u6765\u8bf4\uff0ck\u8fd1\u90bb\u7b97\u6cd5\u91c7\u7528\u6d4b\u91cf\u4e0d\u540c\u7279\u5f81\u503c\u4e4b\u95f4\u7684\u8ddd\u79bb\u65b9\u6cd5\u8fdb\u884c\u5206\u7c7b<\/p>\n

k-\u8fd1\u90bb\u7b97\u6cd5<\/strong>
\n\u4f18\u70b9\uff1a\u7cbe\u5ea6\u9ad8\uff0c\u5bf9\u5f02\u5e38\u503c\u4e0d\u654f\u611f\u3001\u65e0\u6570\u636e\u8f93\u5165\u5047\u5b9a
\n\u7f3a\u70b9\uff1a\u8ba1\u7b97\u590d\u6742\u5ea6\u9ad8\u3001\u7a7a\u95f4\u590d\u6742\u5ea6\u9ad8
\n\u9002\u7528\u6570\u636e\u8303\u56f4\uff1a\u6570\u636e\u578b\u548c\u6807\u79f0\u578b<\/p>\n

\u5de5\u4f5c\u539f\u7406\u662f\uff1a\u5b58\u5728\u4e00\u4e2a\u6837\u672c\u6570\u636e\u96c6\u5408\uff0c\u4e5f\u79f0\u4f5c\u8bad\u7ec3\u6837\u672c\u96c6\uff0c\u5e76\u4e14\u6837\u672c\u96c6\u4e2d\u6bcf\u4e2a\u6570\u636e\u90fd\u5b58\u5728\u6807\u7b7e\uff0c\u5373\u6211\u4eec\u77e5\u9053\u6837\u672c\u96c6\u4e2d\u6bcf\u4e00\u6570\u636e\u4e0e\u6240\u5c5e\u5206\u7c7b\u7684\u5bf9\u5e94\u5173\u7cfb\u3002\u8f93\u4eba\u6ca1\u6709\u6807\u7b7e\u7684\u65b0\u6570\u636e\u540e\uff0c\u5c06\u65b0\u6570\u636e\u7684\u6bcf\u4e2a\u7279\u5f81\u4e0e\u6837\u672c\u96c6\u4e2d\u6570\u636e\u5bf9\u5e94\u7684\u7279\u5f81\u8fdb\u884c\u6bd4\u8f83\uff0c\u7136\u540e\u7b97\u6cd5\u63d0\u53d6\u6837\u672c\u96c6\u4e2d\u7279\u5f81\u6700\u76f8\u4f3c\u6570\u636e\uff08\u6700\u8fd1\u90bb\uff09\u7684\u5206\u7c7b\u6807\u7b7e\u3002\u4e00\u822c\u6765\u8bf4\uff0c\u6211\u4eec\u53ea\u9009\u62e9\u6837\u672c\u6570\u636e\u96c6\u4e2d\u524dk\u4e2a\u6700\u76f8\u4f3c\u7684\u6570\u636e\uff0c\u8fd9\u5c31\u662fk-\u8fd1\u90bb\u7b97\u6cd5\u4e2dk\u7684\u51fa\u5904\uff0c\u901a\u5e38k\u662f\u4e0d\u5927\u4e8e20\u7684\u6574\u6570\u3002\u6700\u540e\uff0c\u9009\u62e9k\u4e2a\u6700\u76f8\u4f3c\u6570\u636e\u4e2d\u51fa\u73b0\u6b21\u6570\u6700\u591a\u7684\u5206\u7c7b\uff0c\u4f5c\u4e3a\u65b0\u6570\u636e\u7684\u5206\u7c7b\u3002<\/p>\n

\u4ee5\u7535\u5f71\u5206\u7c7b\u4e3a\u4f8b\uff0c\u7edf\u8ba1\u7535\u5f71\u6253\u6597\u955c\u5934\u6570\u548c\u63a5\u543b\u955c\u5934\u6570\u4ee5\u53ca\u7535\u5f71\u8bc4\u4f30\u7c7b\u578b\u5982\u88682-1\uff1a
\n\"\"<\/a><\/p>\n

\u5373\u4f7f\u4e0d\u77e5\u9053\u672a\u77e5\u7535\u5f71\u5c5e\u4e8e\u54ea\u79cd\u7c7b\u578b\uff0c\u6211\u4eec\u4e5f\u53ef\u4ee5\u901a\u8fc7\u67d0\u79cd\u65b9\u6cd5\u8ba1\u7b97\u51fa\u6765\u3002\u9996\u5148\u8ba1\u7b97\u672a\u77e5\u7535\u5f71\u4e0e\u6837\u672c\u96c6\u4e2d\u5176\u4ed6\u7535\u5f71\u7684\u8ddd\u79bb\uff0c\u5982\u88682-2\u6240\u793a\u3002\u6b64\u5904\u6682\u65f6\u4e0d\u8981\u5173\u5fc3\u5982\u4f55\u8ba1\u7b97\u5f97\u5230\u8fd9\u4e9b\u8ddd\u79bb\u503c\uff0c\u4f7f\u7528Python\u5b9e\u73b0\u7535\u5f71\u5206\u7c7b\u5e94\u7528\u65f6\uff0c\u4f1a\u63d0\u4f9b\u5177\u4f53\u7684\u8ba1\u7b97\u65b9\u6cd5
\n\"\"<\/a><\/p>\n

\u73b0\u5728\u6211\u4eec\u5f97\u5230\u4e86\u6837\u672c\u96c6\u4e2d\u6240\u6709\u7535\u5f71\u4e0e\u672a\u77e5\u7535\u5f71\u7684\u8ddd\u79bb\uff0c\u6309\u7167\u8ddd\u79bb\u9012\u589e\u6392\u5e8f\uff0c\u53ef\u4ee5\u627e\u5230k\u4e2a\u8ddd\u79bb\u6700\u8fd1\u7684\u7535\u5f71\u3002\u5047\u5b9ak=3\uff0c\u5219\u4e09\u4e2a\u6700\u9760\u8fd1\u7684\u7535\u5f71\u4f9d\u6b21\u662fHe’s Not Really into Dudes\u3001Beautiful Woman\u548cCalifornia Man\u3002k-\u8fd1\u90bb\u7b97\u6cd5\u6309\u7167\u8ddd\u79bb\u6700\u8fd1\u7684\u4e09\u90e8\u7535\u5f71\u7684\u7c7b\u578b\uff0c\u51b3\u5b9a\u672a\u77e5\u7535\u5f71\u7684\u7c7b\u578b\uff0c\u800c\u8fd9\u4e09\u90e8\u7535\u5f71\u5168\u662f\u7231\u60c5\u7247\uff0c\u56e0\u6b64\u6211\u4eec\u5224\u5b9a\u672a\u77e5\u7535\u5f71\u662f\u7231\u60c5\u7247\u3002<\/p>\n

k-\u8fd1\u90bb\u7b97\u6cd5\u7684\u4e00\u822c\u6d41\u7a0b <\/strong>
\n(1)\u6536\u96c6\u6570\u636e\uff1a\u53ef\u4ee5\u4f7f\u7528\u4efb\u4f55\u65b9\u6cd5\u3002
\n(2)\u51c6\u5907\u6570\u636e\uff1a\u8ddd\u79bb\u8ba1\u7b97\u6240\u9700\u8981\u7684\u6570\u503c\uff0c\u6700\u597d\u662f\u7ed3\u6784\u5316\u7684\u6570\u636e\u683c\u5f0f\u3002
\n(3)\u5206\u6790\u6570\u636e\uff1a\u53ef\u4ee5\u4f7f\u7528\u4efb\u4f55\u65b9\u6cd5\u3002
\n(4)\u8bad\u7ec3\u7b97\u6cd5\uff1a\u6b64\u6b65\u9a5f\u4e0d\u9002\u7528\u4e8ek-\u8fd1\u90bb\u7b97\u6cd5\u3002
\n(5)\u6d4b\u8bd5\u7b97\u6cd5\uff1a\u8ba1\u7b97\u9519\u8bef\u7387\u3002
\n(6)\u4f7f\u7528\u7b97\u6cd5\uff1a\u9996\u5148\u9700\u8981\u8f93\u5165\u6837\u672c\u6570\u636e\u548c\u7ed3\u6784\u5316\u7684\u8f93\u51fa\u7ed3\u679c\uff0c\u7136\u540e\u8fd0\u884ck-\u8fd1\u90bb\u7b97\u6cd5\u5224\u5b9a\u8f93\u5165\u6570\u636e\u5206\u522b\u5c5e\u4e8e\u54ea\u4e2a\u5206\u7c7b\uff0c\u6700\u540e\u5e94\u7528\u5bf9\u8ba1\u7b97\u51fa\u7684\u5206\u7c7b\u6267\u884c\u540e\u7eed\u7684\u5904\u7406\u3002<\/p>\n

\u4f7f\u7528Python\u5b9e\u73b0KNN\u7b97\u6cd5<\/h4>\n

\u521b\u5efa\u6587\u4ef6KNN.py\uff0c\u5b9a\u4e49\u521b\u5efa\u6570\u636e\u96c6\u51fd\u6570\uff1a<\/p>\n

\nfrom numpy import *\nimport operator\n# \u8bad\u7ec3\u6570\u636e\u4ee5\u53ca\u5bf9\u5e94\u7684\u7c7b\u522b\ndef createDataSet():\n    group = array([[1.0,1.1],[1.0,1.0],[0.0,0.0],[0.0,0.1]])\n    labels = ['A','A','B','B']\n    return group,labels\n<\/code><\/pre>\n
\u5b9a\u4e49KNN\u5206\u7c7b\u51fd\u6570\uff1a<\/p>\n
\n#KNN\u5206\u7c7b\u7b97\u6cd5\ndef classify0(inX,dataSet,label,k):\ndataSize = dataSet.shape[0] #\u6570\u636e\u96c6\u7684\u6837\u672c\u6570\u91cf\n###\u8ba1\u7b97\u6b27\u5f0f\u8ddd\u79bb\ndiffMat = tile(inX,(dataSize,1)) - dataSet#\u6bcf\u4e2a\u8bad\u7ec3\u6837\u672c\u4e0e\u6d4b\u8bd5\u6837\u672c\u5750\u6807\u76f8\u51cf\nsqDiffMat = diffMat ** 2#\u76f8\u51cf\u7ed3\u679c\u6c42\u5e73\u65b9\nsquareDist = sum(sqDiffMat,axis = 1)#\u5e73\u65b9\u76f8\u52a0\ndist = squareDist ** 0.5#\u5bf9\u5e73\u65b9\u548c\u5f00\u6839\u53f7\n###\u5bf9\u8ddd\u79bb\u8fdb\u884c\u6392\u5e8f\nsortedDistIndex = argsort(dist)#argsort()\u6839\u636e\u5143\u7d20\u7684\u503c\u4ece\u5c0f\u5230\u5927\u5bf9\u5143\u7d20\u8fdb\u884c\u6392\u5e8f\uff0c\u8fd4\u56de\u4e0b\u6807\nclassCount = {}#\u7edf\u8ba1\u8fd1\u8ddd\u79bb\u7684\u8be5\u7c7b\u522b\u4e2a\u6570\n    for i in range(k):#\u7edf\u8ba1\u5404\u7c7b\u522b\u7684\u6b21\u6570\n        voteLabel = label[sortedDistIndex[i]]\n        classCount[voteLabel] = classCount.get(voteLabel,0) + 1\n        sortedClassCount = sorted(classCount.iteritems(),\n        key = operator.itergetter(1),reverse=True)\n        return sortedClassCount[0][0]#\u8fd4\u56de\u6807\u7b7e\n<\/code><\/pre>\n
inX\u4e3a\u8f93\u5165\u7684\u6d4b\u8bd5\u6570\u636e\uff0cdataSet\u4e3a\u8bad\u7ec3\u96c6\uff0clabel\u662f\u8bad\u7ec3\u96c6\u5bf9\u5e94\u7684\u6807\u7b7e\uff0ck\u8868\u793a\u90bb\u8fd1\u503c\u3002
\n\u6b27\u6c0f\u8ddd\u79bb\u5373\u4e24\u70b9\u95f4\u7684\u76f4\u7ebf\u8ddd\u79bb\uff0c\u4f8b\u5982\uff080,0\uff09\u4e0e\uff083,4\uff09\u8ddd\u79bb\u4e3asqrt(3^2+4^2)=5
\n\u4e4b\u540e\u4f7f\u7528<\/p>\n
\nKNN.classify0([0,0], group, labels, 3)\n<\/code><\/pre>\n
\u9a8c\u8bc1\u7ed3\u679c
\n\"\"<\/a><\/p>\n
\n
\u4e0a\u4e00\u6b21\u505a\u5230KNN\u7b80\u5355\u7684\u793a\u4f8b\uff0c\u8bad\u7ec3\u96c6\u53ea\u67094\u4e2a\u6570\u636e\u3002\u8fd9\u4e00\u6b21\u4f7f\u7528digits\u6570\u636e\u96c6\uff0c\u628a1600\u4e2a\u6570\u636e\u4f5c\u4e3a\u8bad\u7ec3\u96c6\u8f93\u5165\uff0c200\u4e2a\u6570\u636e\u4f5c\u4e3a\u6d4b\u8bd5\u96c6\u8f93\u5165\uff0c\u4f7f\u7528KNN\u9884\u6d4b\u5e76\u5c1d\u8bd5\u8c03\u6574k\u503c\u4f7f\u7ed3\u679c\u66f4\u7cbe\u786e\u3002\u5f97\u5230\u7684\u8bad\u7ec3\u7ed3\u679c\u5982\u4e0b\uff1a<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
K\u503c<\/strong><\/td>\n\u6b63\u786e\u6570<\/strong><\/td>\n\u9519\u8bef\u6570<\/strong><\/td>\n\u51c6\u786e\u7387<\/strong><\/td>\n<\/tr>\n
1<\/td>\n191<\/td>\n9<\/td>\n95.500000%<\/td>\n<\/tr>\n
2~3<\/td>\n190<\/td>\n10<\/td>\n95.000000%<\/td>\n<\/tr>\n
4<\/td>\n191<\/td>\n9<\/td>\n95.500000%<\/td>\n<\/tr>\n
5<\/td>\n189<\/td>\n11<\/td>\n94.500000%<\/td>\n<\/tr>\n
6<\/td>\n191<\/td>\n9<\/td>\n95.500000%<\/td>\n<\/tr>\n
7<\/td>\n188<\/td>\n12<\/td>\n94.000000%<\/td>\n<\/tr>\n
8<\/td>\n187<\/td>\n13<\/td>\n93.500000%<\/td>\n<\/tr>\n
9<\/td>\n186<\/td>\n14<\/td>\n93.000000%<\/td>\n<\/tr>\n
10<\/td>\n187<\/td>\n13<\/td>\n93.500000%<\/td>\n<\/tr>\n
11<\/td>\n186<\/td>\n14<\/td>\n93.000000%<\/td>\n<\/tr>\n
12<\/td>\n187<\/td>\n13<\/td>\n93.500000%<\/td>\n<\/tr>\n
13~16<\/td>\n186<\/td>\n14<\/td>\n93.000000%<\/td>\n<\/tr>\n
17~18<\/td>\n187<\/td>\n13<\/td>\n93.500000%<\/td>\n<\/tr>\n
19~20<\/td>\n186<\/td>\n14<\/td>\n93.000000%<\/td>\n<\/tr>\n
30<\/td>\n186<\/td>\n14<\/td>\n93.000000%<\/td>\n<\/tr>\n
50<\/td>\n183<\/td>\n17<\/td>\n91.500000%<\/td>\n<\/tr>\n
100<\/td>\n180<\/td>\n20<\/td>\n90.000000%<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
K\u53d6\u503c2~6\u65f6\uff0c\u51c6\u786e\u7387\u8fbe\u523095\u4ee5\u4e0a\uff0c\u8d85\u8fc720\u4ee5\u540e\u51c6\u786e\u7387\u660e\u663e\u4e0b\u964d\u3002\u7f51\u4e0a\u5bf9K\u53d6\u503c\u95ee\u9898\u8ba8\u8bba\u4e0d\u4e00\uff0c\u8fd9\u4e2a\u95ee\u9898\u7559\u7ed9\u4e4b\u540e\u6709\u5927\u6837\u672c\u8f93\u5165\u518d\u601d\u8003\u5427\u3002<\/p>\n
\u6d4b\u8bd5\u4ee3\u7801\uff1a
\nKNN.py<\/p>\n
\n#coding:utf-8\nfrom numpy import *\nimport operator\n\n\n#\u8bad\u7ec3\u6570\u636e\u4ee5\u53ca\u5bf9\u5e94\u7684\u7c7b\u522b\ndef createDataSet():\ngroup = array([[1.0,1.1],[1.0,1.0],[0.0,0.0],[0.0,0.1]])\nlabels = ['A','A','B','B']\nreturn group,labels\n<\/code>\n#KNN\u5206\u7c7b\u7b97\u6cd5\ndef classify0(inX,dataSet,label,k):\n    dataSize = dataSet.shape[0]#\u6570\u636e\u96c6\u7684\u6837\u672c\u6570\u91cf\n    result=[]#\u7ed3\u679clist\n    ###\u8ba1\u7b97\u6b27\u5f0f\u8ddd\u79bb\n    for ineachX in inX:#\u5bf9\u6bcf\u4e2a\u6d4b\u8bd5\u5143\u7d20\u8ba1\u7b97\n        diffMat = tile(ineachX,(dataSize,1)) - dataSet#\u6bcf\u4e2a\u8bad\u7ec3\u6837\u672c\u4e0e\u6d4b\u8bd5\u6837\u672c\u5750\u6807\u76f8\u51cf\n        sqDiffMat = diffMat ** 2#\u76f8\u51cf\u7ed3\u679c\u6c42\u5e73\u65b9\n        squareDist = sum(sqDiffMat,axis = 1)#\u5e73\u65b9\u76f8\u52a0\n        dist = squareDist ** 0.5#\u5bf9\u5e73\u65b9\u548c\u5f00\u6839\u53f7\n        ###\u5bf9\u8ddd\u79bb\u8fdb\u884c\u6392\u5e8f\n        sortedDistIndex = argsort(dist)#argsort()\u6839\u636e\u5143\u7d20\u7684\u503c\u4ece\u5c0f\u5230\u5927\u5bf9\u5143\u7d20\u8fdb\u884c\u6392\u5e8f\uff0c\u8fd4\u56de\u4e0b\u6807\n        classCount = {}#\u7edf\u8ba1\u8fd1\u8ddd\u79bb\u7684\u8be5\u7c7b\u522b\u4e2a\u6570\n        for i in range(k):#\u7edf\u8ba1\u5404\u7c7b\u522b\u7684\u6b21\u6570\n            voteLabel = label[sortedDistIndex[i]]\n            classCount[voteLabel] = classCount.get(voteLabel,0) + 1\n            sortedClassCount = sorted(classCount.iteritems(),\n            key = operator.itemgetter(1),reverse=True)\n            result.append(sortedClassCount[0][0])#\u8fd4\u56de\u6807\u7b7e\n    return result\n<\/code><\/pre>\n
testKNN.py<\/p>\n
\n#coding=utf-8\t\u542b\u6709\u4e2d\u6587\u5fc5\u987b\u89c4\u5b9a\u7f16\u7801\u683c\u5f0f\nimport KNN\nfrom sklearn import datasets\nimport numpy as np\ndef count(a1,a2,yes,no):#\u7edf\u8ba1\u6b63\u786e\u6570\u4e0e\u9519\u8bef\u6570\n    i = 0\n    while i < a1.size:\n        if a1[i] != a2[i]:\n            no += 1\n        else:\n            yse += 1\n        return yes,no\nif __name__ == "__main__":\n    digits = datasets.load_digits()#\u8bfb\u53d6digits\u6570\u636e\u96c6\n    n = 200#\u540en\u9879\u4e3a\u6d4b\u8bd5\u96c6\uff0c\u5176\u4ed6\u4e3a\u8bad\u7ec3\u96c6\n    test = digits.data[-n:]#\u6d4b\u8bd5\u96c6\n    train = digits.data[:-n]#\u8bad\u7ec3\u96c6\n    np.set_printoptions(threshold='nan')#\u5b8c\u5168\u6253\u5370\n    origin=digits.target[-n:]#\u6b63\u786e\u7ed3\u679c\n    predict = np.array(KNN.classify0(test, train, digits.target[:-n], 200))#\u9884\u6d4b\u7ed3\u679c\n    print "origin array:\\n%s"%(origin)\n    print "predict array:\\n%s"%(predict)\n    yes,no = 0,0\n    yes,no = count(origin,predict,yes,no)\n    rate = float(100 * yes) \/ float(yes + no)#\u6b63\u786e\u7387\n    print "\\nyes:%d no:%d \\naccuracy rate:%f%%\\n"%(yes,no,rate)\n<\/code><\/pre>\n
\u8fd0\u884c\u7ed3\u679c\uff1a
\n\"\"<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
1,444 Views\u53c2\u8003\u4e66\u7c4d\u300a\u673a\u5668\u5b66\u4e60\u5b9e\u6218\u300b K-\u8fd1\u90bb\u7b97\u6cd5\u6982\u8ff0 \u7b80\u5355\u6765\u8bf4\uff0ck\u8fd1\u90bb\u7b97\u6cd5\u91c7\u7528\u6d4b\u91cf\u4e0d\u540c\u7279\u5f81\u503c\u4e4b\u95f4\u7684 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[105],"tags":[42,43],"class_list":["post-241","post","type-post","status-publish","format-standard","hentry","category-machine-learning","tag-knn","tag-python"],"_links":{"self":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/241","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=241"}],"version-history":[{"count":16,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/241\/revisions"}],"predecessor-version":[{"id":1158,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/241\/revisions\/1158"}],"wp:attachment":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=241"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=241"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=241"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}