原标题：kNN算法和决策树

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

kNN

kNN算法的原理很简单，就是将新数据的特征与样本集中相应的特征进行比较，然后提取将样本集中特征最相似的数据的分类标签作为新数据的标签，一般的，只选取数据集中前k个最相似的元素，因此该算法被称为kNN，通常k取不大于20的整数。
下面看书上给出的实例：

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))

首先，定义了一个createdataset()函数用来生成数据样本集，然后定义的classify()函数有4个输人参数:用于分类的输人向量是inx，输入的训练样本集为dataset, 标签向量为labels 最后的参数k表示用于选择最近邻居的数目其中标签向量的元素数目和矩 阵如dataset的行数相同。
dataset.shape[0]返回dataset数组的第二维，也就是二维数组的行数，此例中为4，接下来的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 logdef 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_entdef 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))

keys()函数用于返回一个字典所有的键。不难看出label_counts是一个将类别与属于该类别的样本数作为键值对的字典。实际上，对于data_set上的一个随机变量x，x为yes所属类的概率为2/5，x为no的概率为3/5，那么x的熵为-(2/5)*lb(2/5)-(3/5)*lb(3/5)，也就是上面代码中计算的data_set的熵。（在这个实例中，yes和no对应的是最终分类标签（是否为鱼），前面的1，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和决策树算法感觉还是很简单的，希望之后的学习内容也是如此

免责声明：本文来自互联网新闻客户端自媒体，不代表本网的观点和立场。

合作及投稿邮箱：E-mail:editor@tusaishared.com