赞
踩
1 定义
给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的 k 个实例,这 k 个实例的多数属于某个类,就把该输入实例分为这个类。
2 距离度量
k 近邻法常用的距离度量是欧氏距离,公式如下:
3 k 值的选择
如果选择比较小的k值,预测结果会对近邻的实例点比较敏感,如果近邻的实例点是噪声点,会导致预测出错,也就是容易发生过拟合。 如果选择比较大的k值,距离待预测实例点较远的实例点(不相似的)也会对预测起作用,使预测失误。在实际应用中k值一般取一个比较小的数值,通常采用交叉验证来选取最优的k值。
关于kd树的讲解 推荐看知乎上的一篇文章 讲解很详细
【数学】kd 树算法之详细篇
作者 宏观经济算命椰
https://zhuanlan.zhihu.com/p/23966698
下面是代码实现
数据来源于和鲸社区
因为数据中大多数特征值是离散的 并且是以自然语言的形式呈现的 比如
OnlineSecurity有三种取值No,Yes,No internet service,可以用LabelEncoder来编码 结果是以数字0,1,2分别代表这三种类型 对所有值是离散类型的特征都采用这种方法来处理
def datapreprocessing(data):#数据预处理 le = LabelEncoder() data['gender'] = le.fit_transform(data['gender'].values) data['Partner'] = le.fit_transform(data['Partner'].values) data['Dependents'] = le.fit_transform(data['Dependents'].values) data['PhoneService'] = le.fit_transform(data['PhoneService'].values) data['MultipleLines'] = le.fit_transform(data['MultipleLines'].values) data['InternetService'] = le.fit_transform(data['InternetService'].values) data['OnlineSecurity'] = le.fit_transform(data['OnlineSecurity'].values) data['OnlineBackup'] = le.fit_transform(data['OnlineBackup'].values) data['DeviceProtection'] = le.fit_transform(data['DeviceProtection'].values) data['TechSupport'] = le.fit_transform(data['TechSupport'].values) data['StreamingTV'] = le.fit_transform(data['StreamingTV'].values) data['StreamingMovies'] = le.fit_transform(data['StreamingMovies'].values) data['Contract'] = le.fit_transform(data['Contract'].values) data['PaperlessBilling'] = le.fit_transform(data['PaperlessBilling'].values) data['PaymentMethod'] = le.fit_transform(data['PaymentMethod'].values) data['Churn'] = le.fit_transform(data['Churn'].values) print(data) data.to_csv('Customer-Churn.csv')#
TotalCharges这一列有空白值 首先用0填充缺失值,以把这一列的数据类型由字符串转换为浮点型 之后求出这一列的平均值来取代为0的值
df=read_data("Customer-Churn.csv")#读数据
df['TotalCharges'] = df['TotalCharges'].replace(" ", "0")#TotalCharges中有空格
df['TotalCharges'] = pd.to_numeric(df['TotalCharges'])
TotalCharges = []
for i in range(df.shape[0]):
TotalCharges.append(float(df.loc[i, 'TotalCharges'])) # 将字符串数据转化为浮点型加入到数组之中
avg=np.var(TotalCharges)
df['TotalCharges'] = df['TotalCharges'].replace(0, avg)#用均值填充缺失值
划分特征和标签 并对数据进行标准化处理
def prepare_data(df):#数据预处理
ndarray_data = df.values
X=df.iloc[:,2:21]#数据切片
Y=df.iloc[:,21]
print(X)
#特征值标准化\n"
minmax_scale = preprocessing.MinMaxScaler(feature_range=(0, 1))
X = minmax_scale.fit_transform(X)
Y = Y.replace(0, -1)
return X , Y
KNN模型
class Node: def __init__(self, isvisit, left,right,X,split,label):#是否访问过,左子树,右子树,特征坐标,切分轴,标签 self.isvisit = isvisit self.left = left self.right = right self.X=X self.split=split self.label=label class KNN:#基于kd树进行k近邻搜索的KNN算法 def __init__(self,k,data,label): self.k=k # 找多少个近邻 #self.data=data self.stack=[] self.root=self.create_kdtree(data,0,label) #kd树根结点 def create_kdtree(self,data,split,label): #print("split="+str(split)) len = data.shape[0] # 求出datas长度方便找中位数 if len==0: return None data = data[np.argsort(data[:, split])]#按照划分的那一维度进行排序 # print(data) # print("******************") dimension=data.shape[1]#求出数据维度 #print("dimension=" +str(dimension)) print() mid=int(len/2) #中位数 if len%2==0: mid=mid-1 left=data[0:mid,:] #左孩子 llabel=label[0:mid,:] now=data[mid:mid+1,:]#当前结点 nlabel = label[mid:mid+1,:] #print(nlabel[0][0]) right=data[mid+1:,:] #右孩子 rlabel= label[mid+1:,:] #print("now: ") # print(now) node=Node(False,None,None,now[0],split,nlabel[0][0]) # print(node.X) node.left=self.create_kdtree(left,(split+1)%dimension,llabel) node.right=self.create_kdtree(right,(split+1)%dimension,rlabel) return node def pre_order(self,node):#先序遍历 if node!=None: print(node.X) self.pre_order(node.left) self.pre_order(node.right) def in_order(self, node): # 中序遍历 if node != None: self.in_order(node.left) print(node.X) self.in_order(node.right) def search_k_neighbor(self,X): #寻找某个点的k个邻居结点 L=[]#存放k个邻居结点的列表 node=self.root #从根节点开始遍历 Lmax=0 maxi=0 node = self.search_leaf_node(node, X) # 首先寻找叶子节点 node.isvisit = True #设置为已访问 Lmax= self.EuclideanDistance(X, node.X) L.append(node) while len(self.stack)!=0 : node=self.stack.pop() if node.isvisit==False: #如果这个结点没有被访问过 node.isvisit=True dist=self.EuclideanDistance(X,node.X) if len(L)<self.k:#如果L中不足k个结点直接放入 if Lmax<dist: #有需要的话调整最大距离 Lmax=dist maxi=len(L) L.append(node) elif dist<Lmax:#当前点到 X的距离 比L中结点到X的最大距离 要小 说明需要更新L L.pop(maxi) L.append(node) Lmax,maxi= self.max_dist(L,X) split=node.split if abs(X[split]-node.X[split]) < Lmax:#从另一支出发 left=node.left right=node.right if left!=None and left.isvisit==False: node=left node = self.search_leaf_node(node, X) # 首先寻找叶子节点 node.isvisit = True dist=self.EuclideanDistance(X,node.X) if len(L) < self.k: # 如果L中不足k个结点直接放入 if Lmax < dist: Lmax = dist maxi = len(L) L.append(node) elif dist < Lmax: # 当前点到 X的距离 比L中结点到X的最大距离 要小 说明需要更新L L.pop(maxi) L.append(node) Lmax, maxi = self.max_dist(L, X) if right!=None and right.isvisit==False: node=right node = self.search_leaf_node(node, X) # 首先寻找叶子节点 node.isvisit = True dist = self.EuclideanDistance(X, node.X) if len(L) < self.k: # 如果L中不足k个结点直接放入 if Lmax < dist: Lmax = dist maxi = len(L) L.append(node) elif dist < Lmax: # 当前点到 X的距离 比L中结点到X的最大距离 要小 说明需要更新L L.pop(maxi) L.append(node) Lmax, maxi = self.max_dist(L, X) return L def max_dist(self,L,X): Lmax=0 maxi=0 for i in range(len(L)): dist=self.EuclideanDistance(L[i].X,X) if dist>Lmax: Lmax=dist maxi=i return Lmax,maxi def EuclideanDistance(self,X1,X2):#欧氏距离计算公式 dist=0 for (x1,x2) in zip(X1,X2): dist+=(x1-x2)**2 return dist**0.5 def search_leaf_node(self,node,X): while (node.left != None) or (node.right != None): # 不是叶子节点 self.stack.append(node) if node.left == None: # 单分支结点 node = node.right elif node.right == None: # 单分支结点 node = node.left else: split = node.split # 以哪个轴做分割的 nodeX = node.X if X[split] > nodeX[split]: node = node.right else: node = node.left return node def predict(self,X_test,Y_test): n = X_test.shape[0] # 共有多少条数据 num = 0 # 正确预测的数据有多少 for i in range(X_test.shape[0]): X = X_test[i] Y = Y_test[i] L=self.search_k_neighbor(X) positive =0 negative =0 for node in L: if node.label==1: positive+=1 else: negative+=1 if positive>=negative: label=1 else: label=-1 if label==Y[0]: num+=1 return num / n
执行过程
df=read_data("Customer-Churn.csv")#读数据 df['TotalCharges'] = df['TotalCharges'].replace(" ", "0")#TotalCharges中有空格 df['TotalCharges'] = pd.to_numeric(df['TotalCharges']) TotalCharges = [] for i in range(df.shape[0]): TotalCharges.append(float(df.loc[i, 'TotalCharges'])) # 将字符串数据转化为浮点型加入到数组之中 avg=np.var(TotalCharges) df['TotalCharges'] = df['TotalCharges'].replace(0, avg)#用均值填充缺失值 print(df.shape)#(7043, 21) #print(df.dtypes)#查看各列数据的数据类型 X,Y=prepare_data(df) train_size = int(len(X) * 0.7)#划分训练集与测试集 X_train = np.array(X[:train_size]) print(X_train.shape) Y_train=np.array(Y[:train_size]) Y_train.resize([Y_train.shape[0],1]) X_test = np.array(X[train_size:]) Y_test =np.array( Y[train_size:]) Y_test.resize([Y_test.shape[0],1]) knn=KNN(10,X_train,Y_train) print(knn.predict(X_test,Y_test))
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。