机器学习--KNN算法，决策树

KNN算法

1. 基本概念
   KNN算法即K临近算法，是一个基础的分类算法，非常有效并且易于掌握。采用测量不同特征值之间的距离方法进行分类。
   优点：精度高、对异常值不敏感、无数据输入假定。
   缺点：计算复杂度高、空间复杂度高。
   适用数据范围：数值型和标称型
2. 原理
   对于KNN算法我们需要给定一个样本数据集，并且样本集中每个数据都存在标签，即我们知道样本集中每个数据与所属分类的对应关系。对新输入没有标签的实例，在训练数据集中找到与该实例最邻近的 k 个实例，这 k 个实例的多数属于某个类，就把该输入实例分为这个类。
   具体是测定实例坐标与样本集每个样本坐标的欧式距离，然后选出距离最小的k个点，统计这k个点钟出现频率最多的样本特征作为实例的特征。这个比较好理解

简单的示例判别特征：

#### KNN文件
from numpy import *
import operator
###################### 简单的提供样本标签与坐标的函数
def CreatDataSet():
    group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels=['A','A','B','B']
    return group,labels
###################### 主要函数，inX为需要分类的向量，dataset是样本集，labels是样本集对应的标签集，k是用于选择最近邻居的个数，一般来说k不大于20
def classify(inX,dataSet,labels,k):
    dataSetSize=dataSet.shape[0]
    diffMat=tile(inX,(dataSetSize,1))-dataSet
    sqDiffMat=diffMat**2
    sqDistances=sqDiffMat.sum(axis=1)
    distances=sqDistances**0.5
    sortedDistIndicies=distances.argsort()
    classCount={}
    for i in range(k):
        voteIlabel=labels[sortedDistIndicies[i]]
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
    sortedClassCount=sorted(classCount.items(),    ###python3.5中iteritems变为items
                            key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

• CreatDataSet()
  用来生成简单数据集的函数，这里给出了4个样本数据坐标和其对应的样本特征（A,或者B）在实际应用中，数据集是通过文件导入的。接下来调用该函数来生成我们需要示范的简单数据集。

import KNN
group,labels=KNN.CreatDataSet()
print(group)
print(labels)
###############Result
[[1.  1.1]
 [1.  1. ]
 [0.  0. ]
 [0.  0.1]]
['A', 'A', 'B', 'B']

在坐标图上反映该4个样本点如下：

• classify(inX,dataSet,labels,k)
  该函数是主要函数，参数中inX是需要区分特征的实例的坐标，dataset是样本集坐标，即对应上面的group，labels是对应样本集坐标的标签。k是用于选择最近邻居的个数，一般来说k不大于20。给定参数之后开始利用KNN算法的原理（原理在上）进行计算

###测试classify函数
import KNN
group,labels=KNN.CreatDataSet()
print(KNN.classify([0,0],group,labels,3))
####################Result
B

可以看到，对于坐标点为（0,0）的实例，当取K为3时，给出的实例的特征为B。这与坐标图中能看出的结果是一致的。

实际应用
KNN算法在实际应用时还有考虑以下几点

• k值的选取：
  k值得选取直接影响到KNN算法对实例判别的结果，例如样本集个数为10，取k值为10的话，对于任何实例坐标，给出的判别都是样本集中频率最多的数。再k值小于样本集个数的情况下，k值过大过小都会使得算法准确度降低

• 样本集的处理
  示例中的样本集是自己创建的，实际的样本集是通过文件导入的，而且可能具有多个维度的坐标。这样就设计到这些样本数据的归一化处理。来消除特征之间量级不同导致的影响

• 测试算法
  实际应用中，为了了解算法的准确程度，需要对KNN算法增加一个训练样本集合进行准确性的判断，该训练样本集中样本有明确的坐标和特征。利用KNN算法对于该样本集中样本坐标进行判断，如果KNN算法给出的特征与样本不同，则标记为一个错误，最后统计错误就行得到KNN算法对于该实例的判断准确度

决策树

• 基本概念
  KNN算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内
  在含义，决策树的主要优势就在于数据形式非常容易理解。
  
  上图即为一个简单的决策树（流程图形式）。
  我们需要知道就是如何根据样本集数据和特征来通过决策树划分样本集
  决策树学习通常包括 3 个步骤：特征选择、决策树的生成和决策树的修剪。

###伪代码
def createBranch():
    检测数据集中的所有数据的分类标签是否相同:
        If so return 类标签
        Else:
            寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征）
            划分数据集
            创建分支节点
                for 每个划分的子集
                    调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中
            return 分支节点

这里特征的选择设置到信息熵的概念：
信息熵：

• 熵（entropy）： 熵指的是体系的混乱的程度，在不同的学科中也有引申出的更为具体的定义，是各领域十分重要的参量，如化学反应很多就设置到熵增熵减。
• 信息论（information theory）中的熵（香农熵）： 是一种信息的度量方式，表示信息的混乱程度，也就是说：信息越有序，信息熵越低。
• 信息增益（information gain）： 在划分数据集前后信息发生的变化称为信息增益。
  这里决策树划分数据集的原则是：将无序的数据变得更加有序。选择信息增益最大的特征来划分数据集。

##对于给定的数据集计算香农熵
from math import log
###############################Python计算香农熵
def CalcShannonEnt(dataset):
    numEntries=len(dataset)
    labelCounts={}
    for featVec in dataset:
        currentLabel=featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
            labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

例如，对于海洋生物数据与特征

#################根据上表生成简单的数据集
def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    return dataSet, labels

###########################计算上述数据集的香农熵
import trees
group,labels=trees.CreatDataSet()
print(trees.CalcShannonEnt(group))
#########################Result
0.9287712379549449

划分数据集
这是构造决策树中最重要的一步。前面有关信息熵的概念就是为该步划分数据集做准备

##########################################按照给定特征划分数据集
def SplitDataSet(dataSet,axis,value):
    retDataSet=[]
    for featVec in dataSet:
        if featVec[axis]==value:
            reducedFeatVec=featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet
##########################################遍历数据集，循环ShannonEnt(),和SplitDataSet()函数，找到最好的特征划分方式
def ChooseBestFeatureToSplit(dataSet):
    numFeatures=len(dataSet[0])-1
    baseEntropy=CalcShannonEnt(dataSet)
    bestInfoGain=0.0
    bestFeature=-1
    for i in range(numFeatures):
        featList=[example[i] for example in dataSet]
        uniqueVals=set(featList)
        newEntropy=0.0
        for value in uniqueVals:
            subDataSet=SplitDataSet(dataSet,i,value)
            prob=len(subDataSet)/float(len(dataSet))
            newEntropy+=prob*CalcShannonEnt(subDataSet)
        infoGain=baseEntropy-newEntropy
        if(infoGain>bestInfoGain):
            bestInfoGain=infoGain
            bestFeature=i
    return bestFeature

• SplitDataSet(dataSet,axis,value):
  根据给定的axis，value来划分数据集。

• ChooseBestFeatureToSplot(dataSet)：
  对划分好的数据集进行香农熵的计算，来找出最好的特征划分方式

import trees
##########################上述函数对鱼群例子的测试
group,labels=trees.CreatDataSet()
print(trees.SplitDataSet(group,0,0))
print(trees.ChooseBestFeatureToSplit(group))
##########################Result
[[1, 'no'], [1, 'no']]
1

决策树的创建

########################################################选择出现次数最多的一个结果
def MajorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]
#########################################################生成决策树
def CreateTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    if len(dataSet[0]) == 1:
        return MajorityCnt(classList)
    bestFeat = ChooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel: {}}
    del (labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = CreateTree(SplitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

######################生成决策树代码测试
import trees
group,labels=trees.CreatDataSet()
#print(trees.SplitDataSet(group,0,0))
#print(trees.ChooseBestFeatureToSplit(group))
mytree=trees.CreateTree(group,labels)
print(mytree)
#####################Result
{'flippers': {0: 'no', 1: {'no surfacing': {0: 'no', 1: 'yes'}}}}