机器学习（二）¶

knn算法的使用¶

K近邻算法（K-Nearest Neighbor，KNN）是一种基本的分类和回归算法。

其基本思想是在样本空间中通过计算不同样本点之间的距离，以最邻近样本点的标签来决定该样本点的类别。KNN算法实现简单，不需要求解复杂的数学模型，具有较高的可解释性和准确性，广泛应用于模式识别、图像处理、数据挖掘等领域。

KNN算法的核心思路是：对于给定的一个未标记的样本，将其与已标记的样本比较，找到距离该样本最近的K个已标记样本，然后根据这K个样本的标记来预测该样本的标记。其中K是一个预先设定的常数，一般通过交叉验证来确定。

KNN算法的优点在于它可以非常自然地处理多分类问题（例如，通过多数表决确定样本的类别），并且对于训练样本集中的噪音和异常点具有较高的鲁棒性。但是，KNN算法的计算成本较高，尤其是在处理大规模数据集时，因为要计算每个未标记样本和所有已标记样本之间的距离。此外，在KNN算法中，距离度量的选择对算法的性能影响很大，需要根据具体问题进行选择。

from sklearn.neighbors import KNeighborsClassifier

# 构造数据集

x = [0], [1], [2], [3]
y = [0,0,1,1]

# 实例化对象
estimator = KNeighborsClassifier(n_neighbors=2)

# 使用fit方法进行训练
estimator.fit(x,y)


# 数据预测
ret = estimator.predict([[0]])

print(ret)

ret1 = estimator.predict([[1]])

print(ret1)

k值过小：易受异常点影响 k值过大：受到样本均衡问题

kd树¶

KD树（K-Dimensional Tree）是一种基于二叉树的数据结构，它可以高效地处理k维空间中的数据。KD树的构建过程中，每次以某一维度为分割轴，将数据集划分成两个子集，并递归地在子集中构建KD树。通过这种方式，KD树可以实现对高维空间中数据的快速搜索和最近邻查询等操作。

KNN（K-Nearest Neighbor）是一种基于实例的学习方法，它的基本思想是利用已知类别的样本中的K个最邻近的样本，来确定未知样本的类别。KNN算法的实现过程中，需要对每个未知样本进行一次最近邻查询，以获取最邻近的K个样本。而KD树正是KNN算法中实现最近邻查询的一种常用数据结构。

在KNN算法中，使用KD树可以显著提高查询的速度，因为KD树能够有效地减少需要对每个样本进行距离计算的次数。同时，通过KD树的优化，可以对KNN算法中的内存占用和查询时间等指标进行优化，提升整个算法的性能。

构建过程：

在构建kd树的过程中，我们首先需要选定一个划分维度，然后根据该维度将数据分为左右两个子集，左子集包含所有小于该维度值的数据点，右子集包含所有大于该维度值的数据点。接着，我们可以递归地在子集中继续进行划分，直到所有数据点都被划分到一个叶子节点中。

在进行查询操作时，我们首先需要确定查询点所处的叶子节点，然后计算该叶子节点中所有数据点与查询点之间的距离，并找出距离最近的数据点。如果该节点的父节点中还存在更近的数据点，则继续向上回溯，直到找到距离最近的数据点为止。

需要注意的是，kd树的构建和查询过程中，划分维度的选择和数据点的插入顺序都会影响树的结构和查询效率。因此，在实际应用中，我们需要根据具体情况来选择最优的划分策略和数据插入顺序，以获得最佳的性能和效果。