本文共 2026 字，大约阅读时间需要 6 分钟。

最近邻

K-近邻（待会介绍）的一种极端情况。“近朱者赤，近墨者黑”。

def distance(p0, p1):    # Computes squared euclidean distance    return np.sqrt(np.sum((p0-p1)**2))def nn_classify(training_set, training_labels, new_example):    dists = np.array([distance(t, new_example) for t in training_set])    nearest = dists.argmin()    return training_labels[nearest]

K近邻

将上述的最近邻算法泛化为一个k近邻分类器，不仅考虑最近邻的点，还要考虑前k个最近邻点。k近邻假设给定一个训练数据集，其中的实例类别已定，分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式来进行预测。k近邻不具有显式的学习过程(lazy learning)，实际是利用训练数据集对特征向量空间进行划分。

• 优点：精度高、对异常值不敏感、无数据输入假定
• 缺点：计算复杂度高、空间复杂度高
  • K近邻算法必须保存全部数据集，如果训练集很大，需要使用大量的存储空间。
  • 由于需要对数据集中每个数据计算距离值，实际使用可能耗时。
  • 无法给出任何数据的基础结果信息，无法知晓平均实例样本和典型实例样本的特征。

K近邻算法的三个基本要素：

def knn_classify(inX, dataset, labels, k):    size = dataset.shape[0]    diffMat = np.tile(inX, (size, 1)) - dataset    sqDiffMat = diffMat ** 2    sqDistances = sqDiffMat.sum(axis=1)    distances = sqDistances ** 0.5    sortedDistIndicies = distances.argsort()    classCount={}    for i in range(k):        votelabel = labels[sortedDistIndicies[i]]        classCount[votelabel] = classCount.get(votelabel, 0) + 1    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)    return sortedClassCount[0][0]

实践指导

• 归一化到Z-score: 每个特征都采用同样的单位（无量纲的），可以放心的混合不同维度的特征。防止少量特征占统治地位，使得所有维度都具有相同的重要性。

X_norm = (X - X_min) / (X_max - X_min )

lambda x: (x - x.min()) / (x.max() - x.min())

def autoNorm(dataset):    minVals = dataset.min(0)    maxVals = dataset.max(0)    ranges = maxVals - minVals    normDataset = np.zeros(np.shape(dataset))    m = dataset.shape[0]    normDataset = dataset - np.tile(minVals, (m, 1))    normDataset = normDataset / np.tile(ranges, (m, 1))    return normDataset

拓展

k近邻由Cover和Hart与1967年提出。Cover T, Hart P. Nearest neighbor pattern classification. IEEE Transactions on Information Theory.

《Building Machine Learning Systems with Python》

《Machine Learning in Action》

《统计学习方法》

《机器学习》