一般k鄰近

import numpy as np import matplotlib.pyplot as pltclass K_near:def __init__(self,X,Y,K=5,p=2):self.K = Kself.X = np.array(X)self.Y = np.array(Y)self.p = pdef cauclate_dis(self,x1,x2):return np.sum(abs(x1-x2)**self.p)**(1/self.p)def predict(self,x):result=[]for x_ in x:dis_set = [self.cauclate_dis(i,x_) for i in self.X]dis_max = dis_set[:self.K]dis_label = self.Y[:self.K]for i,j in zip(dis_set[self.K:],self.Y[self.K:]):max_dis = max(dis_max)if i < max_dis:min_index = dis_max.index(max_dis)dis_max[min_index] = idis_label[min_index] = jdict = {}for i in dis_label:if i not in dict.keys():dict[i]=1else:dict[i] +=1sort_ = sorted(dict.items(), key=lambda dict:dict[1],reverse = True)predict_ = sort_[0][0]result.append(predict_)return resultdef main():x = [[1,2],[2,3],[2,2],[2,1],[9,7],[10,2],[2,5]]y = [1,1,1,-1,-1,-1,1]x_predict = [[4,2],[8,4]]plt.show()K_near_ = K_near(x,y,3,2)print(K_near_.predict(x_predict))positive_ = np.array(x)[np.array(y) == 1]negetive_ = np.array(x)[np.array(y) == -1]plt.scatter([k[0] for k in positive_],[k[1] for k in positive_],c='r',label='1')plt.scatter([k[0] for k in negetive_], [k[1] for k in negetive_],c='b',label='0')plt.scatter([k[0] for k in x_predict], [k[1] for k in x_predict], c='g', label='0')plt.show()if __name__ == '__main__':main()######result###################### /usr/bin/python3 /Users/zhengyanzhao/PycharmProjects/tongjixuexi/K_near [1, -1]

平衡kd樹構(gòu)造與鄰近搜索

搜索用遍歷結(jié)點(diǎn)代替實(shí)現(xiàn)，怪我太菜了，不知道原算法中另一結(jié)點(diǎn)的超平面到點(diǎn)的距離該如何計(jì)算。

import numpy as np import matplotlib.pyplot as pltclass Node:def __init__(self,values=None,left=None,right=None,layers=None,index=None):self.values = valuesself.left = leftself.right = rightself.layers = layersself.index = indexdef get_layer(self):return self.layersdef get_index(self):return self.indexclass Build_Kdtree:def __init__(self,X):self.X = Xself.feature_dim = len(X[0])self.root = Node(layers=0)self.closest_x_true = []self.closest_dis_true = []def bulid_tree(self):def return_mid_data(x,layer):if len(x) == 0:return None,None,None,Noneelse:sample_num = len(x)cut_feature_index = layer % self.feature_dimx.sort(key=lambda x:x[cut_feature_index])mid = sample_num // 2mid_value = x[mid]left_x = x[:mid]right_x = x[mid+1:]return mid_value,cut_feature_index,left_x,right_xdef create_tree(root,x,layer):if len(x) == 1:root.values = x[0]root.layers = layerroot.index = Noneroot.left = Noneroot.right = Noneelse:mid_value,cut_feature_index,left_x,right_x = return_mid_data(x,layer)root.values = mid_valueroot.layers = layerroot.index = cut_feature_indexif left_x:root.left = Node()create_tree(root.left,left_x,layer+1)if right_x:root.right = Node()create_tree(root.right,right_x,layer+1)create_tree(self.root,self.X,0)def print_tree(self):root = self.rootdef pre_order(root):if root:print(root.layers,root.index,root.values)pre_order(root.left)pre_order(root.right)pre_order(root)def cauclate_dis(self,x1,x2,p=2):x1 = np.array(x1)x2 = np.array(x2)return np.sum(abs(x1-x2)**p)**(1/p)def search_leave(self,x,k):def search(x,root):if root:closest_x = root.valuesclosest_dis = self.cauclate_dis(closest_x,x)if len(self.closest_x_true)<k:self.closest_x_true.append(closest_x)self.closest_dis_true.append(closest_dis)elif closest_dis<max(self.closest_dis_true):self.closest_dis_true[self.closest_dis_true.index(max(self.closest_dis_true))] = closest_disself.closest_x_true[self.closest_dis_true.index(max(self.closest_dis_true))] = closest_xif root.right:search(x,root.right)if root.left:search(x,root.left)root = self.rootif len(x) != self.feature_dim:raise IndexErrorsearch(x,root)# def search_nearest_leave(x,root):# while root:# if root.left is None and root.right is None:# break# if root.left is None and root.right is not None:# root = root.right# break# if root.left is not None and root.right is None:# root = root.left# break# if x[root.index] <= root.values[root.index]:# root = root.left# else:# root= root.right# closest_x = root.values# closest_dis = self.cauclate_dis(closest_x,x)# return closest_x,closest_dis,root## closest_x, closest_dis,root = search_nearest_leave(x,root)# closest_x_true = closest_x# closest_dis_true = closest_disdef main():x=[[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]kdtree = Build_Kdtree(x)kdtree.bulid_tree()kdtree.print_tree()predict_x = [6.9,6]kdtree.search_leave(predict_x,2)print(kdtree.closest_x_true,kdtree.closest_dis_true)plt.scatter([k[0] for k in x], [k[1] for k in x], c='g')plt.scatter(predict_x[0],predict_x[1],c='b')plt.scatter([k[0] for k in kdtree.closest_x_true], [k[1] for k in kdtree.closest_x_true],c='r')plt.show()if __name__ == '__main__':main()######result######################## /usr/bin/python3 /Users/zhengyanzhao/PycharmProjects/tongjixuexi/kd_search_tree 0 0 [7, 2] 1 1 [5, 4] 2 None [2, 3] 2 None [4, 7] 1 1 [9, 6] 2 None [8, 1] [[5, 4], [9, 6]] [2.7586228448267445, 2.0999999999999996]

總結(jié)

以上是生活随笔為你收集整理的统计学习方法第三章作业：一般k邻近、平衡kd树构造、kd树邻近搜索算法代码实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。