赞
踩
K近邻法(KNN)是一种基本的分类与回归方法。分类时,对于新的实例,根据与它最接近的k个训练实例的类别,通过多数表决等方式,进行预测。对于给定的训练集,当k值,距离度量和分类决策规则(统称三要素)确定后,基于k近邻法的模型就已经确定了。所以,它实际上利用训练集对特征向量空间进行划分,并没有显示的学习过程。k近邻法,符合我们基本的认知,即 “物以类聚,人以群分” ,一件事物的类别通常与它附近的事物具有相似性。
给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的k个实例,这k个实例的多数属于某个类(多数表决argmax),就把该输入实例分为这个类。
优点:易于实现,无需估计参数,无需训练,支持增量学习,能对超多边形的复杂决策空间建模
缺点:计算量较大,分析速度慢(因为要扫描全部训练样本并计算距离)
KNN模型由三个基本要素——距离度量、K值的选择和分类决策规则决定。根据选择的距离度量(如曼哈顿距离或欧氏距离),可计算测试实例与训练集中的每个实例点的距离,根据k值选择k个最近邻点,最后根据分类决策规则将测试实例分类。
如图1,根据欧氏距离,选择k=4个离测试实例最近的训练实例(红圈处),再根据多数表决的分类决策规则,即这4个实例多数属于“-类”,可推断测试实例为“-类”。
特征空间中的两个实例点的距离是两个实例点相似程度的反映。KNN模型使用的距离是欧式距离,但也可以是其他距离,如更一般的Lp距离或Minkowski距离。
设特征空间X是n维实数向量空间 R n R^n Rn, x i , x j ∈ X x_i,x_j∈X xi,xj∈X, x i = ( x i ( 1 ) , x i ( 2 ) , . . . , x i ( n ) ) , x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)}), xi=(xi(1),xi(2),...,xi(n)), x j = ( x j ( 1 ) , x j ( 2 ) , . . . , x j ( n ) ) , x_j=(x_j^{(1)},x_j^{(2)},...,x_j^{(n)}), xj=(xj(1),xj(2),...,xj(n)),
L p 距 离 L_p距离 Lp距离
L p ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ p ) 1 p L_p(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}} Lp(xi,xj)=(l=1∑n∣xi(l)−xj(l)∣p)p1
其中, p ≥ 1 p\geq1 p≥1
L 2 距 离 ( 欧 式 距 离 ) L_2距离(欧式距离) L2距离(欧式距离)
L 2 ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ 2 ) 1 2 L_2(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^2)^{\frac{1}{2}} L2(xi,xj)=(l=1∑n∣xi(l)−xj(l)∣2)21
L 1 距 离 ( 曼 哈 顿 距 离 — M a n h a t t a n d i s t a n c e ) L_1距离(曼哈顿距离—Manhattan\ distance) L1距离(曼哈顿距离—Manhattan distance)
L 1 ( x i , x j ) = ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ L_1(x_i,x_j)=\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}| L1(xi,xj)=l=1∑n∣xi(l)−xj(l)∣
当 p = ∞ p=∞ p=∞时,它是各个坐标距离的最大值,即
L ∞ ( x i , x j ) = m a x l ∣ x i ( l ) − x j ( l ) ∣ L_∞(x_i,x_j)=max_l|x_i^{(l)}-x_j^{(l)}| L∞(xi,xj)=maxl∣xi(l)−xj(l)∣
k值的选择会对k近邻法的结果产生重大影响。在应用中,k值一般取一个比较小的数值,通常采用交叉验证法来选取最优的k值。
k近邻法中的分类决策规则往往是多数表决,即由输入实例的k个邻近的训练实例中的多数类,决定输入实例的类。
输入:训练集
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
⋯
,
(
x
N
,
y
N
)
}
T= \Big \{ (x_1 ,y_1 ),(x_2,y_2 ),⋯,(x_N,y_N)\Big \}
T={(x1,y1),(x2,y2),⋯,(xN,yN)}
其中,
x
i
∈
X
⊆
R
n
x_i∈X ⊆ R^n
xi∈X⊆Rn为实例的特征向量,
y
i
∈
Y
=
(
c
1
,
c
2
,
.
.
.
,
c
k
)
y_i∈Y=(c_1,c_2,...,c_k)
yi∈Y=(c1,c2,...,ck)为实例的类别,i=1,2,…,N。
输出:实例x所属的类别y
① 根据给定的距离度量,在训练集T中找出与x最近邻的k个点,涵盖这k个点的x的领域记作 N k ( x ) N_k(x) Nk(x) 。
② 在
N
k
(
x
)
N_k(x)
Nk(x)中根据分类决策规则(如多数表决)决定x的类别y:
y
=
a
r
g
m
a
x
c
j
∑
x
i
∈
N
k
(
x
)
I
(
y
i
=
c
j
)
,
i
=
1
,
2
,
.
.
.
N
;
j
=
1
,
2
,
.
.
.
,
K
y=argmax_{c_j}\sum_{x_i\in N_k(x)}I(y_i=c_j),i=1,2,...N;j=1,2,...,K
y=argmaxcjxi∈Nk(x)∑I(yi=cj),i=1,2,...N;j=1,2,...,K
其中,
I
I
I为指示函数,即当
y
i
=
c
j
y_i=c_j
yi=cj时I为1,否则I为0。
【代码实现】
import numpy as np import pandas as pd import matplotlib.pyplot as plt %matplotlib inline from collections import Counter 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):#判别/预测输入X属于哪一类 # 取出n个点,先算前n个样本与待预测样本X的L2距离,并添加到列表中 knn_list = [] for i in range(self.n): dist = np.linalg.norm(X - self.X_train[i], ord=self.p)#Lp计算X与训练数据集中各个样本的Lp距离 knn_list.append((dist, self.y_train[i]))#将距离以及对应的类别添加到列表 #计算其余样本与待预测样本X的L2距离,若距离比列表中最大者小,则替换其最大者 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)#L2范数 if knn_list[max_index][0] > dist: knn_list[max_index] = (dist, self.y_train[i])#替换最大者 # 统计 knn = [k[-1] for k in knn_list]#提取knn_list中的最后一列即类别 count_pairs = Counter(knn)#求数组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)
案例一:使用KNN算法预测一个电影是爱情片还是动作片
下面表格是我们已有的数据集合,也就是训练样本集。这个数据集有两个特征,即打斗镜头,接吻镜头。试预测打斗镜头为101,接吻镜头为20的电影属于哪个类型。
电影名称 | 打斗镜头 | 接吻镜头 | 电影类型 |
---|---|---|---|
电影1 | 1 | 101 | 爱情片 |
电影2 | 5 | 89 | 爱情片 |
电影3 | 108 | 5 | 动作片 |
电影4 | 115 | 8 | 动作片 |
1、创建数据集
对于这些少量数据集的,我们可以定义创建数据集的函数:
def createDataSet():
#四组二维特征
X_train = np.array([[1,101],[5,89],[108,5],[115,8]])
#四组特征的标签
Y_train= ['爱情片','爱情片','动作片','动作片']
return X_train, Y_train
2、利用上述创建的模块预测
X_train, Y_train =createDataSet()
a=KNN(X_train, Y_train)
test = [101,20]
print('Test Point: {}'.format(a.predict(test)))
Test Point: 动作片
案例二:利用常用验证模型的鸢尾花数据集建立模型,并预测鸢尾花属于哪一类别
1、加载数据集,为各列命名
# data
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['label'] = iris.target#将特征名iris.target转换为label
df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']
df#查看数据集
2、选取前两个特征作为分类依据,划分训练集与测试集
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)
数据可视图,查看数据分布
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()
3、进行预测
clf = KNN(X_train, y_train)
clf.score(X_test, y_test)
test_point = [6.0, 3.0]
print('Test Point: {}'.format(clf.predict(test_point)))
Test Point: 1.0
4、可以将待预测的点画在训练集上的散点图上
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 也简称sklearn,提供了众多的机器学习方法
使用sklearn可以很方便地让我们实现一个机器学习算法。一个复杂度算法的实现,使用sklearn可能只需要调用几行API即可。所以学习sklearn,可以有效减少我们特定任务的实现周期。
KNneighborsClassifier参数说明:
KNeighborsClassifier提供了以一些方法供我们使用,如下图所示。
下面用sklearn中KNN模块实现上述的预测
clf_sk = KNeighborsClassifier()
clf_sk.fit(X_train, y_train)
clf_sk.score(X_test, y_test)
test_point = [6.0, 3.0]
clf_sk.predict([test_point])
array([1.])
实现k近邻法问题是如何对训练数据进行快速k近邻搜索,这点在特征空间的维数大及训练数据容量大时尤其必要。
k近邻法最简单的实现方法是线性扫描(linear scan),这时要计算输入实例与每一个训练实例的距离,当训练集很大时,计算非常耗时,这种方法是不行的。为了提高k近邻法搜索的效率,可以考虑使用特殊的结构存储训练数据,以减少计算距离的次数。 具体方法很多,下面介绍其中的kd树方法(kd树是存储k维空间数据的树结构,这里的k与k近邻法的k意义不同)。
kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。 kd树是二叉树,表示对k维空间的一个划分。构造kd树相当于不断利用垂直于坐标轴的超平面将k维空间划分,构成一些列的k维超矩形区域。设想一个最简单的情况(当k=1时),kd树就退化为二叉搜索树,我们可以以O(logn)的时间复杂度查找数据。
构造kd树的方法如下:构造根节点,使根结点对应于k维空间中包含所有实例点的超矩形区域;通过下面的递归方法,不断地对k维空间进行划分,生成子节点。在超矩形区域(结点)上选择一个坐标轴和在此坐标轴上的一个切分点,确定一个超平面,这个超平面通过选定的切分点并垂直于选定的坐标轴,将当前超矩形区域划分为左右两个子区域(子结点);这时,实例被分到两个子区域。重复此过程直到子区域没有实例时终止。在此过程中,将实例保存在相应的结点上。
这里有两个需要注意的问题:a. 如何选定坐标轴(维度);b. 如何选定切分点。对于问题a,我们通常选择数据最为分散的维度,即方差最大的维度,有时为了简单也可以循环地选择维度(j(mod k) + 1,其中j为结点的深度)。对于问题b,我们可以选择中位数作为切分点,这样得到的kd树是平衡的,但搜索效率未必是最优的。
构造kd树算法过程
构造平衡kd树
输入:k维空间数据集T={
x
1
,
x
2
,
⋯
,
x
N
x_1,x_2,⋯,x_N
x1,x2,⋯,xN},
其中
x
i
=
(
x
i
(
1
)
,
x
i
(
2
)
,
⋯
x
i
(
k
)
)
T
x_i=(x_i^{(1)},x_i^{(2)},⋯x_i^{(k)})^T
xi=(xi(1),xi(2),⋯xi(k))T,i=1,2,⋯,N;
输出:kd树。
(1)开始:构造根结点,根结点对应于包含T的k维空间的超矩形区域。
选择以 x ( 1 ) x^{(1)} x(1)为坐标轴,以T中所有的实例的 x ( 1 ) x^{(1)} x(1)坐标的中位数为切分点,将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 x ( 1 ) x^{(1)} x(1)垂直的超平面实现。
由根结点生成深度为1的左、右子结点:左子结点对应左边 x ( 1 ) x^{(1)} x(1)小于切分点的子区域,右子结点对应于坐标 x ( 1 ) x^{(1)} x(1)大于切分点的子区域。
将落在切分超平面上的实例点保存在根结点。
(2)重复:
(3)直到两个子区域没有实例存在时停止,从而形成kd树的区域划分。
为了便于理解,下面结合实例进行讲述kd树的构造过程。给定一个二维空间的数据集:T = { (2, 3), (5, 4), (9, 6), (4, 7) ,(8, 1), (7, 2) }。
根结点对应包含数据集T的矩形,选择 x ( 1 ) x^{(1)} x(1)轴(采用循环选择维度的方法,因为根结点的深度为0,根据公式算出此时的维度为1,即x轴),6个数据点的 x ( 1 ) x^{(1)} x(1)轴坐标的中位数为7(事实上5也可以,因为有偶数个数字,中位数本应为6,这里没有选6是由于结点必须选择一个存在的实例),以 x ( 1 ) x^{(1)} x(1)=7将空间划分为左右两个子矩形({ (2, 3), (5, 4), (4, 7) }和{ (8, 1), (9, 6) });
l
=
j
(
m
o
d
k
)
+
1
=
1
(
m
o
d
2
)
+
1
=
2
l=j(modk)+1=1(mod2)+1=2
l=j(modk)+1=1(mod2)+1=2
接着左矩形以
x
(
2
)
x^{(2)}
x(2)=4分为两个子矩形({ (2, 3) }和{ (4, 7) }),右矩形以
x
(
2
)
x^{(2)}
x(2)=6分为两个子矩形({ (8, 1) }和{})。如此递归,最后得到如图2-1所示的特征空间和如图2-2所示的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 下一分割维度序号$l=j(modk)+1$ # 递归的创建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)
将此算法用于上述案列
data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]
kd = KdTree(data)
preorder(kd.root)
[7, 2]
[5, 4]
[2, 3]
[4, 7]
[9, 6]
[8, 1]
利用kd树可以省去对大部分数据点的搜索,从而减少搜索的即使是算量。这里以最近邻(k=1)为例加以叙述,同样的方法可以应用到k近邻。
算法(用kd树的最近邻搜索)
输入:已构造的kd树,目标点x;
输出:x的最近邻
(1)在kd树中找到包含目标点x的叶结点:从根结点出发,递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标,则移动到左子结点,否则移动到右子结点。直到子结点为叶节点为止。
(2)以此叶节点为“当前最近点”
(3)递归地向上回退,在每个结点进行以下操作:
(a)如果该结点保存的实例点比当前最近点距离目标点更近,则以该实例点为“当前最近点”
(b)当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点对应的区域是否与以目标点为球心,以目标点与“当前最近点”间的距离为半径的超球体相交。
(4)当回退到根结点时,搜索结束。最后的“当前最近点”即为x的最近邻点。
【代码实现】
# 对构建好的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")) # 从根节点开始递归
案例:利用上面构造的kd树求点x=(3,4.5)的最近邻点。
ret = find_nearest(kd, [3,4.5])
print (ret)
Result_tuple(nearest_point=[2, 3], nearest_dist=1.8027756377319946, nodes_visited=4)
如果实例点是随机分布的,kd树搜索的平均计算复杂度是 O ( l o g N ) O(logN) O(logN),这里N是训练实例数。kd树更适合用于训练实例数远大于空间维数时的k近邻搜索,当空间维数接近训练实例数时,它的效率会迅速下降,几乎接近线性扫描。
利用kd树k近邻算法总代码:
''' 构造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 下一分割维度序号$l=j(modk)+1$ # 递归的创建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的前序遍历,非必要部分,主要是为了查看kd树 def preorder(root): print(root.dom_elt) if root.left: # 节点不为空 preorder(root.left) if root.right: preorder(root.right) ''' 搜索Kd树,查找最近邻邻点(k=1) ''' # 对构建好的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")) # 从根节点开始递归
kd树更适合用于训练实例数远大于空间维数时的k近邻搜索,下面看一下大量训练数据下,查找最近邻点所耗费时间
from time import clock from random import random # 产生一个k维随机向量,每维分量值在0~1之间 def random_point(k): return [random() for _ in range(k)] # 产生n个k维随机向量 def random_points(k, n): return [random_point(k) for _ in range(n)] N = 400000 t0 = clock() kd2 = KdTree(random_points(3, N)) # 构建包含四十万个3维空间样本点的kd树 ret2 = find_nearest(kd2, [0.1,0.5,0.8]) # 四十万个样本点中寻找离目标最近的点 t1 = clock() print ("time: ",t1-t0, "s") print (ret2)
time: 7.038252100001046 s
Result_tuple(nearest_point=[0.10284308148070764, 0.5056170533243651, 0.7922743068211113], nearest_dist=0.009965978900691678, nodes_visited=59)
时间还是挺快的,说明kd树搜索适合大量训练数据集。
优点
缺点:
计算复杂性高;空间复杂性高;
样本不平衡问题(即有些类别的样本数量很多,而其它样本的数量很少);
一般数值很大的时候不用这个,计算量太大。但是单个样本又不能太少,否则容易发生误分。
最大的缺点是无法给出数据的内在含义。
两点间距离公式不能提供足够的信息
维度灾难
另:
from collections import Counter
a = [1,4,2,3,2,3,4,2]
b = Counter(a) #求数组中每个数字出现了几次
print(b)
print( b[2]) #计算每个元素出现了几次
Counter({2: 3, 4: 2, 3: 2, 1: 1})
3
>>> from collections import namedtuple >>> Student = namedtuple('Student', ('name', 'age', 'sex')) >>> tom = Student('Tom', '12', 'meal') # 按位置指定其中各项 >>> lisa = Student(name='Lisa', age=12, sex='female') # 采用关键字来指定 >>> tom.name # 通过属性名称访问 'Tom' >>> tom.sex 'meal' >>> lisa.name 'Lisa' >>> lisa.age 12 >>> lisa[0] 'Lisa' >>> lisa[1] 12 >>> [ i for i in lisa ] ['Lisa', 12, 'female'] >>> len(lisa) 3
参考资料:
1、李航《统计学习方法》
2、周志华《机器学习》
3、Peter Harrington《Machine Learing in Action》
4、https://github.com/fengdu78/lihang-code/blob/master/%E7%AC%AC03%E7%AB%A0%20k%E8%BF%91%E9%82%BB%E6%B3%95/3.KNearestNeighbors.ipynb
未完待续
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。