Python中更快的kNN分类算法

Question

我想从头开始编写自己的kNN算法，原因是我需要加权特征。问题是，尽管删除了for循环并使用内置的numpy功能，但我的程序仍然非常慢。

有人能建议一种加速的方法吗？我不使用np.sqrt来计算L2距离，因为这是不必要的，实际上会使速度变慢。

class GlobalWeightedKNN:
    """
    A k-NN classifier with feature weights

    Returns: predictions of k-NN.
    """

    def __init__(self):
        self.X_train = None
        self.y_train = None
        self.k = None
        self.weights = None
        self.predictions = list()

    def fit(self, X_train, y_train, k, weights):        
        self.X_train = X_train
        self.y_train = y_train
        self.k = k
        self.weights = weights

    def predict(self, testing_data):
        """
        Takes a 2d array of query cases.

        Returns a list of predictions for k-NN classifier
        """

        np.fromiter((self.__helper(qc) for qc in testing_data), float)  
        return self.predictions


    def __helper(self, qc):
        neighbours = np.fromiter((self.__weighted_euclidean(qc, x) for x in self.X_train), float)
        neighbours = np.array([neighbours]).T 
        indexes = np.array([range(len(self.X_train))]).T
        neighbours = np.append(indexes, neighbours, axis=1)

        # Sort by second column - distances
        neighbours = neighbours[neighbours[:,1].argsort()]  
        k_cases = neighbours[ :self.k]
        indexes = [x[0] for x in k_cases]

        y_answers = [self.y_train[int(x)] for x in indexes]
        answer = max(set(y_answers), key=y_answers.count)  # get most common value
        self.predictions.append(answer)


    def __weighted_euclidean(self, qc, other):
        """
        Custom weighted euclidean distance

        returns: floating point number
        """

        return np.sum( ((qc - other)**2) * self.weights )

- Eoin Ó Coinnigh

---

KNN是一种非常慢的预测算法（每个样本O(n*m)），除非您采用查找近似邻居的方法，如KD-Trees、LSH等。但是，您仍然可以通过避免存储所有距离和排序等方式来改进实现。相反，您可以使用大小为K的优先队列（堆，查看heapq模块），并仅在其中存储当前最接近的邻居。 - carrdelling

你并没有移除for循环，而是将它们放在生成器表达式中。这仍然是一个O[N^2]的算法...scipy和scikit-learn都有基于树的最近邻算法，时间复杂度为O[Nlog(N)]。我建议使用其中之一。 - jakevdp

谢谢回复！我必须道歉，我应该明确说明我需要保证最近邻居，所以 KD 树等方法不行。虽然列表推导式并没有真正消除循环，但它们比显式循环要快得多，对吧？感谢您提供优先队列的提示，我之前没有考虑过，主要瓶颈是需要计算所有 L2 距离...而不是排序。 - Eoin Ó Coinnigh

Answer 1

Scikit-learn使用KD Tree或Ball Tree算法以O[N log(N)]的时间复杂度计算最近邻。而您的算法则需要O[N^2]的时间复杂度，同时在Python生成器表达式中使用了嵌套循环，与优化过的代码相比会增加显著的计算开销。

如果您想要使用一个快速的O[N log(N)]实现来计算加权k近邻分类，可以使用sklearn.neighbors.KNeighborsClassifier 与加权明可夫斯基度量，将p=2（对于欧几里得距离）并将w设置为所需的权重。例如：

from sklearn.neighbors import KNeighborsClassifier

model = KNeighborsClassifier(metric='wminkowski', p=2,
                             metric_params=dict(w=weights))
model.fit(X_train, y_train)
y_predicted = model.predict(X_test)

- jakevdp

---

非常感谢，我不知道sklearn中有这个选项。我刚刚用“brute”算法（我的方法）进行了测试，有趣的是它实际上需要4782秒，而不是2079秒。然而，KD树非常快，当我使用非常大的数据集时，我肯定会选择这个选项，而不是使用我的实现，即使它不能保证找到最近的邻居，但它非常接近。谢谢！ - Eoin Ó Coinnigh

KD树/球树是一种精确算法，因此它保证能够找到最近的邻居。 - jakevdp

请原谅我，但我不认为那是真的，是吗？否则，在sklearn中拥有“暴力”算法选项还有什么意义呢？我阅读过的所有资料都告诉我，kd_tree和ball_tree不能保证找到最近的邻居，但可以找到非常接近的邻居。 - Eoin Ó Coinnigh

晚些时候回复并提供更多信息：kdtree和ball_tree确实保证找到最近的邻居。 "brute" 存在的原因有两个：（1）对于小数据集，暴力搜索更快，（2）它是一种更简单的算法，因此非常适用于测试。您可以确认这些算法在sklearn单元测试中直接进行比较。 - jakevdp

Answer 2

您可以查看这篇介绍 faiss 的优秀文章
用20行代码让 kNN 比Scikit-learn的快300倍！
它是在幕后使用C++开发的GPU加速算法。

import numpy as np
import faiss


class FaissKNeighbors:
    def __init__(self, k=5):
        self.index = None
        self.y = None
        self.k = k

    def fit(self, X, y):
        self.index = faiss.IndexFlatL2(X.shape[1])
        self.index.add(X.astype(np.float32))
        self.y = y

    def predict(self, X):
        distances, indices = self.index.search(X.astype(np.float32), k=self.k)
        votes = self.y[indices]
        predictions = np.array([np.argmax(np.bincount(x)) for x in votes])
        return predictions

- amirhe

Answer 3

修改你的类并使用BallTree数据结构（建立时间为O(n.(log n)^2)，参见https://arxiv.org/ftp/arxiv/papers/1210/1210.6122.pdf），使用自定义的DistanceMetric（由于在度量参数中不支持可调用函数的KDTree，如在这里作为注释提到的：https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.BallTree.html），您也可以使用以下代码（还要删除预测循环）：

from sklearn.neighbors import BallTree
from sklearn.neighbors import DistanceMetric
from scipy.stats import mode

class GlobalWeightedKNN:
    """
    A k-NN classifier with feature weights

    Returns: predictions of k-NN.
    """

    def __init__(self):
        self.X_train = None
        self.y_train = None
        self.k = None
        self.weights = None
        self.tree = None
        self.predictions = list()

    def fit(self, X_train, y_train, k, weights):        
        self.X_train = X_train
        self.y_train = y_train
        self.k = k
        self.weights = weights
        self.tree = BallTree(X_train, \
                             metric=DistanceMetric.get_metric('wminkowski', p=2, w=weights))

    def predict(self, testing_data):
        """
        Takes a 2d array of query cases.

        Returns a list of predictions for k-NN classifier
        """
        indexes = self.tree.query(testing_data, self.k, return_distance=False)
        y_answers = self.y_train[indexes]
        self.predictions = np.apply_along_axis(lambda x: mode(x)[0], 1, y_answers)
        return self.predictions

培训：

from time import time
n, d = 10000, 2
begin = time()
cls = GlobalWeightedKNN()
X_train = np.random.rand(n,d)
y_train = np.random.choice(2,n, replace=True)
cls.fit(X_train, y_train, k=3, weights=np.random.rand(d))
end = time()
print('time taken to train {} instances = {} s'.format(n, end - begin))
# time taken to train 10000 instances = 0.01998615264892578 s

测试/预测:

begin = time()
X_test = np.random.rand(n,d)
cls.predict(X_test)
end = time()
print('time taken to predict {} instances  = {} s'.format(n, end - begin))
#time taken to predict 10000 instances  = 3.732935905456543 s

- Sandipan Dey