机器学习入门：K-近邻算法详解与实现

引言

在机器学习的征途上，数学往往是第一道拦路虎。很多工程师在试图入门机器学习时，需要重新拾起那些曾被遗忘的数学知识。然而，对于工程师来说，直接动手编写代码是最有效的入门方法。本文将从最基础的机器学习算法——K-近邻算法（K-Nearest Neighbor，简称kNN）入手，逐步引导读者掌握传统机器学习算法。

为什么选择kNN算法

KNN算法因其简单易懂、无需复杂的数学背景而备受青睐。它不仅适用于分类任务，还可以应用于回归问题。与其他算法相比，KNN对数据没有特定假设，因此在实际应用中表现优秀，对异常点也不敏感。此外，KNN算法能详细解释机器学习过程中的各种细节，帮助读者全面理解机器学习的应用流程。

kNN算法简介

KNN算法的核心思想是“近朱者赤，近墨者黑”。具体来说，它认为每个样本都可以通过其最接近的k个邻居来表示。例如，要判断某个样本的类别，只需找到与其距离最近的k个样本，然后根据这些邻居的类别进行投票，最终确定该样本的类别。

kNN算法流程

KNN算法可以概括为“找邻居+投票”的过程。具体步骤如下：

1. 计算间隔：计算测试样本与训练集中每个样本的间隔，通常采用欧氏距离。
2. 排序选取：按间隔大小对训练样本进行排序，选取间隔最小的k个样本。
3. 投票决策：统计这k个样本的类别，出现次数最多的类别即为测试样本的类别。

算法实现

接下来，我们将通过一个具体的例子来展示如何实现KNN算法。

数据准备

首先，我们准备一组数据，包括特征和标签。特征表示肿瘤大小和发现时间，标签表示肿瘤是良性还是恶性。

```python import numpy as np import matplotlib.pyplot as plt

特征数据

rawdataX = [ [3.393533211, 2.331273381], [3.110073483, 1.781539638], [1.343853454, 3.368312451], [3.582294121, 4.679917921], [2.280362211, 2.866990212], [7.423436752, 4.685324231], [5.745231231, 3.532131321], [9.172112222, 2.511113104], [7.927841231, 3.421455345], [7.939831414, 0.791631213] ]

标签数据

rawdatay = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

数据可视化

Xtrain = np.array(rawdataX) ytrain = np.array(rawdatay) plt.scatter(Xtrain[ytrain==0,0], Xtrain[ytrain==0,1], color='g', label='Benign Tumor') plt.scatter(Xtrain[ytrain==1,0], Xtrain[ytrain==1,1], color='r', label='Malignant Tumor') plt.xlabel('Tumor Size') plt.ylabel('Discovery Time') plt.axis([0,10,0,5]) plt.legend() plt.show() ```

距离计算

接下来，我们需要计算测试样本与训练集中每个样本的距离。

```python from math import sqrt

def computedistances(testsample, trainingsamples): distances = [] for sample in trainingsamples: distance = sqrt(np.sum((sample - test_sample) ** 2)) distances.append(distance) return distances

testsample = np.array([8.90933607318, 3.365731514]) distances = computedistances(testsample, Xtrain) print("Distances:", distances) ```

排序选取

接下来，我们找到距离最近的k个样本。

```python import numpy as np

def findnearestneighbors(distances, k): sortedindices = np.argsort(distances) return sortedindices[:k]

k = 6 nearestindices = findnearestneighbors(distances, k) print("Nearest Indices:", nearestindices) ```

决策规则

根据最近的k个样本，进行投票，确定测试样本的类别。

```python def majorityvote(neighbors, labels): votecount = {} for index in neighbors: label = labels[index] if label not in votecount: votecount[label] = 0 votecount[label] += 1 return max(votecount, key=vote_count.get)

nearestlabels = ytrain[nearestindices] predictedlabel = majorityvote(nearestindices, nearestlabels) print("Predicted Label:", predictedlabel) ```

自定义KNN类

为了便于复用，我们将上述过程封装成一个KNN分类器类。

```python from collections import Counter

class KNNClassifier: def init(self, k): assert k >= 1, "k must be valid" self.k = k self.Xtrain = None self.ytrain = None

def fit(self, X_train, y_train):
    assert X_train.shape[0] == y_train.shape[0], "Size mismatch between X_train and y_train"
    self.X_train = X_train
    self.y_train = y_train

def predict(self, X_test):
    predictions = []
    for test_sample in X_test:
        distances = compute_distances(test_sample, self.X_train)
        nearest_indices = find_nearest_neighbors(distances, self.k)
        nearest_labels = self.y_train[nearest_indices]
        prediction = majority_vote(nearest_indices, nearest_labels)
        predictions.append(prediction)
    return np.array(predictions)

使用示例

knn = KNNClassifier(k=6) knn.fit(Xtrain, ytrain) testsample = np.array([8.90933607318, 3.365731514]) prediction = knn.predict(testsample.reshape(1, -1)) print("Prediction:", prediction) ```

使用scikit-learn库

除了自己实现KNN算法外，我们还可以借助scikit-learn库中的KNeighborsClassifier类。

```python from sklearn.neighbors import KNeighborsClassifier

创建KNN分类器实例

knnclassifier = KNeighborsClassifier(nneighbors=6)

训练模型

knnclassifier.fit(Xtrain, y_train)

预测

testsample = np.array([8.90933607318, 3.365731514]) prediction = knnclassifier.predict(test_sample.reshape(1, -1)) print("Prediction with scikit-learn:", prediction) ```

参数详解

KNeighborsClassifier类有许多参数可供调整，以优化模型性能：

• n_neighbors: 最近邻的数量，默认为5。
• weights: 邻居的权重，可选uniform或distance，默认为uniform。
• algorithm: 计算最近邻的算法，可选auto、ball_tree、kd_tree或brute，默认为auto。
• leaf_size: BallTree或KDTree的叶子大小，默认为30。
• p: Minkowski距离的参数，默认为2（欧几里得距离）。
• metric: 用于计算距离的度量方法，默认为minkowski。
• n_jobs: 并行运行的任务数量，默认为1。

总结

通过本文，我们了解了KNN算法的基本原理和实现过程。虽然我们已经实现了一个简单的KNN算法，但在实际应用中，还需要考虑更多因素，如数据预处理、特征选择、模型评估等。希望本文能帮助读者更好地理解和应用KNN算法。

更多代码和资源可在以下链接查看：https://github.com/japsonzbz/ML_Algorithms

继续探索机器学习之旅，期待下次再见！