knn optimize top k select time

WenDesi · WenDesi · commit 14bd7c8680b5 · 2016-07-17T14:45:33.000+08:00
diff --git a/knn/knn.py b/knn/knn.py
@@ -32,40 +32,55 @@ def get_hog_features(trainset):
 def Predict(testset,trainset,train_labels):
     predict = []
     count = 0
+
     for test_vec in testset:
+        # 输出当前运行的测试用例坐标，用于测试
         print count
         count += 1
 
-        knn_list = []
+        knn_list = []       # 当前k个最近邻居
+        max_index = -1      # 当前k个最近邻居中距离最远点的坐标
+        max_dist = 0        # 当前k个最近邻居中距离最远点的距离
 
-        for i in range(len(train_labels)):
+        # 先将前k个点放入k个最近邻居中，填充满knn_list
+        for i in range(k):
             label = train_labels[i]
             train_vec = trainset[i]
 
-            dist = np.linalg.norm(train_vec - test_vec)
+            dist = np.linalg.norm(train_vec - test_vec)         # 计算两个点的欧氏距离
 
-            if len(knn_list) < k:                               # 如果还不够10个邻近点则直接添加即可
-                knn_list.append((dist,label))
-            else:
-                max_index = -1
-                max_dist = dist
+            knn_list.append((dist,label))
+
+        # 剩下的点
+        for i in range(k,len(train_labels)):
+            label = train_labels[i]
+            train_vec = trainset[i]
+
+            dist = np.linalg.norm(train_vec - test_vec)         # 计算两个点的欧氏距离
 
-                # 寻找10个邻近点钟距离最远的点
+            # 寻找10个邻近点钟距离最远的点
+            if max_index < 0:
                 for j in range(k):
                     if max_dist < knn_list[j][0]:
                         max_index = j
                         max_dist = knn_list[max_index][0]
 
-                if max_index >= 0:
-                    knn_list[max_index] = (dist,label)
+            # 如果当前k个最近邻居中存在点距离比当前点距离远，则替换
+            if dist < max_dist:
+                knn_list[max_index] = (dist,label)
+                max_index = -1
+
 
+        # 统计选票
         class_total = 10
         class_count = [0 for i in range(class_total)]
         for dist,label in knn_list:
             class_count[label] += 1
 
+        # 找出最大选票
         mmax = max(class_count)
 
+        # 找出最大选票标签
         for i in range(class_total):
             if mmax == class_count[i]:
                 predict.append(i)
