编程知识 cdmana.com

k临近算法程序模拟

《统计学习方法》李航 第三章 k临近法

  • 我是小白一个;本文代码转载地址文末有注释;注释大部分自己书写,有问题请多指教。
  1. 本章第一个程序是求向量的范数
import math
# combinations函数用于组合,表示从n中取出m个
# 作为对比,permutations函数用于排序,表示从n中依次取出m个
# from itertools import combinations

def L(x, y, p):
    if len(x) == len(y) and len(x) > 1:  # 进行计算的前提
        sum = 0
        for i in range(len(x)):  # i表示下标
            sum += math.pow(abs(x[i] - y[i]), p)  # pow求幂,abs求绝对值
        return math.pow(sum, 1/p)
    else:
        return 0

x1 = [1, 1]
x2 = [5, 1]
x3 = [4, 4]

for i in range(1, 5):
        r = {"1-{}".format(c):L(x1, c, p=i) for c in [x2, x3]}
        print("当前次数:{},当前r:{}".format(i, r))
        print("当前最小:")
        print(min(zip(r.values(), r.keys())))

输出结果:

当前次数:1,当前r:{'1-[5, 1]': 4.0, '1-[4, 4]': 6.0}
当前最小:
(4.0, '1-[5, 1]')
当前次数:2,当前r:{'1-[5, 1]': 4.0, '1-[4, 4]': 4.242640687119285}
当前最小:
(4.0, '1-[5, 1]')
当前次数:3,当前r:{'1-[5, 1]': 3.9999999999999996, '1-[4, 4]': 3.7797631496846193}
当前最小:
(3.7797631496846193, '1-[4, 4]')
当前次数:4,当前r:{'1-[5, 1]': 4.0, '1-[4, 4]': 3.5676213450081633}
当前最小:
(3.5676213450081633, '1-[4, 4]')
  1. 第二个程序,模拟k临近算法 思想:遍历所有的点,找出最近的k个点,通过多数表决,决定测试点的分类
import numpy as np
import pandas as dp
import matplotlib.pyplot as plt

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split  # 用于划分数据
from collections import Counter  # 计数器

class KNN:
    def __init__(self, X_train, y_train, n_neighbors=3, p=2):  # 设置了k与p,分别表示最临近的3个点,和距离用二范数决定
        self.n = n_neighbors
        self.p = p
        self.X_train = X_train
        self.y_train = y_train

    def predict(self, X):
        knn_list = []
        # 先求出三个点的“距离”,这里的k=3,p=2。根据需要修改
        for i in range(self.n):
            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)
            knn_list.append((dist, self.y_train[i]))
        # 然后,递归遍历剩下的点,通过判断:距离  是否比  已经计算的距离  小,小就替换。最终这个列表剩下的是最临近的三个点
        for i in range(self.n, len(X_train)):
            max_index = knn_list.index(max(knn_list, key=lambda x:x[0]))
            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)
            if knn_list[max_index][0] > dist:
                knn_list[max_index] = (dist, self.y_train[i])
        # 我们将knn_list中最后一行取出来,即取出了最临近的三个点的类别
        knn = [k[-1] for k in knn_list]
        # 用计数器,这一步结果应该是{"1":数量,“0”:数量 }
        count_pairs = Counter(knn)
        # count_pairs.items()存储的是,[类别,数量]
        # 按照列表的第二维进行排序,从小到大。
        # 这里排序考虑到有些数据不止两种类型。
        # [-1][0]取出最后一行的第一维,即最可能的类型
        max_possible = sorted(count_pairs.items(), key=lambda x:x[1])[-1][0]
        return  max_possible

    def score(self, X_test, y_test):
        right_count = 0
        for X, y in zip(X_test, y_test):
            label = self.predict(X)
            if label == y:
                right_count += 1
        return right_count/len(X_test)


iris = load_iris()
df = dp.DataFrame(iris.data, columns=iris.feature_names)
df['label'] = iris.target
df.columns = ["sepal length", "sepal width", "petal length", "petal width", "label"]

data = np.array(df.iloc[:100, [0, 1, -1]])
X, y = data[:, :-1], data[:, -1]
# 将数据划分成训练集和测试集,测试集占比0.25
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25)

clf = KNN(X_train, y_train)
print("评分:")
print(clf.score(X_test, y_test))

test_point = [5.0, 4.0]
print('test point score:{}'.format(clf.predict(test_point)))  # 输出这个点可能的类别,1或者0

plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label="0")
plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label="1")

plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()
plt.show()

结果: 评分大多数时候1.0,偶尔0.96

版权声明
本文为[Allez_Levide]所创,转载请带上原文链接,感谢
https://my.oschina.net/LevideGrowthHistory/blog/4714995

Scroll to Top