ML入门1.0 -- 手写KNN
- 全文内容
- KNN简介
- 写作背景
- 算法原理
- 算法结构
- KNN实现
- 运行结果
- 完整代码见github
- 优缺点
全文内容
KNN简介
KNN 全称为 K Nearest Neighbors 中文又称 K- 近邻算法 ，是一种用与分类和回归的非参数统计的方法。KNN采用向量空间模型来分类，概念为相同类别的案例，彼此的相似度高，而可以借由计算与已知类别案例之相似度，来评估未知类别案例可能的分类。
KNN是一种基于实例的学习，或者是局部近似和将所有计算推迟到分类之后的惰性学习。k-近邻算法是所有的机器学习算法中最简单的之一。
写作背景
写这篇博客呢，主要是因为最近学校开了 ML 的课程，记录一下学习过程中的一些想法和踩过的坑，方便大家一起交流学习。
算法原理
KNN常用于有监督学习，作为一个分类算法，那么它的主要作用就是确定同一事物中的不同类别，例如区分三种鸾尾花，将不同身高的人类进行分类···
KNN算法的工作原理也很简单：给定一个具有若干数据的数据集，该数据集分为两个部分— 训练样本a & 测试样本b，训练样本a是一些既有特征向量（特征数据） 和 标签（类别） 的数据集合；测试样本b 是只有特征向量未知其类别的数据集合，那么确定测试样本b中的单个样本是基于该样本与训练样本a中样本的特征向量的某种距离度量，在训练样本a中找出K个与该样本距离度量最小的样本，之后基于这K个样本的标签信息进行投票，选择K个样本中出现最多的类别作为该单个测试样本标签（类别）的预测值。PS：一般情况下K<=20; 距离度量选择欧式距离。
欧式距离计算公式：
d = ∑ i = 0 n ( X i − Y i ) 2 d = \sqrt{\sum_{i=0}^{n}(Xi-Yi)^2} d=i=0∑n(Xi−Yi)2
以上解释涉及少量专业术语，考虑本人表述能力较差建议选择性阅读，这里给出一个非常生动的解释：
【数学】一只兔子帮你理解 kNN - 宏观经济算命椰的文章 - 知乎
link.
算法结构
Step1: 加载数据集
Step2: 分类
- 2.1 找到k个近邻
- 2.2 投票
KNN实现
这里的代码是用Python实现：
- 数据集选用：sklearn.datasets.load_iris (150个样本，3个类别)
Func1(): Loaddata() 读取数据集数据并划分训练集（120）和 测试集 （30）
# Step1 load iris data
def Loaddata():
''' :tempDataset: the returned Bunch object :X: 150 flowers' data (花朵的特征数据) :Y: 150 flowers' label (花朵的种类标签) :return: X1(train_set), Y1(train_label), X2(test_set), Y2(test_label) '''
tempDataset = sklearn.datasets.load_iris()
X = tempDataset.data
Y = tempDataset.target
# Step2 split train set & test set
X1, X2, Y1, Y2 = sklearn.model_selection.train_test_split(X, Y, test_size=0.2)
return X1, Y1, X2, Y2
Func2(): euclideanDistance(x, y) 计算单个样本之间的欧式距离
def euclideanDistance(x, y):
''' 计算欧式距离 :param x: 某一朵花的数据 :param y: 另一朵花的数据 :return: 两个花朵数据之间的欧式距离 '''
tempDistance = 0
m = x.shape[0]
for i in range(m):
tempDifference = x[i] - y[i]
tempDistance += tempDifference * tempDifference
return tempDistance**0.5
Func3(): stKnnClassifierTest(X1, Y1, X2, Y2, K = 5)
) 不当调包侠 手写KNN分类器
# Step3 Classify
def stKnnClassifierTest(X1, Y1, X2, Y2, K = 5):
''' :param X1: train_set :param Y1: train_label :param X2: test_set :param Y2: test_label :param K: 所选的neighbor的数量 :return: no return '''
tempStartTime = time.time()
tempScore = 0
test_Instances = Y2.shape[0]
train_Instances = Y1.shape[0]
print('the num of testInstances = {}'.format(test_Instances))
print('the num of trainInstances = {}'.format(train_Instances))
tempPredicts = np.zeros((test_Instances))
for i in range(test_Instances):
# tempDistacnes = np.zeros((test_Instances))
# Find K neighbors
tempNeighbors = np.zeros(K + 2)
tempDistances = np.zeros(K + 2)
for j in range(K + 2):
tempDistances[j] = 1000
tempDistances[0] = -1
for j in range(train_Instances):
tempdis = euclideanDistance(X2[i], X1[j])
tempIndex = K
while True:
if tempdis < tempDistances[tempIndex]:
# prepare move forward
tempDistances[tempIndex + 1] = tempDistances[tempIndex]
tempNeighbors[tempIndex + 1] = tempNeighbors[tempIndex]
tempIndex -= 1
#insert
else:
tempDistances[tempIndex + 1] = tempdis
tempNeighbors[tempIndex + 1] = j
break
# Vote
tempLabels = []
for j in range(K):
tempIndex = int(tempNeighbors[j + 1])
tempLabels.append(int(Y1[tempIndex]))
tempCounts = []
for label in tempLabels:
tempCounts.append(int(tempLabels.count(label)))
tempPredicts[i] = tempLabels[np.argmax(tempCounts)]
# the rate of correct classify
tempCorrect = 0
for i in range(test_Instances):
if tempPredicts[i] == Y2[i]:
tempCorrect += 1
tempScore = tempCorrect / test_Instances
tempEndTime = time.time()
tempRunTime = tempEndTime - tempStartTime
print(' ST KNN score: {}%, runtime = {}'.format(tempScore*100, tempRunTime))
运行结果
完整代码见github
link
优缺点
优点：
1.简单，易于理解，易于实现，无需估计参数；
2. 适合对稀有事件进行分类；
3.特别适合于多分类问题(multi-modal,对象具有多个类别标签
缺点：
1.该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。
2.该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。
