沐诩 2018-09-03
摘要: 本文简单介绍最近邻算法的基本思想以及具体python实现,并且分析了其优缺点及适用范围,适合初学者理解与动手实践。
新生开学了,部分大学按照兴趣分配室友的新闻占据了头条,这其中涉及到机器学习算法的应用。此外,新生进入大学后,可能至少参加几个学生组织或社团。社团是根据学生的兴趣将它们分为不同的类别,那么如何定义这些类别,或者区分各个组织之间的差别呢?我敢肯定,如果你问过运营这些社团的人,他们肯定不会说他们的社团和其它的社团相同,但在某种程度上是相似的。比如,老乡会和高中同学会都有着同样的生活方式;足球俱乐部和羽毛球协会对运动有着相同的兴趣;科技创新协会和创业俱乐部有相近的的兴趣等。也许让你去衡量这些社团或组织所处理的事情或运行模式,你自己就可以确定哪些社团是自己感兴趣的。但有一种算法能够帮助你更好地做出决策,那就是k-Nearest Neighbors(NN)算法, 本文将使用学生社团来解释k-NN算法的一些概念,该算法可以说是最简单的机器学习算法,构建的模型仅包含存储的训练数据集。该算法对新数据点进行预测,就是在训练数据集中找到最接近的数据点——其“最近邻居”。
在其最简单的版本中,k-NN算法仅考虑一个最近邻居,这个最近邻居就是我们想要预测点的最近训练数据点。然后,预测结果就是该训练点的输出。下图说明构造的数据集分类情况。
从图中可以看到,我们添加了三个新的数据点,用星星表示。对于三个点中的每一点,我们都标记了训练集中离其最近的点,最近邻算法的预测输出就是标记的这点(用交叉颜色进行表示)。
同样,我们也可以考虑任意数量k个邻居,而不是只考虑一个最近的邻居。这是k-NN算法名称的由来。在考虑多个邻居时,我们使用投票的方式来分配标签。这意味着对于每个测试点,我们计算有多少个邻居属于0类以及有多少个邻居属于1类。然后我们统计这些近邻中属于哪一类占的比重大就将预测点判定为哪一类:换句话说,少数服从多数。以下示例使用了5个最近的邻居:
同样,将预测结果用交叉的颜色表示。从图中可以看到,左上角的新数据点的预测与我们仅使用一个最近邻居时的预测结果不相同。
虽然此图仅展示了用于二分类的问题,但此方法可应用于具有任意数量类的数据集。对于多分类问题,同样计算k个邻居属于哪些类,并进行数量统计,从中选取数量最多的类作为预测结果。
以下是k-NN算法的伪代码,用于对一个数据点进行分类(将其称为A点):
对于数据集中的每一个点:
Python实现代码如下:
def knnclassify(A, dataset, labels, k): datasetSize = dataset.shape[0] # 计算A点和当前点之间的距离 diffMat = tile(A, (datasetSize, 1)) - dataset sqDiffMat = diffMat ** 2 sqDistances = sqDiffMat.sum(axis=1) distances = sqDistances ** 0.5 # 按照增序对距离排序 sortedDistIndices = distances.argsort() # 选出距离最小的k个点 classCount = {} for i in range(k): voteIlabel = labels[sortedDistIndices[i]] classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 # 对这些点所处的类别按照频次排序 sortedClassCount = sorted(classCount.iteritem(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0]
下面让我们深入研究下上述代码:
Scikit-Learn是一个机器学习工具箱,内部集成了很多机器学习算法。现在让我们看一下如何使用Scikit-learn实现kNN算法。代码如下:
from sklearn import datasets from sklearn.model_selection import train_test_split from sklearn.neighbors import KNeighborsClassifier # 导入iris数据集 iris = datasets.load_iris() X = iris.data y = iris.target # 将其按照一定的比例划分为训练集和测试集(random_state=0 保证每次运行分割得到一样的训练集和测试集) X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0) # 设定邻居个数 clf = KNeighborsClassifier(n_neighbors=5) # 拟合训练数据 clf.fit(X_train, y_train) # 对测试集进行预测 predictions = clf.predict(X_test) print("Test set predictions: {}".format(predictions)) # 评估模型性能 accuracy = clf.score(X_test, y_test) print("Test set accuracy: {:.2f}".format(accuracy))
下面让我们来看看上述代码:
模型运行完毕,测试集上得到97%的准确度,这意味着模型在测试数据集中97%的样本都正确地预测出类别;
一般而言,k-NN分类器有两个重要参数:邻居数量以及数据点之间的距离计算方式。
k-NN的优势之一是该模型非常易于理解,并且通常无需进行大量参数调整的情况下就能获得比较不错的性能表现。在考虑使用更高级的技术之前,使用此算法是一种很好的基线方法。k-NN模型的建立通常会比较快,但是当训练集非常大时(无论是特征数还是样本数量),预测时耗费的时间会很多。此外,使用k-NN算法时,对数据进行预处理非常重要。该方法通常在具有许多特征(数百或更多)的数据集上表现不佳,并且对于大多数特征在大多数情况下为0的数据集(所谓的稀疏数据集)而言尤其糟糕。
k-NN算法是一种简单有效的数据分类方法,它是基于实例学习的一种机器学习算法,需要通过数据实例来执行机器学习算法,该算法必须携带完整的数据集。而对于大型的数据集,需要耗费比较大的存储。此外,还需要计算数据库中每个数据点距离预测点的的距离,这个过程会很麻烦,且耗时多。另一个缺点是k-NN算法不能够让你了解数据的基础结构,无法知道每个类别的“平均”或“范例”具体是什么样子。
因此,虽然k-NN算法易于理解,但由于预测速度慢且无法处理多特征问题,因此在实践中并不常用。
James Le,机器学习工程师
LinkedIn:http://www.linkedin.com/in/khanhnamle94
本文由阿里云云栖社区组织翻译。
文章原标题《k-Nearest Neighbors: Who are close to you》,译者:海棠,审校:Uncle_LLD。