机器学习笔记
前言
章节目录
k近邻算法
k近邻模型
模型
距离度量
k值选择
分类决策规则
k近邻法的实现: KDTree（涉及二叉树，难）
构造KDTree
搜索KDTree
导读
kNN是一种基本分类与回归方法，这里仅讨论分类问题中的k邻近法；
多数表决规则等价于0-1损失函数下的经验风险最小化，支持多分类， 有别于前面的感知机算法
kNN的k和KDTree的k含义不同
KDTree是一种存储k维空间数据的树结构，KDTree是平衡二叉树；书中的KDTree搜索实现的时候针对了一种k=1的特殊的情况，实际是最近邻搜索
KDTree的搜索问题分为k近邻查找和范围查找，一个是已知k，求点集范围，一个是已知范围，求里面有k个点。范围查找问题在维度高的时候复杂度非常高，不太推荐用KDTree做范围查找。
最近邻算法
k=1的情形，称为最近邻算法。书中后面的分析都是按照最近邻做例子，这样不用判断类别，可以略去一些细节。
k近邻模型
算法
输入:
\( T=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\} \)，\( x_i\in \mathcal{X}\subseteq{\bf{R}^n} \), \( y_i\in\mathcal{Y}=\{c_1,c_2,\dots, c_k\} \); 实例特征向量 \( x \)
输出: 实例所属的 \( y \)
步骤:
根据指定的距离度量，在 \( T \) 中查找 \( x \) 的最近邻的 \( k \) 个点，覆盖这 \( k \) 个点的 \( x \) 的邻域定义为 \( N_k(x) \)；
在 \( N_k(x) \) 中应用分类决策规则决定 \( x \) 的类别 \( y \)；
公式表示为： \[ y=\arg\max_{c_j}\sum_{x_i\in N_k(x)}I(y_i=c_j), i=1,2,\dots,N, j=1,2,\dots,K \]
这里提到了k近邻模型的三要素，距离度量、 \( k \) 值选择和分类决策规则。
距离度量
特征空间中的两个实例点的距离是两个实例点相似程度的反映；距离越近(数值越小)， 相似度越大。
Lp距离以及python代码实现
p=1曼哈顿距离
p=2欧氏距离
p=∞ 切比雪夫距离 (L∞距离)
\[ L_p(x_i, x_j) = \left( \sum_{l=1}^{n} \left| x_{i}^{(l)} - x_{j}^{(l)} \right|^p \right)^{\frac{1}{p}} \]
k值选择
关于k大小对预测结果的影响，书中给的参考文献是ESL，这本书还有个先导书叫ISL。
通过交叉验证选取最优k，算是超参数
二分类问题，k选择奇数有助于避免平票
分类决策规则
误分类率
\[ \frac{1}{k} \sum_{x_i \in N_k(x)} I(y_i \neq c_i) = 1 - \frac{1}{k} \sum_{x_i \in N_k(x)} I(y_i = c_i) \]
如果分类损失函数是0-1损失，误分类率最低即经验风险最小。
实现
KD树
kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。
kd树是二叉树，表示对k维空间的一个划分（partition）。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。
构造kd树的方法如下：
构造根结点，使根结点对应于k维空间中包含所有实例点的超矩形区域；通过下面的递归方法，不断地对k维空间进行切分，生成子结点。在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域 （子结点）；这时，实例被分到两个子区域。这个过程直到子区域内没有实例时终止（终止时的结点为叶结点）。在此过程中，将实例保存在相应的结点上。
通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴上的中位数 （median）为切分点，这样得到的kd树是平衡的。注意，平衡的kd树搜索时的效率未必是最优的。
KDTree的构建是一个递归的过程
注意: KDTree左边的点比父节点小，右边的点比父节点大。
这里面有提到，KDTree搜索时效率未必是最优的，这个和样本分布有关系。随机分布样本KDTree搜索(这里应该是最近邻搜索)的平均计算复杂度是O($log N$)，空间维数K接近训练样本数N时，搜索效率急速下降，几乎O($N$)
构造平衡KDTree算法
输入：k维空间数据集
\[ T = \{x_1, x_2, \ldots, x_N\}, \] \[ x_{i} = \left( x_{i}^{(1)}, x_{i}^{(2)}, \ldots, x_{i}^{(k)} \right)^{\mathrm{T}}, \quad i = 1, 2, \ldots, N; \]
输出：kd树；具体步骤：
开始：构造根结点，根结点对应于包含 \( T \) 的 \( k \) 维空间的超矩形区域；
选择 \( x^{(1)} \) 为坐标轴，以 \( T \) 中所有实例的 \( x^{(1)} \) 坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 \( x^{(1)} \) 垂直的超平面实现；
由根结点生成深度为 \( 1 \) 的左、右子结点：左子结点对应坐标 \( x^{(1)} \) 小于切分点的子区域，右子结点对应于坐标 \( x^{(1)} \) 大于切分点的子区域；
将落在切分超平面上的实例点保存在根结点；
重复：对深度为 \( j \) 的结点，选择 \( x^{(1)} \) 为切分的坐标轴，\( l = j \mod k + 1 \)，以该结点的区域中所有实例的 \( x^{(1)} \) 坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 \( x^{(1)} \) 垂直的超平面实现；
由该结点生成深度为 \( j + 1 \) 的左、右子结点：左子结点对应坐标 \( x^{(1)} \) 小于切分点的子区域，右子结点对应坐标 \( x^{(1)} \) 大于切分点的子区域；
将落在切分超平面上的实例点保存在该结点；
直到两个子区域没有实例存在时停止。从而形成kd树的区域划分。
# kd-tree每个结点中主要包含的数据结构如下
class KdNode(object):
def __init__(self, dom_elt, split, left, right):
self.dom_elt = dom_elt # k维向量节点(k维空间中的一个样本点)
self.split = split # 整数（进行分割维度的序号）
self.left = left # 该结点分割超平面左子空间构成的kd-tree
self.right = right # 该结点分割超平面右子空间构成的kd-tree
class KdTree(object):
def __init__(self, data):
k = len(data[0]) # 数据维度
def CreateNode(split, data_set): # 按第split维划分数据集exset创建KdNode
if not data_set: # 数据集为空
return None
# key参数的值为一个函数，此函数只有一个参数且返回一个值用来进行比较
# operator模块提供的itemgetter函数用于获取对象的哪些维的数据，参数为需要获取的数据在对象中的序号
#data_set.sort(key=itemgetter(split)) # 按要进行分割的那一维数据排序
data_set.sort(key=lambda x: x[split])
split_pos = len(data_set) // 2 # //为Python中的整数除法
median = data_set[split_pos] # 中位数分割点
split_next = (split + 1) % k # cycle coordinates
# 递归的创建kd树
return KdNode(
median,
split,
CreateNode(split_next, data_set[:split_pos]), # 创建左子树
CreateNode(split_next, data_set[split_pos + 1:])) # 创建右子树
self.root = CreateNode(0, data) # 从第0维分量开始构建kd树,返回根节点
# KDTree的前序遍历
def preorder(root):
print(root.dom_elt)
if root.left: # 节点不为空
preorder(root.left)
if root.right:
preorder(root.right)
# 对构建好的kd树进行搜索，寻找与目标点最近的样本点：
from math import sqrt
from collections import namedtuple
# 定义一个namedtuple,分别存放最近坐标点、最近距离和访问过的节点数
result = namedtuple("Result_tuple",
"nearest_point nearest_dist nodes_visited")
def find_nearest(tree, point):
k = len(point) # 数据维度
def travel(kd_node, target, max_dist):
if kd_node is None:
return result([0] * k, float("inf"),
0) # python中用float("inf")和float("-inf")表示正负无穷
nodes_visited = 1
s = kd_node.split # 进行分割的维度
pivot = kd_node.dom_elt # 进行分割的“轴”
if target[s] <= pivot[s]: # 如果目标点第s维小于分割轴的对应值(目标离左子树更近)
nearer_node = kd_node.left # 下一个访问节点为左子树根节点
further_node = kd_node.right # 同时记录下右子树
else: # 目标离右子树更近
nearer_node = kd_node.right # 下一个访问节点为右子树根节点
further_node = kd_node.left
temp1 = travel(nearer_node, target, max_dist) # 进行遍历找到包含目标点的区域
nearest = temp1.nearest_point # 以此叶结点作为“当前最近点”
dist = temp1.nearest_dist # 更新最近距离
nodes_visited += temp1.nodes_visited
if dist < max_dist:
max_dist = dist # 最近点将在以目标点为球心，max_dist为半径的超球体内
temp_dist = abs(pivot[s] - target[s]) # 第s维上目标点与分割超平面的距离
if max_dist < temp_dist: # 判断超球体是否与超平面相交
return result(nearest, dist, nodes_visited) # 不相交则可以直接返回，不用继续判断
#----------------------------------------------------------------------
# 计算目标点与分割点的欧氏距离
temp_dist = sqrt(sum((p1 - p2)**2 for p1, p2 in zip(pivot, target)))
if temp_dist < dist: # 如果“更近”
nearest = pivot # 更新最近点
dist = temp_dist # 更新最近距离
max_dist = dist # 更新超球体半径
# 检查另一个子结点对应的区域是否有更近的点
temp2 = travel(further_node, target, max_dist)
nodes_visited += temp2.nodes_visited
if temp2.nearest_dist < dist: # 如果另一个子结点内存在更近距离
nearest = temp2.nearest_point # 更新最近点
dist = temp2.nearest_dist # 更新最近距离
return result(nearest, dist, nodes_visited)
return travel(tree.root, point, float("inf")) # 从根节点开始递归k近邻查找
KNN查找已知查询点 \( p \)，树当前节点 \( o \)，近邻数目 \( k \)；可以用一个优先队列存储最优的 \( k \) 个点，每次比对回溯节点是否比当前最优点更优的时候，就只需用当前最优中距离 \( p \) 最远的节点来对比，而这个工作对于优先队列来说是 \( O(1) \)。
python代码实现
# 距离度量的函数构建 import math from itertools import combinations -------------------------------------------------- def L(x, y, p=2): # x1 = [1, 1], x2 = [5,1] if len(x) == len(y) and len(x) > 1: sum = 0 for i in range(len(x)): sum += math.pow(abs(x[i] - y[i]), p) return math.pow(sum, 1 / p) else: return 0
同样借助鸢尾花数据构建一个完整的代码模型：
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from collections import Counter
# data
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]])
df.columns # Index(['sepal length', 'sepal width', 'petal length',
'petal width', 'label'], dtype='object')
plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')
plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()
data = np.array(df.iloc[:100, [0, 1, -1]])
X, y = data[:,:-1], data[:,-1]
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
class KNN:
def __init__(self, X_train, y_train, n_neighbors=3, p=2):
# parameter: n_neighbors 临近点个数
# parameter: p 距离度量
self.n = n_neighbors
self.p = p
self.X_train = X_train
self.y_train = y_train
def predict(self, X):
# 取出n个点
knn_list = []
for i in range(self.n):
dist = np.linalg.norm(X - self.X_train[i], ord=self.p)
knn_list.append((dist, self.y_train[i]))
for i in range(self.n, len(self.X_train)):
max_index = knn_list.index(max(knn_list, key=lambda x: x[0]))
dist = np.linalg.norm(X - self.X_train[i], ord=self.p)
if knn_list[max_index][0] > dist:
knn_list[max_index] = (dist, self.y_train[i])
# 统计
knn = [k[-1] for k in knn_list]
count_pairs = Counter(knn)
#max_count = sorted(count_pairs, key=lambda x: x)[-1]
max_count = sorted(count_pairs.items(), key=lambda x: x[1])[-1][0]
return max_count
def score(self, X_test, y_test):
right_count = 0
n = 10
for X, y in zip(X_test, y_test):
label = self.predict(X)
if label == y:
right_count += 1
return right_count / len(X_test)
clf = KNN(X_train, y_train)
clf.score(X_test, y_test) # 1.0
test_point = [6.0, 3.0]
print('Test Point: {}'.format(clf.predict(test_point)))
# Test Point: 1.0
plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')
plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')
plt.plot(test_point[0], test_point[1], 'bo', label='test_point')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()
scikit-learn实例
from sklearn.neighbors import KNeighborsClassifier clf_sk = KNeighborsClassifier() clf_sk.fit(X_train, y_train) clf_sk.score(X_test, y_test)
n_neighbors: 临近点个数
p: 距离度量
algorithm: 近邻算法，可选{'auto', 'ball_tree', 'kd_tree', 'brute'}
weights: 确定近邻的权重
习题3.1
参照图3.1，在二维空间中给出实例点，画出k为1和2时的k近邻法构成的空间划分，并对其进行比较，体会k值选择与模型复杂度及预测准确率的关系。
%matplotlib inline
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
data = np.array([[5, 12, 1], [6, 21, 0], [14, 5, 0], [16, 10, 0], [13, 19, 0],
[13, 32, 1], [17, 27, 1], [18, 24, 1], [20, 20,
0], [23, 14, 1],
[23, 25, 1], [23, 31, 1], [26, 8, 0], [30, 17, 1],
[30, 26, 1], [34, 8, 0], [34, 19, 1], [37, 28, 1]])
X_train = data[:, 0:2]
y_train = data[:, 2]
models = (KNeighborsClassifier(n_neighbors=1, n_jobs=-1),
KNeighborsClassifier(n_neighbors=2, n_jobs=-1))
models = (clf.fit(X_train, y_train) for clf in models)
titles = ('K Neighbors with k=1', 'K Neighbors with k=2')
fig = plt.figure(figsize=(15, 5))
plt.subplots_adjust(wspace=0.4, hspace=0.4)
X0, X1 = X_train[:, 0], X_train[:, 1]
x_min, x_max = X0.min() - 1, X0.max() + 1
y_min, y_max = X1.min() - 1, X1.max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.2),
np.arange(y_min, y_max, 0.2))
for clf, title, ax in zip(models, titles, fig.subplots(1, 2).flatten()):
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
colors = ('red', 'green', 'lightgreen', 'gray', 'cyan')
cmap = ListedColormap(colors[:len(np.unique(Z))])
ax.contourf(xx, yy, Z, cmap=cmap, alpha=0.5)
ax.scatter(X0, X1, c=y_train, s=50, edgecolors='k', cmap=cmap, alpha=0.5)
ax.set_title(title)
plt.show()
习题3.2
利用例题3.2构造的$kd$树求点$x=(3,4.5)^T$的最近邻点。
import numpy as np
from sklearn.neighbors import KDTree
train_data = np.array([(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)])
tree = KDTree(train_data, leaf_size=2)
dist, ind = tree.query(np.array([(3, 4.5)]), k=1)
x1 = train_data[ind[0]][0][0]
x2 = train_data[ind[0]][0][1]
print("x点的最近邻点是({0}, {1})".format(x1, x2))
# x点的最近邻点是(2, 3)最长的一篇，累！
2024-08-21 23:57:12
哈哈哈，写的太好了https://www.lawjida.com/
《王者天下》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/58870.html
《暴力云与送子鹳》动画片高清在线免费观看：https://www.jgz518.com/xingkong/11461.html
《满洲候选人》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/81236.html
《满洲候选人》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/81236.html
真好呢
不错不错，我喜欢看 www.jiwenlaw.com
想想你的文章写的特别好https://www.ea55.com/
想想你的文章写的特别好https://www.237fa.com/
怎么收藏这篇文章？