算法原理算法实现
算法原理在现实生活判断一样东西是否复合我们的预期，大多数情况都是判断是与否，也就是一个二分类的问题。
例如：在周志华老师的西瓜书中提到的选西瓜的例子，判断色泽，响度等。但我们不会同时判断所有的特征，而是会一个特征一个特征的去判断，就很像是一个二叉树。
原来到这就没有了。
但是就通过这道理，写出代码是有几个困难的点。
1.怎么样的划分是好的划分
2.如何实现划分
3.划分到什么样的程度结束。
问题一： 解决方法是借鉴与信息论中熵（克劳德 克劳德 提出）的概念。熵在物理学上表示事务的混乱程度。假设事件一，有一个六面都是一的骰子，那出现一就是必然情况。事件二，有一个正常的骰子有六个面都不相同。
那么，我们投出这枚骰子时，事件一的答案我们是十分确定，事件二不确定性高，也就是说事件二的信息量大。类比到分类中，我们是希望这种信息小，这样子我们的答案就会更加的确定。
在这里给出信息熵的定义：
l
(
x
i
)
=
−
l
o
g
2
p
(
x
i
)
l(x_i)=-log_2p(x_i)
l(xi)=−log2p(xi)
就如骰子的例子我们一个骰子有多种可能的时候，就会有多个x，此时采用期望来解决。
H
=
−
∑
i
=
1
n
p
(
x
i
)
l
o
g
2
p
(
x
i
)
H=-sum_{i=1}^np(x_i)log_2p(x_i)
H=−i=1∑np(xi)log2p(xi)
其中p表示事件x发生的概率
至于为什么采用负对数来表示信息，我试图揣测大佬的意图：第一，能采用初等函数来描述。第二 ，计算方便，能够很好的表示信息混乱度和函数的相关性。毕竟这玩意儿非常具体信息增量如何表示也说不太清楚，就大致方向对就行了。
问题二： 将会在代码中进行解释如何划分。
问题三： 看到树，很快能想到的就是二叉树，二叉树建立的过程是一个递归的过程，以此类推，建立一课可以分类的树也是一个递归的过程。那么首要考虑的是递归的终点是什么？其次是返回的内容是什么？
递归终点：没有特征可以进行划分。
返回内容：划分节点的内容，构建成一个字典方便新来一个数据可以通过查字典的方法进行获得所属类别。
算法实现创建数据集
def createDataset():
dataset = [
[1,1,'yes']
,[1,1,'yes']
,[1,0,'no']
,[0,1,'no']
,[0,1,'no']
]
label = ['no surfacing','flippers']
return dataset,label
dataset, label = createDataset()
第一步计算熵的公式
def calShannonEnt(dataset):
num = len(dataset)
#对每个标签进行计数，计算每个标签会出现的概率（prob）
labels = {}
for vec in dataset:
vec_label = vec[-1]
labels[vec_label] = labels.get(vec_label,0)+1
shannonEnt = 0.0
for key in labels:
prob = labels[key]/num
shannonEnt += -prob*math.log(prob,2)
return shannonEnt
第二步对数据集进行划分,这里我们选择某个特征之后抽取出某一类的数据
def splitDataSet(dataset,axis,value):
# axis 是某一类的特征
# vlaue 是该特征对应特征
subdataset = []
for vec in dataset:
if vec[axis] == value:
temp = []
temp.extend(vec[:axis])
temp.extend(vec[axis+1:])
subdataset.append((temp))
return subdataset
splitDataSet(list(dataset),0,0)
第三步通过分类后的熵的变化选择，信息增益（划分前后，熵变化的值）最高的特征。增益信息越高越好。
def chooseBestFeature(dataset):
numFeature = len(dataset[0]) - 1
baseEntropy = calShannonEnt(dataset)
bestInfoGain = 0 ; indexFeature = -1
for i in range(numFeature):
featurelist = [example[i] for example in dataset]
uniquefeature = set(featurelist)
newEntropy = 0.0
for value in uniquefeature:
subdataset = splitDataSet(dataset,i,value)
prob = len(subdataset)/float(len(dataset))
newEntropy *= prob*calShannonEnt(subdataset)
infoGain = baseEntropy - newEntropy
if infoGain > bestInfoGain:
bestInfoGain = infoGain
indexFeature = i
return indexFeature
chooseBestFeatureToSplit(dataset)
现在已经使用完了所有的特征，如果叶子结点里面全是同一个类别的话，那叶子节点就是这个类别的。但是如果现在在同一个叶子结点中仍旧有不同类别的数据时候，将采用少服从多数的方法。否则无法对这个叶子结点的类别进行打标签。
def majority(classlist):
classCount = {}
for vote in classlist:
classlist[vote] = classCount.get(vote,0)+1
sorted_class = sorted(classCount.items(),key= lambda s:s[1],reverse=True)
return sorted_class[0][0]
第四步现在已经有划分节点的步骤和给每个叶子结点的标签，最后就是通过上述划分过程进行建的过程。
def creatTree(dataset, feature_name):
classlist = [example[-1] for example in dataset] #这里我们将数据的标签是放在最后一列的位置
if classlist.count(classlist[0]) == len(classlist):
return classlist[0] #叶子结点中所有数据都是一个类别的
if len(dataset[0]) == 1:
return majority(dataset) #叶子结点中有多个类别，选择最多的
beststep = chooseBestFeature(dataset)
beststep_name = feature_name[beststep]
myTree = {beststep_name : {}} # 构建划分的字典
del feature_name[beststep]
step_value = [example[beststep] for example in dataset]
unique_step_value = set(step_value) #确保特征所有的都会被划分到
for value in unique_step_value:
subfeature = feature_name[:]
myTree[beststep_name][value] = creatTree(splitDataSet(dataset,beststep,value),subfeature)
return myTree
**优点：**算法本身比较好理解，就是实现略微复杂，对于输入也没有一定要求是数值类型，文本类型也是可以作为输入。
**缺点：**面对同一特征中存在大量可能的时候，也会存在一定的问题，整体分类效果不是非常强。
每种算法都存在自己的优缺点，不存在一种无敌的算法。‼️
本算法实现的是ID3
