数据挖掘十大算法之 k-NN
原创
k-NN (k-nearest neighbor) 由 Cover 和 Hart 于 1968 年提出，属于机器学习算法中的监督学习算法，可以用来解决分类和回归问题。
k-NN 的工作原理
为了对 k-NN 算法有个直观的认识，我们看个例子：
有两类物体 A 和 B，它们在坐标轴中的分布如上图所示。现在来了一个未知类别的物体，由图中的正方形表示，我们该把它归为哪一类呢？k-NN 算法的工作原理是看离待分类物体最近的 k 个物体的类别，这 k 个物体的大多数属于那个类别，待分类物体也就属于那个类别。例如：当 k = 3 时，离待分类物体最近的 3 个物体中，有 1 个 A 类物体，2 个 B 类物体，所以待分类物体属于 B 类；当 k = 9 时，离待分类物体最近的 9 个物体中，有 5 个 A 类物体，4 个 B 类物体，所以待分类物体属于 A 类。由上面的例子可知，k-NN 的工作流程分为三步：
- 计算待分类物体和其他物体之间的距离。
- 选取距离待分类物体最近的 k 个物体。
- 这 k 个物体的大多数属于那个分类，待分类物体也就属于那个分类。距离的计算特征空间中两个实例点之间的距离反映了两个实例点的相似程度。距离越大，相似度越小；距离越小，相似度越大。k 近邻模型的特征空间一般是 n 维实数向量空间 R^n。使用的距离是欧式距离，但也可以是其他距离，如更一般的 L_p（L_p distance） 距离或闵可夫斯基距离（Minkowski distance）。 设特征空间 \chi 是 n 维实数向量空间 R^n，x_i，x_j \in \chi，x_i = (x_i^{(1)}, x_i^{(2)} ,..., x_i^{(n)})^T，x_j = (x_j^{(1)}, x_j^{(2)} ,..., x_j^{(n)})^T，x_i，x_j 的 L_p 距离定义为 L_p(x_i, y_i) = \Bigg(\displaystyle \sum^n_{l=1}|x_i^{(l)}-x_j^{(l)}|^p\Bigg)^\frac{1}{p}， p \geq 1， 当 p = 2时，称为欧式距离，即 L_2(x_i, y_i) = \Bigg(\displaystyle \sum^n_{l=1}|x_i^{(l)}-x_j^{(l)}|^2\Bigg)^\frac{1}{2}， 当 p = 1 时，称为曼哈顿距离，即 L_1(x_i, y_i) = \displaystyle \sum^n_{l=1}|x_i^{(l)}-x_j^{(l)}|， 当 p = \infty 时，它是各个坐标距离的最大值，即 L_\infty(x_i, y_j) = \mathop{max}\limits_{l}|x_i^{(l)}-x_j^{(l)}|， 称为切比雪夫距离。
k 值的选择
从上面的例子我们看到，k 值的选择会对结果产生重大的影响。同一个物体，如果 k 值选择的不同，结果可能完全不同。另外，k 值的选择也对模型的预测效果产生较大影响。如果 k 值选择的较小，只有较小邻域内的训练实例才会对预测结果起作用，这时整体模型变得复杂，容易发生过拟合；如果 k 值选择的较大，意味着距离输入实例较远的训练实例也会对预测结果起作用，这时整体模型变得简单，容易发生欠拟合。在应用中，一般采用交叉验证法来选取最优的 k 值。
决策规则
k 近邻法中往往采用多数表决的决策规则，也就是输入实例的 k 个近邻的多数类决定输入实例的类。
kd 树
在实现 k 近邻法时，为了找出距离输入实例最近的 k 个训练实例，最简单的方法便是线性扫描，这时要计算输入实例和每个训练实例的距离。当特征空间的维数以及训练集较大时，计算非常耗时。为了提高效率，减少不必要的计算，可以使用 kd 树来存储训练数据，并通过搜索 kd 树来减少计算量。
两个例子
鸢尾花的分类
鸢尾花的分类问题属于监督学习中比较经典的问题。鸢尾花有三个类别，分别为山鸢尾（Iris Setosa）、杂色鸢尾（Iris Versicolour）和维吉尼亚鸢尾（Iris Virginica）。每个类别的鸢尾花都有四个属性，分别是花萼长度（SepalLength）、花萼宽度（SepalWidth）、花瓣长度（PetalLength）以及花瓣宽度（PetalWidth）。鸢尾花的分类问题就是通过花萼长度、花萼宽度、花瓣长度以及花瓣宽度的值来对鸢尾花进行分类。下面我们通过 Scikit-learn 中的 k-NN 算法对鸢尾花进行分类。
- 导入库
import pandas as pd
from sklearn import metrics
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn.preprocessing import StandardScaler- 读取数据
iris_data = pd.read_csv('Iris.csv')- 将数据集分成训练数据集和测试数据集
y = iris_data['Species']
x = iris_data[['SepalLengthCm', 'SepalWidthCm', 'PetalLengthCm', 'PetalWidthCm']]
train_x, test_x, train_y, test_y = train_test_split(x, y, test_size=0.3, random_state=33)- 使用训练数据对模型进行训练，并使用得到的模型对测试数据进行测试。
knn = KNeighborsClassifier()
knn.fit(train_x, train_y)
predict_y = knn.predict(test_x)- 输出测试结果
print("KNN准确率: %.4lf" % accuracy_score(test_y, predict_y))- output
KNN准确率: 0.9556糖尿病的预测
糖尿病的预测是根据患者的一些信息来预测患者是否有糖尿病。下面我们通过 Scikit-learn 中的 k-NN 算法对患者是否患有糖尿病进行预测。
- 导入库
import pandas as pd
from sklearn import metrics
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn.preprocessing import StandardScaler- 读取数据
diabetes_data = pd.read_csv('diabetes.csv')- 对数据进行清洗，对于某列数据中的0值，使用这一列值的平均值进行填充。
diabetes_data.replace({
'Glucose': 0,
'BloodPressure': 0,
'SkinThickness': 0,
'BMI': 0,
'Insulin': 0
}, np.NaN, inplace=True)
glucose_mean = diabetes_data['Glucose'].mean()
blood_pressure_mean = diabetes_data['BloodPressure'].mean()
skin_thickness_mean = diabetes_data['SkinThickness'].mean()
bmi_mean = diabetes_data['BMI'].mean()
insulin_mean = diabetes_data['Insulin'].mean()
diabetes_data['Glucose'].replace(np.NaN, glucose_mean, inplace=True)
diabetes_data['BloodPressure'].replace(np.NaN, blood_pressure_mean, inplace=True)
diabetes_data['SkinThickness'].replace(np.NaN, skin_thickness_mean, inplace=True)
diabetes_data['BMI'].replace(np.NaN, bmi_mean, inplace=True)
diabetes_data['Insulin'].replace(np.NaN, insulin_mean, inplace=True)- 将数据集分成训练数据集和测试数据集。
y = diabetes_data['Outcome']
x = diabetes_data[['Pregnancies', 'Glucose', 'BloodPressure', 'SkinThickness', 'Insulin', 'BMI', 'DiabetesPedigreeFunction', 'Age']]
train_x, test_x, train_y, test_y = train_test_split(x, y, test_size=0.2, random_state=0)- 对数据进行规范化。
sc_x = StandardScaler()
train_x = sc_x.fit_transform(train_x)
test_x = sc_x.fit_transform(test_x)- 使用训练数据对模型进行训练，并使用得到的模型对测试数据进行测试。
knn = KNeighborsClassifier(n_neighbors=11, metric='euclidean', p=2, weights='uniform', algorithm='auto', leaf_size=30)
knn.fit(train_x, train_y)
predict_y = knn.predict(test_x)- 输出测试结果
print("KNN准确率: %.4lf" % accuracy_score(test_y, predict_y))- output
KNN准确率: 0.8052总结
本文介绍了 k -NN 的工作原理以及在实际问题中的应用。
数据下载
鸢尾花：https://www.kaggle.com/uciml/iris
糖尿病：https://www.kaggle.com/uciml/pima-indians-diabetes-database
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。