kNN算法和决策树

的整数。

下面看书上给出的实例：

from numpy import *

import operator

def createdataset():

group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])

labels=['a','a','b','b']

return group,labels

group,labels=createdataset()

def classify(inx,dataset,labels,k):

datasetsize=dataset.shape[0]

diffmat=tile(inx,(datasetsize,1)) - dataset

sqdiffmat=diffmat**2

sqdistance=sqdiffmat.sum(axis=1)

distance=sqdistance**0.5 #计算距离，也就是比较特征

sorteddist=distance.argsort()

classcount={}

for i in range(k):

votelabel=labels[sorteddist[i]]

classcount[votelabel]=classcount.get(votelabel,0)+1 #为字典classcount创建前k个最近的数据的标签对应出现次数的键值对

sortedclasscount=sorted(classcount.items(),key=operator.itemgetter(1),reverse=True)

return sortedclasscount[0][0]

print(classify([0,0],group,labels,3))

个输人参数:用于分类的输人向量是inx，输入的训练样本集为dataset, 标签向量为labels 最后的参数k表示用于选择最近邻居的数目其中标签向量的元素数目和矩阵如dataset的行数相同。

，接下来的tile函数将inx数组的第二维重复了四次，第一维重复一次，也就是将inx数组从一行变成了4行，每一行都是原来的inx数组，这样就与dataset数组的行列数是一样的，用于接下来计算inx与每个数据样本的距离，这里的sqdiffmat.sum(axis=1)表示每一行的数组求和，这里返回一个长度为4的一维数组，每一个元素都是sqdiffmat对应一行的和，下面的argsort()函数将distance中的元素从小到大排列，提取其对应的index(索引)，然后输出到sorteddist。

然后创建了一个空字典classcount，在接下来的for循环中为字典classcount创建了前k个最近的数据的标签对应出现次数的键值对

接下来有一个sorted函数，它的语法如下：

sorted(iterable, key=None, reverse=False)

iterable – 可迭代对象。

key – 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。

reverse – 排序规则，reverse = True 降序， reverse = False 升序（默认）。

items函数返回字典中可遍历的(键, 值) 元组数组。

operator.itemgetter函数的作用是获取对象哪些维的数据，参数是表示维的序号。

在这个例子中这个sorted函数的作用就是对字典classcount所生成的元组数组按照外汇返佣标签对应出现的次数进行降序排序，最后整个classify函数返回的sortedclasscount[0][0]就是出现次数最多的标签，以此作为待划分数据的分类标签。最后运行结果为 b 。

决策树

决策树伪代码如下：

检测数据集中的每个子项是否属于同一分类：

If so return 类标签；

Else

寻找划分数据集的最好特征

划分数据集

创建分支节点

for 每个划分的子集

调用决策树函数并增加返回结果到分支节点中

return 分支节点

下面根据伪代码一步一步实现

在划分数据集之前之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择，集合信息的度量方式称为香农熵或者简称为熵，熵定义为信息的期望值。

如果待分类的事务可能划分在多个分类之中，则符号x的信息定义为 l(x)=-lb(p(x))，p(x)为选择该分类的概率。

要计算熵，则需要计算所有类别所有可能值包含的信息期望值。下面给出书上的计算熵代码：

from math import log

def c_shannon_ent(data_set):

num_entries=len(data_set)

label_counts={}

for feat_vec in data_set:

current_label=feat_vec[-1]

if current_label not in label_counts.keys():

label_counts[current_label]=0

label_counts[current_label]+=1

shannon_ent=0.0

for key in label_counts:

prob=float(label_counts[key])/num_entries

shannon_ent-=prob*log(prob,2)

return shannon_ent

def create_data_set():

data_set=[[1,1,'yes'],[1,0,'no'],[0,1,'no'],[1,1,'yes'],[0,1,'no']]

labels=['no surfacing','flippers']

return data_set,labels

my_data,labels=create_data_set()

print(c_shannon_ent(my_data))

，0是用于判断的特征数据，所以按照yes和no的分类来计算data_set的熵）熵越高，代表数据的无序程度就越高。

划分数据集

先看看书上的对于给定特征划分数据集的代码：

def split_data_set(data_set,axis,value):

ret_data_set=[]

for feat_vec in data_set:

if feat_vec[axis]==value:

reduced_feat_vec=feat_vec[:axis]

reduced_feat_vec.extend(feat_vec[axis+1:])

ret_data_set.append(reduced_feat_vec)

return ret_data_set

这段代码还是很容易看懂的，首先创建了一个新列表，然后对于符合所输入的特征的数据就截取到 reduced_feat_vec中（把特征值截掉了），然后再将 reduced_feat_vec添入新建的列表ret_data_set中作为一个元素，这样就得到了一个符合所选特征值的数据集ret_data_set。

选择最好的数据集划分方式

def choose_best_feature_to_split(data_set):

num_features=len(data_set[0])-1

base_entropy=c_shannon_ent(data_set)

best_info_gain=0.0;best_feature=-1

for i in range(num_features):

feat_list=[example[i] for example in data_set]

unique_vals=set(feat_list)

new_entropy=0.0

for value in unique_vals:

sub_data_set=split_data_set(data_set,i,value)

prob=len(sub_data_set)/float(len(data_set))

new_entropy+=prob*c_shannon_ent(sub_data_set)

info_gain=base_entropy-new_entropy

if(info_gain>best_info_gain):

best_info_gain=info_gain

best_feature=i

return best_feature

如果上面都看懂了，那么看懂这一段代码也不会难的。

首先用一个变量存储特征总数，一个变量存储初始熵，然后每选一个特征，就用一个集合unique_vals存储该特征所有可能的取值，再根据这个对该特征进行分类并且计算分类后的熵，最后计算出信息增益info_gain，然后从所有特征值中找出信息增益最大的一个，输出该特征值。为什么找信息增益最大的呢？上面说到在划分数据集之前之后信息发生的变化称为信息增益，也就是划分前后的熵之差，而熵越高，表明无序程度越大，信息增益实际上就是无序程度减少的程度，越大就表明分类后的无序程度越小。

构建决策树

def major_cnt(class_list):

class_count={}

for vote in class_list:

if vote not in class_count.keys():class_count[vote]=0

class_count[vote]+=1

sorted_class_count=sorted(class_count.items,key=operator.itemgetter,reverse=True)

return sorted_class_count[0][0]

def create_tree(data_set,labels):

class_list=[example[-1] for example in data_set]

if class_list.count(class_list[0])==len(class_list):

return class_list[0]

if len(data_set[0])==1:

return major_cnt(class_list)

best_feat=choose_best_feature_to_split(data_set)

best_feat_label=labels[best_feat]

my_tree={best_feat_label:{}}

del(labels[best_feat])

feat_values=[example[best_feat] for example in data_set]

unique_vals=set(feat_values)

for value in unique_vals:

sub_labels=labels[:] my_tree[best_feat_label][value]=create_tree(split_data_set(data_set,best_feat,value),sub_labels)

return my_tree

第一个函数和Knn里的一段代码是很相似的，这里不再多说。

第二个函数有两个参数：数据集data_set和标签labels，标签对该算法来说不是必须的，只是能表明数据的内在意义。

create_tree中第一个if表示如果数据都是同一类就返回该类别，第二个if表示特征用完后数据仍然不是同一类则返回出现次数最多的分类标签。然后就是选取最好的特征进行分类，再对分好类的数据集执行同样的操作，最后生成整颗树，代码还是相当简单的。

最后给出完整的代码：

from math import log

import operator

def c_shannon_ent(data_set):

num_entries=len(data_set)

label_counts={}

for feat_vec in data_set:

current_label=feat_vec[-1]

if current_label not in label_counts.keys():

label_counts[current_label]=0

label_counts[current_label]+=1

shannon_ent=0.0

for key in label_counts:

prob=float(label_counts[key])/num_entries

shannon_ent-=prob*log(prob,2)

return shannon_ent

def create_data_set():

data_set=[[1,1,'yes'],[1,0,'no'],[0,1,'no'],[1,1,'yes'],[0,1,'no']]

labels=['no surfacing','flippers']

return data_set,labels

def split_data_set(data_set,axis,value):

ret_data_set=[]

for feat_vec in data_set:

if feat_vec[axis]==value:

reduced_feat_vec=feat_vec[:axis]

reduced_feat_vec.extend(feat_vec[axis+1:])

ret_data_set.append(reduced_feat_vec)

return ret_data_set

def choose_best_feature_to_split(data_set):

num_features=len(data_set[0])-1

base_entropy=c_shannon_ent(data_set)

best_info_gain=0.0;best_feature=-1

for i in range(num_features):

feat_list=[example[i] for example in data_set]

unique_vals=set(feat_list)

new_entropy=0.0

for value in unique_vals:

sub_data_set=split_data_set(data_set,i,value)

prob=len(sub_data_set)/float(len(data_set))

new_entropy+=prob*c_shannon_ent(sub_data_set)

info_gain=base_entropy-new_entropy

if(info_gain>best_info_gain):

best_info_gain=info_gain

best_feature=i

return best_feature

def major_cnt(class_list):

class_count={}

for vote in class_list:

if vote not in class_count.keys():class_count[vote]=0

class_count[vote]+=1

sorted_class_count=sorted(class_count.items,key=operator.itemgetter,reverse=True)

return sorted_class_count[0][0]

def create_tree(data_set,labels):

class_list=[example[-1] for example in data_set]

if class_list.count(class_list[0])==len(class_list):

return class_list[0]

if len(data_set[0])==1:

return major_cnt(class_list)

best_feat=choose_best_feature_to_split(data_set)

best_feat_label=labels[best_feat]

my_tree={best_feat_label:{}}

del(labels[best_feat])

feat_values=[example[best_feat] for example in data_set]

unique_vals=set(feat_values)

for value in unique_vals:

sub_labels=labels[:] my_tree[best_feat_label][value]=create_tree(split_data_set(data_set,best_feat,value),sub_labels)

return my_tree

data,labels=create_data_set()

print(create_tree(data,labels))

输出结果：{‘no surfacing’:{0:‘no’,1:{‘flippers’:{0:‘no’,1:‘yes’}}}}

Knn和决策树算法感觉还是很简单的，希望之后的学习内容也是如此

原文链接：https://blog.csdn.net/weixin_45772508/article/details/102994629

巴特西

kNN算法和决策树

最新文章

热门文章