最近邻

无监督的最近邻是许多其它学习方法的基础,尤其是manifold learning(流形学习)和spectral clustering(谱聚类)。 neighbors-based(基于邻居的)监督学习分为两种:classification(分类)针对的是具有离散标签的数据,regression(回归)针对的是具有连续标签的数据。

最近邻方法背后的原理是从训练样本中找到与新点在距离上最近的预定数量的几个点,然后从这些点中预测标签。 这些点的数量可以是用户自定义的常量(K-最近邻学习), 也可以根据不同的点的局部密度(基于半径的最近邻学习)确定。距离通常可以通过任何度量来衡量:standard Euclidean distance(标准欧式距离)是最常见的选择。Neighbors-based(基于邻居的)方法被称为非泛化机器学习方法,因为它们只是简单地"记住"了其所有的训练数据(可能转换为一个快速索引结构,如Ball Tree或KD Tree)。

尽管它简单,但最近邻算法已经成功地适用于很多的分类和回归问题,例如手写数字或卫星图像的场景。作为一个 non-parametric(非参数化)方法,它经常成功地应用于决策边界非常不规则的分类情景下。

一、最近邻分类

最近邻分类属于基于实例的学习或非泛化学习:它不会去构造一个泛化的内部模型,而是简单地存储训练数据的实例。分类是由每个点的最近邻的简单多数投票中计算得到的:一个查询点的数据类型是由它最近邻点中最具代表性的数据类型来决定的。

scikit-learn实现了两种不同的最近邻分类器:基于每个查询点的k个最近邻实现,其中k是用户指定的整数值。RadiusNeighborsClassifier基于每个查询点的固定半径r内的邻居数量实现,其中r是用户指定的浮点数值。

k-邻居分类是KNeighborsClassifie的技术中比较常用的一种。 值的最佳选择是高度依赖数据的:通常较大的k是会抑制噪声的影响,但是使得分类界限不明显。

如果数据是不均匀采样的,那么RadiusNeighborsClassifier中的基于半径的近邻分类可能是更好的选择。用户指定一个固定半径,使得稀疏邻居中的点使用较少的最近邻来分类。对于高维参数空间,这个方法会由于所谓的"维度灾难"而变得不那么有效。

基本的最近邻分类使用统一的权重:分配给查询点的值是从最近邻的简单多数投票中计算出来的。 在某些环境下,最好对邻居进行加权,使得更近邻更有利于拟合。可以通过weights关键字来实现。默认值weights='uniform'为每个近邻分配统一的权重。而weights='distance'分配权重与查询点的距离成反比。 或者,用户可以自定义一个距离函数用来计算权重。

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from sklearn import neighbors, datasets

n_neighbors = 15

# import some data to play with
iris = datasets.load_iris()

# we only take the first two features. We could avoid this ugly
# slicing by using a two-dim dataset
X = iris.data[:, :2]
y = iris.target

h = .02  # step size in the mesh

# Create color maps
cmap_light = ListedColormap(['orange', 'cyan', 'cornflowerblue'])
cmap_bold = ListedColormap(['darkorange', 'c', 'darkblue'])

for weights in ['uniform', 'distance']:
    # we create an instance of Neighbours Classifier and fit the data.
    clf = neighbors.KNeighborsClassifier(n_neighbors, weights=weights)
    clf.fit(X, y)

    # Plot the decision boundary. For that, we will assign a color to each
    # point in the mesh [x_min, x_max]x[y_min, y_max].
    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])

    # Put the result into a color plot
    Z = Z.reshape(xx.shape)
    plt.figure()
    plt.pcolormesh(xx, yy, Z, cmap=cmap_light)

    # Plot also the training points
    plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold,
                edgecolor='k', s=20)
    plt.xlim(xx.min(), xx.max())
    plt.ylim(yy.min(), yy.max())
    plt.title("3-Class classification (k = %i, weights = '%s')"% (n_neighbors, weights))

plt.show()

二、最近邻回归

最近邻回归是用在数据标签为连续变量,而不是离散变量的情况下。分配给查询点的标签是由它的最近邻标签的均值计算而来的。

scikit-learn实现了两种不同的最近邻回归:KNeighborsRegressor基于每个查询点的k个最近邻实现,其中k是用户指定的整数值。RadiusNeighborsRegressor基于每个查询点的固定半径r内的邻点数量实现,其中r是用户指定的浮点数值。

基本的最近邻回归使用统一的权重:即本地邻域内的每个邻点对查询点的分类贡献一致。在某些环境下,对邻点加权可能是有利的,使得附近点对于回归所作出的贡献多于远处点。这可以通过weights关键字来实现。默认值weights='uniform'为所有点分配同等权重。而weights='distance'分配的权重与查询点距离呈反比。或者,用户可以自定义一个距离函数用来计算权重。

# #############################################################################
# Generate sample data
import numpy as np
import matplotlib.pyplot as plt
from sklearn import neighbors

np.random.seed(0)
X = np.sort(5 * np.random.rand(40, 1), axis=0)
T = np.linspace(0, 5, 500)[:, np.newaxis]
y = np.sin(X).ravel()

# Add noise to targets
y[::5] += 1 * (0.5 - np.random.rand(8))

# #############################################################################
# Fit regression model
n_neighbors = 5

for i, weights in enumerate(['uniform', 'distance']):
    knn = neighbors.KNeighborsRegressor(n_neighbors, weights=weights)
    y_ = knn.fit(X, y).predict(T)

    plt.subplot(2, 1, i + 1)
    plt.scatter(X, y, color='darkorange', label='data')
    plt.plot(T, y_, color='navy', label='prediction')
    plt.axis('tight')
    plt.legend()
    plt.title("KNeighborsRegressor (k = %i, weights = '%s')" % (n_neighbors, weights))

plt.tight_layout()
plt.show()

三、最近邻算法

• 暴力计算

最近邻的快速计算是机器学习中一个活跃的研究领域。最简单的近邻搜索的实现涉及数据集中所有成对点之间距离的暴力计算(线性扫描法):对于D维度中的N个样本来说,这个方法的复杂度是$O(DN^2)$。对于小数据样本,高效的暴力近邻搜索是非常有竞争力的。 然而,随着样本数N的增长,暴力方法很快变得不切实际了。在sklearn.neighbors类中,暴力近邻搜索通过关键字algorithm='brute'来指定,并通过sklearn.metrics.pairwise中的例程来进行计算。

所以实际应用中,往往会寻找其他类型的数据结构来保存特征,以降低搜索的时间复杂度。常用的存储结构可以分为树和图两大类。树结构的代表是KDTree,以及改进版BallTree和Annoy等;基于图结构的搜索算法有HNSW等。

• KDTree

kd树是一种对k维特征空间中的实例点进行存储以便对其快速检索的树形数据结构。它将二维Quad-trees和三维Oct-trees推广到任意数量的维度. KD树是一个二叉树结构,它沿着数据轴递归地划分参数空间，将其划分为嵌入数据点的嵌套的各向异性区域。KD树的构造非常快:因为只需沿数据轴执行分区,无需计算D-dimensional距离。一旦构建完成,查询点的最近邻距离计算复杂度仅为$O[\log(N)]$。虽然KD树的方法对于低维度(D<20)近邻搜索非常快,当D增长到很大时,效率变低:这就是所谓的"维度灾难"的一种体现。在scikit-learn中,KD树近邻搜索可以使用关键字algorithm='kd_tree'来指定,并且使用类KDTree来计算。

kd树核心思想是对k维特征空间不断切分(假设特征维度是768,对于(0,1,2,...,767)中的每一个维度,以中值递归切分)构造的树,每一个节点是一个超矩形,小于结点的样本划分到左子树,大于结点的样本划分到右子树。

树构造完毕后,最终检索时:

1. 从根结点出发,递归地向下访问kd树。若目标点$x$当前维的坐标小于切分点的坐标,移动到左子树,否则移动到右子树,直至到达叶结点;
2. 以此叶结点为"最近点",递归地向上回退,查找该结点的兄弟结点中是否存在更近的点,若存在则更新"最近点",否则回退;未到达根结点时继续执行2;
3. 回退到根结点时,搜索结束。

import numpy as np
from math import sqrt
import pandas as pd
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split

class Node:
    def __init__(self, data, depth=0, lchild=None, rchild=None):
        self.data = data     # 此结点
        self.depth = depth   # 树的深度
        self.lchild = lchild # 左子结点
        self.rchild = rchild # 右子节点


class KdTree:
    def __init__(self):
        self.KdTree = None
        self.n = 0
        self.nearest = None

    def create(self, dataSet, depth=0):
        """KD-Tree创建过程"""
        if len(dataSet) > 0:
            m, n = np.shape(dataSet)
            self.n = n - 1
            # 按照哪个维度进行分割，比如0：x轴，1：y轴
            axis = depth % self.n
            # 中位数
            mid = int(m / 2)
            # 按照第几个维度（列）进行排序
            dataSetcopy = sorted(dataSet, key=lambda x: x[axis])
            # KD结点为中位数的结点，树深度为depth
            node = Node(dataSetcopy[mid], depth)
            if depth == 0:
                self.KdTree = node
            # 前mid行为左子结点，此时行数m改变，深度depth+1，axis会换个维度
            node.lchild = self.create(dataSetcopy[:mid], depth+1)
            node.rchild = self.create(dataSetcopy[mid+1:], depth+1)
            return node
        return None

    def preOrder(self, node):
        """遍历KD-Tree"""
        if node is not None:
            print(node.depth, node.data)
            self.preOrder(node.lchild)
            self.preOrder(node.rchild)

    def search(self, x, count=1):
        """KD-Tree的搜索"""
        nearest = [] # 记录近邻点的集合
        for i in range(count):
            nearest.append([-1, None])
        self.nearest = np.array(nearest)

        def recurve(node):
            """内方法，负责查找count个近邻点"""
            if node is not None:
                # 步骤1：怎么找叶子节点
                # 在哪个维度的分割线，0,1,0,1表示x,y,x,y
                axis = node.depth % self.n
                # 判断往左走or右走，递归，找到叶子结点
                daxis = x[axis] - node.data[axis]
                if daxis < 0:
                    recurve(node.lchild)
                else:
                    recurve(node.rchild)

                # 步骤2：满足的就插入到近邻点集合中
                # 求test点与此点的距离
                dist = sqrt(sum((p1 - p2) ** 2 for p1, p2 in zip(x, node.data)))
                # 遍历k个近邻点，如果不满k个，直接加入，如果距离比已有的近邻点距离小，替换掉，距离是从小到大排序的
                for i, d in enumerate(self.nearest):
                    if d[0] < 0 or dist < d[0]:
                        self.nearest = np.insert(self.nearest, i, [dist, node], axis=0)
                        self.nearest = self.nearest[:-1]
                        break

                # 步骤3：判断与垂线的距离，如果比这大，要查找垂线的另一侧
                n = list(self.nearest[:, 0]).count(-1)
                # -n-1表示不为-1的最后一行，就是记录最远的近邻点（也就是最大的距离）
                # 如果大于到垂线之间的距离，表示垂线的另一侧可能还有比他离的近的点
                if self.nearest[-n-1, 0] > abs(daxis):
                    # 如果axis < 0，表示测量点在垂线的左侧，因此要在垂线右侧寻找点
                    if daxis < 0:
                        recurve(node.rchild)
                    else:
                        recurve(node.lchild)

        recurve(self.KdTree)        # 调用根节点，开始查找
        knn = self.nearest[:, 1]    # knn为k个近邻结点
        belong = []                 # 记录k个近邻结点的分类
        for i in knn:
            belong.append(i.data[-1])
        b = max(set(belong), key=belong.count) # 找到测试点所属的分类

        return self.nearest, b


    def show_train():
        plt.scatter(x0[:, 0], x0[:, 1], c='pink', label='[0]')
        plt.scatter(x1[:, 0], x1[:, 1], c='orange', label='[1]')
        plt.xlabel('sepal length')
        plt.ylabel('sepal width')


if __name__ == "__main__":
    iris = load_iris()
    df = pd.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]])
    train, test = train_test_split(data, test_size=0.1)
    x0 = np.array([x0 for i, x0 in enumerate(train) if train[i][-1] == 0])
    x1 = np.array([x1 for i, x1 in enumerate(train) if train[i][-1] == 1])

    kdt = KdTree()
    kdt.create(train)
    kdt.preOrder(kdt.KdTree)

    score = 0
    for x in test:
        show_train()
        plt.scatter(x[0], x[1], c='red', marker='x')  # 测试点
        near, belong = kdt.search(x[:-1], 5)  # 设置临近点的个数
        if belong == x[-1]:
            score += 1
        print(x, "predict:", belong)
        print("nearest:")
        for n in near:
            print(n[1].data, "dist:", n[0])
            plt.scatter(n[1].data[0], n[1].data[1], c='green', marker='+')  # k个最近邻点
        plt.legend()
        plt.show()

    score /= len(test)
    print("score:", score)

• BallTree

为了解决KD树在高维上效率低下的问题, ball树数据结构就被研发出来了.其中KD树沿笛卡尔轴(即坐标轴)分割数据,ball树在沿着一系列的hyper-spheres来分割数据. 通过这种方法构建的树要比KD树消耗更多的时间,但是这种数据结构对于高结构化的数据是非常有效的,即使在高维度上也是一样.

ball树将数据递归地划分为由质心C和半径R定义的节点,使得节点中的每个点位于由r和C定义的hyper-sphere内.通过使用triangle inequality(三角不等式)减少近邻搜索的候选点数:$|x+y| \leq |x| + |y|$。

通过这种设置,测试点和质心之间的单一距离计算足以确定距节点内所有点的距离的下限和上限. 由于ball树节点的球形几何,它在高维度上的性能超出KD-tree,尽管实际的性能高度依赖于训练数据的结构. 在scikit-learn中,基于ball树的近邻搜索可以使用关键字algorithm='ball_tree'来指定,并且使用类sklearn.neighbors.BallTree 来计算. 或者,用户可以直接使用BallTree类.

http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.8209

• 最近邻算法的选择

对于给定数据集的最优算法是一个复杂的选择,并且取决于多个因素:

• 样本数量N(i.e. n_samples)和维度D(例如.nfeatures).
  • Brute force查询时间以$O[D N]$增长
  • Ball tree查询时间大约以$O[D \log(N)]$增长
  • KD tree的查询时间的变化是很难精确描述的.对于较小的D(小于20)的成本大约是O[D\log(N)],并且KD树更加有效.对于较大的D成本的增加接近O[DN],由于树结构引起的开销会导致查询效率比暴力还要低.

对于小数据集(n小于30),log(N)相当于N,暴力算法比基于树的算法更加有效. KDTree和BallTree通过提供一个leaf size参数来解决这个问题:这控制了查询切换到暴力计算样本数量.使得两种算法对较小的N的效率都能接近于暴力计算.

• 数据结构:数据的intrinsic dimensionality(本征维数)和/或数据的sparsity(稀疏度).本征维数是指数据所在的流形的维数$d \le D$,在参数空间可以是线性或非线性的.稀疏度指的是数据填充参数空间的程度(这与"稀疏"矩阵中使用的概念不同,数据矩阵可能没有零项,但是从这个意义上来讲,它的structure仍然是“稀疏”的)。
  • Brute force(暴力查询)时间不受数据结构的影响。
  • Ball tree和KD tree的数据结构对查询时间影响很大. 一般地,小维度的sparser(稀疏)数据会使查询更快. 因为KD树的内部表现形式是与参数轴对齐的,对于任意的结构化数据它通常不会表现的像ball tree那样好.

在机器学习中往往使用的数据集是非常结构化的, 而且非常适合基于树结构的查询。

• query point(查询点)所需的近邻数k 。
  • Brute force查询时间几乎不受k值的影响.
  • Ball tree和KD tree的查询时间会随着k的增加而变慢.这是由于两个影响:首先,k的值越大在参数空间中搜索的部分就越大. 其次,使用k>1进行树的遍历时,需要对内部结果进行排序.

当k相比N变大时,在基于树的查询中修剪树枝的能力是减弱的.在这种情况下,暴力查询会更加有效.

• query points(查询点)数.
  • ball tree和KD Tree都需要一个构建阶段. 在许多查询中分摊时,这种结构的成本可以忽略不计。如果只执行少量的查询,可是构建成本却占总成本的很大一部分.如果仅需查询很少的点,暴力方法会比基于树的方法更好.

一般地,如果k>=N/2,或输入是稀疏矩阵,或'effective_metric_'不在'kd_tree'或'ball_tree'的'VALID_METRICS'列表中，那么algorithm='auto'选择'brute'。 如果k<N/2并且'effective_metric_'在'kd_tree'的'VALID_METRICS'列表中,那么algorithm='auto'选择'kd_tree'。 如果k< N/2并且'effective_metric_'在'ball_tree'的'VALID_METRICS'列表中,那么algorithm='auto'选择'ball_tree'。这种选择基于以下假设:查询点的数量与训练点的数量至少在相同的数量级,并且leaf_size接近其默认值30.

• leaf_size的影响

如上所述,对于小样本暴力搜索是比基于树的搜索更有效的方法.这一事实在ball树和KD树中被解释为在叶节点内部切换到暴力搜索.该开关的级别可以使用参数leaf_size来指定.这个参数选择有很多的效果:

• 构造时间:更大的leaf_size会导致更快的树构建时间,因为需要创建更少的节点.
• 查询时间:一个大或小的leaf_size可能会导致次优查询成本. 当leaf_size接近1时,遍历节点所涉及的开销大大减慢了查询时间.当leaf_size,接近训练集的大小,查询变得本质上是暴力的. 这些之间的一个很好的妥协是leaf_size=30,这是该参数的默认值.
• 内存:随着leaf_size的增加,存储树结构所需的内存减少。对于存储每个节点的D维质心的ball tree,这点至关重要。针对BallTree所需的存储空间近似于1/leaf_size乘以训练集的大小.

leaf_size不被brute force queries(暴力查询)所引用.

# test 1
>>> from sklearn.neighbors import NearestNeighbors, KDTree
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> nbrs = NearestNeighbors(n_neighbors=2, algorithm='ball_tree').fit(X)
>>> distances, indices = nbrs.kneighbors(X)

# test 2
>>> kdt = KDTree(X, leaf_size=30, metric='euclidean')
>>> kdt.query(X, k=2, return_distance=False)          

四、邻域成分分析

参考论文: Neighbourhood Components Analysis

邻域成分分析(NCA,Neighborhood Components Analysis)是一种距离度量学习算法,其目的是提高最近邻分类相对于标准欧氏距离的准确性。该算法直接最大化训练集上k近邻(KNN)得分的随机变量,还可以拟合数据的低维线性投影,用于数据可视化和快速分类。

在上图中,我们考虑随机生成的数据集中的一些点。重点研究了３号样本点的随机KNN分类问题.样本3和另一个点之间的链路厚度与它们之间的距离成正比，可以看作是随机最近邻预测规则分配给该点的相对权重(或概率)。在原始空间中，样本3有许多来自不同类的随机邻居，因此正确的分类不太可能。然而，在NCA学习的投影空间中，唯一权重不可忽略的随机邻域与样本3属于同一类，保证了样本3的分类良好。

NCA的目标是拟合一个尺寸为(n_components,n_features)的最优线性变换矩阵,使所有被正确分类的概率样本的和最大,即:

其中N是样本数,$p_i$是第i个样本在学习的嵌入空间中,根据随机近邻规则正确分类的可能性:

其中$C_i$是第i个样本被分类到的点集,$P_{ij}$为嵌入空间中欧氏距离上的归一化指数(softmax)值:

其中$|| L(x_i - x_j)||^2 = (x_i - x_j)^TM(x_i - x_j)$,$M = L^T L$是大小为(特征数，特征数)对称正半定矩阵。

• 分类

与最近邻分类器(KNeighborsClassifier)相结合，NCA是一种有效的分类算法，因为它可以自然地处理多类问题，而不需要增加模型的大小，并且不引入需要用户进行微调的额外参数。

NCA分类在不同规模和难度的数据集的实际应用中显示出良好的效果。与线性判别分析等相关方法相比，NCA没有对类的分布做任何假设。而最近邻分类自然会产生高度不规则的决策边界。

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import (KNeighborsClassifier,
                               NeighborhoodComponentsAnalysis)
from sklearn.pipeline import Pipeline


print(__doc__)

n_neighbors = 1

dataset = datasets.load_iris()
X, y = dataset.data, dataset.target

# we only take two features. We could avoid this ugly
# slicing by using a two-dim dataset
X = X[:, [0, 2]]

X_train, X_test, y_train, y_test = \
    train_test_split(X, y, stratify=y, test_size=0.7, random_state=42)

h = .01  # step size in the mesh

# Create color maps
cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])

names = ['KNN', 'NCA, KNN']

classifiers = [Pipeline([('scaler', StandardScaler()),
                         ('knn', KNeighborsClassifier(n_neighbors=n_neighbors))
                         ]),
               Pipeline([('scaler', StandardScaler()),
                         ('nca', NeighborhoodComponentsAnalysis()),
                         ('knn', KNeighborsClassifier(n_neighbors=n_neighbors))
                         ])
               ]

x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                     np.arange(y_min, y_max, h))

for name, clf in zip(names, classifiers):

    clf.fit(X_train, y_train)
    score = clf.score(X_test, y_test)

    # Plot the decision boundary. For that, we will assign a color to each
    # point in the mesh [x_min, x_max]x[y_min, y_max].
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])

    # Put the result into a color plot
    Z = Z.reshape(xx.shape)
    plt.figure()
    plt.pcolormesh(xx, yy, Z, cmap=cmap_light, alpha=.8)

    # Plot also the training and testing points
    plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold, edgecolor='k', s=20)
    plt.xlim(xx.min(), xx.max())
    plt.ylim(yy.min(), yy.max())
    plt.title("{} (k = {})".format(name, n_neighbors))
    plt.text(0.9, 0.1, '{:.2f}'.format(score), size=15,ha='center', va='center', transform=plt.gca().transAxes)
plt.show()

• 降维

NCA可用于进行监督降维。输入数据被投影到一个由最小化NCA目标的方向组成的线性子空间上。可以使用参数n_components设置所需的维数。例如,下图显示了主成分分析的降维(sklearn.decomposition.PCA),线性判别分析(sklearn.discriminant_analysis.LinearDiscriminantAnalysis)和邻域成分分析(NeighborhoodComponentsAnalysis)在一个64个特征,1797个样本的数字数据集的降维结果。数据集被划分为大小相同的训练集和测试集，然后进行标准化。为了评价该方法的分类精度，对每种方法找到的二维投影点进行了3-最近邻分类精度的计算。每个数据样本属于10个类中的一个。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.decomposition import PCA
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
from sklearn.neighbors import (KNeighborsClassifier,
                               NeighborhoodComponentsAnalysis)
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

print(__doc__)

n_neighbors = 3
random_state = 0

# Load Digits dataset
X, y = datasets.load_digits(return_X_y=True)

# Split into train/test
X_train, X_test, y_train, y_test = \
    train_test_split(X, y, test_size=0.5, stratify=y,
                     random_state=random_state)

dim = len(X[0])
n_classes = len(np.unique(y))

# Reduce dimension to 2 with PCA
pca = make_pipeline(StandardScaler(),
                    PCA(n_components=2, random_state=random_state))

# Reduce dimension to 2 with LinearDiscriminantAnalysis
lda = make_pipeline(StandardScaler(),
                    LinearDiscriminantAnalysis(n_components=2))

# Reduce dimension to 2 with NeighborhoodComponentAnalysis
nca = make_pipeline(StandardScaler(),
                    NeighborhoodComponentsAnalysis(n_components=2,
                                                   random_state=random_state))

# Use a nearest neighbor classifier to evaluate the methods
knn = KNeighborsClassifier(n_neighbors=n_neighbors)

# Make a list of the methods to be compared
dim_reduction_methods = [('PCA', pca), ('LDA', lda), ('NCA', nca)]

# plt.figure()
for i, (name, model) in enumerate(dim_reduction_methods):
    plt.figure()
    # plt.subplot(1, 3, i + 1, aspect=1)

    # Fit the method's model
    model.fit(X_train, y_train)

    # Fit a nearest neighbor classifier on the embedded training set
    knn.fit(model.transform(X_train), y_train)

    # Compute the nearest neighbor accuracy on the embedded test set
    acc_knn = knn.score(model.transform(X_test), y_test)

    # Embed the data set in 2 dimensions using the fitted model
    X_embedded = model.transform(X)

    # Plot the projected points and show the evaluation score
    plt.scatter(X_embedded[:, 0], X_embedded[:, 1], c=y, s=30, cmap='Set1')
    plt.title("{}, KNN (k={})\nTest accuracy = {:.2f}".format(name,
                                                              n_neighbors,
                                                              acc_knn))
plt.show()

五、ANN

参考faiss项目