在线性模型中我们认为事物的属性是具有权重的,即对事物类别判断产生的影响力,在线性模型中我们将这样的权重视为线性函数的参数,由优化方法求出,该过程也称为线性模型的“学习”过程。

在线性模型中,样例的属性是连续的数值型数据,若属性是离散的呢(离散的标签,离散的数值)

例如,下列西瓜数据(数据来源于,周志华的《机器学习》):

编号	色泽	根蒂	敲击	纹理	脐部	触感	好瓜
0	青绿	蜷缩	浊响	清晰	凹陷	硬滑	是
1	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	是
2	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	是
3	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	是
4	浅白	蜷缩	浊响	清晰	凹陷	硬滑	是
5	青绿	稍蜷	浊响	清晰	稍凹	软粘	是
6	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	是
7	乌黑	稍蜷	浊响	清晰	稍凹	硬滑	是
8	乌黑	稍蜷	沉闷	稍糊	稍凹	硬滑	否
9	青绿	硬挺	清脆	清晰	平坦	软粘	否
10	浅白	硬挺	清脆	模糊	平坦	硬滑	否
11	浅白	蜷缩	浊响	模糊	平坦	软粘	否
12	青绿	稍蜷	浊响	稍糊	凹陷	硬滑	否
13	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	否

此时,我们怎么来度量属性的权重呢 ?

回想一下,我们在买西瓜的时候,我们会先敲一敲西瓜,如果敲声通透,我们认为它是好瓜的概率很高,若它的根蒂是蜷缩的,那么它一定是好瓜。我们人,为什么会得出这样的结论呢?

在人的学习中,经验占据大部分,通过多次实践产生经验,是人学习的方式。那么,上述选瓜的方法就是一个经验,即在多次尝试中,具有,敲声通透的瓜很多都是好瓜,若还具有根蒂蜷缩那么都是好瓜,这是一个统计过程。

以上述思想,我们可以得出一个粗浅的模型:

1.挨个选择事物的属性

2.统计该属性不同形式,或取值(敲声浑浊,敲声沉闷,敲声通透),统计他们的正反例数量

3.若出现全为正例,或全为反例,则得出结果(是,否)

4.若不是全正例,或全反例,则在当前属性的基础上,返回步骤1

上述模型可以用树结构存贮,该模型是可以使用的

但是我们挨个选择属性,忽略了属性对事物的判断的影响力,我们可能使用属性触感(西瓜),无论哪种触感的西瓜都是一半好瓜,一半不好的瓜,这种属性就没有任何的意义,那我们用什么度量方式,对属性提供的信息(对判断有用的信息)的多少呢?

1948年,香农提出的“香农熵”,解决了对信息的量化度量问题。

信息熵的公式如下:

可以看到,信息熵是从统计概率的特征得来的,和我们的思路一样嘛(哈哈),关于信息熵的更多知识请参考信息论相关书籍。

可以看出样例中某类样本占比越大,即p(x)越大,信息熵越小,数据的纯度越高。

我们希望每次使用的属性对数据进行划分,能使得数据的信息熵下降最大(纯度提升最大)

我们可以分别计算所有属性的信息熵,信息熵最小的属性,是最优选择。

因为每个属性有不同的取值 ,若定义数据集D,我们使用属性a进行划分,a属性有v个取值{a1, a2, a3, ..., av},则每个取值对应一个数据集Dv,我们可以计算每个取值的信息熵,再加起来,就得到了,在属性a的信息熵,如下:

但是每个属性取值,在数据集中的占比是不一样的,为了消除这样的统计误差,我们在计算信息熵时,乘以该取值所占的比例。

我们计算所有属性的信息熵,找出其中最小值,并使用该属性对数据分类,每使用一个属性,则不再使用该属性,直到使用完所有的属性,模型就做好了。

但是在各类机器学习的书中用到这个公式,信息增益:

计算每个属性的信息增益,信息增益最大的属性选为最佳分类属性,对于当前判断的数据集D,其Ent(D)是一个常数,当后面的式子取最小值时,信息增益最大,所以和我们的推导是一样的。

 那么根据我们的构想,我们开始实现吧,数据使用上面的西瓜数据集:

相关数据集和源代码已上传到我的资源()

读取数据:

我使用的数据文件是一个.xlsx文件,大家可以使用.txt文件,在上传的资源中都有

def loaddataset(filename):
	wb = xlrd.open_workbook(filename)
	ws = wb.sheet_by_name('Sheet1')
	dataset = []
	for r in range(ws.nrows):
		co1 = []
		for c in range(1, ws.ncols):
			co1.append(ws.cell(r,c).value)
		dataset.append(co1)
		
	#记录所有的属性名
	attribute_name = dataset.pop(0)
	del(attribute_name[-1])
	return dataset, attribute_name

dataset:

[['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'], ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'], ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'], ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'], ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'], ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '是'], ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '是'], ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '是'], ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '否'], ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '否'], ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '否'], ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '否'], ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '否'], ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '否'], ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '否'], ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '否'], ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '否']]

attribute_name:

['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']

计算信息熵:

def EntD(dataset):
	#对正例数量计数
	count = 0
	for i in dataset:
		if i[-1] == '是':
			count += 1
 
	#计算正反例所占比例
	p0 = 1 - count / len(dataset)
	p1 = 1 - p0
 
	#当占比为0时,根据信息熵的公式趋近于正无穷
	#这里我们用999代替正无穷
	if p0 == 0:
		entd0 = 999
		entd1 = 0
	elif p1 == 0:
		entd0 = 0
		entd1 = 999
	else:
		entd0 = -p0 * math.log(p0, 2)
		entd1 = -p1 * math.log(p1, 2)
	return entd0 + entd1

我们计算一下整体数据集的信息熵,结果如下:

0.9975025463691153
[Finished in 0.3s]

计算属性的信息熵:

   一:对某个属性的不同取值的数据进行统计

#n表示统计的属性的位置
def statistics(dataset, n):
	#记录统计结果
	count = {}
	for i in dataset:
		if i[n] not in count:
			#列表第一个位置为正例个数,第二个位置是反例个数
			if i[-1] == '是':
				count[i[n]] = [1, 0]
			else:
				count[i[n]] = [0, 1]
		else:
			if i[-1] == '是':
				count[i[n]][0] += 1
			else:
				count[i[n]][1] += 1
	return count

我们对数据集的纹理属性统计一下,纹理是第 4个属性,n=3(从0开始):

{'清晰': [7, 2], '稍糊': [1, 4], '模糊': [0, 3]}
[Finished in 0.3s]

表示纹理清晰的正例有7个,反例有2个。。。 

 

二:计算各个属性取值的信息熵

def EntDv(count):
	#记录结果
	entdv = []
	for i in count:
		p0 = count[i][1] / sum(count[i])
		p1 = count[i][0] / sum(count[i])
 
		#根据信息熵的定义,占比为0是应该是正无穷,占比为1应该是0
		#但是我们认为在该情况下,我们可以忽略该取值的信息对属性整体信息量的影响
		#所以出现这种情况时,该取值的信息熵为0
		#所以这里不再使用if判断,而是使用差错控制语句实现
		try:
			entd0 = -p0 * math.log(p0, 2)
			entd1 = -p1 * math.log(p1, 2)
			entdv.append([entd0 + entd1, sum(count[i])])
		except:
			entdv.append([0, sum(count[i])])
	return entdv

 我们对于纹理属性的信息熵如下:

[[0.7642045065086203, 9], [0.7219280948873623, 5], [0, 3]]
[Finished in 0.3s]

第一个值为信息熵,第二个值时该取值的样例个数。

 

 计算信息增益:

根据公式来就好。

def GainD(entd, entdv, n):
	m = 0
	for i in entdv:
		m += i[1] / n * i[0]
	return entd - m

我看看纹理属性的信息增益:

0.3805918973682686
[Finished in 0.3s]

我们计算所有属性的信息增益,选择信息增益最大的属性:

def choose(dataset, attribute_name):
	#记录所有属性的信息增益
	gaind_set = []
	for i in range(len(attribute_name)):
		entd = EntD(dataset)
		count = statistics(dataset, i)
		entdv = EntDv(count)
		gaind_set.append(GainD(entd, entdv, len(dataset)))
 
	#找其中的最大值
	a = max(gaind_set)
 
	#确定最大值的位置,从而确定是哪个属性
	k = gaind_set.index(a)
 
	#记录属性名
	label = attribute_name[k]
 
	#更新数据集,根据选择的属性的不同取值,分为对个子数据集
	#使用字典类型存储
	data_set = {}
	for i in dataset:
		#选择过的属性,不再使用,所以我们把它删了
		if i[k] not in data_set:
			a = i.pop(k)
			data_set[a] = [i]
		else:
			a = i.pop(k)
			data_set[a].append(i)
 
	#属性标签的列表中也将选择的属性删除,不再使用
	#为了不改变原始的数据,使用deepcopy更新出新的属性标签列表
	attribute_name_new = copy.deepcopy(attribute_name)
	del(attribute_name_new[k])
	return data_set, attribute_name_new, label

 我们看看第一轮的最优属性选择:

label:

纹理
[Finished in 0.3s]

分类后的数据集data_set:

{'清晰': [['青绿', '蜷缩', '浊响', '凹陷', '硬滑', '是'], ['乌黑', '蜷缩', '沉闷', '凹陷', '硬滑', '是'], ['乌黑', '蜷缩', '浊响', '凹陷', '硬滑', '是'], ['青绿', '蜷缩', '沉闷', '凹陷', '硬滑', '是'], ['浅白', '蜷缩', '浊响', '凹陷', '硬滑', '是'], ['青绿', '稍蜷', '浊响', '稍凹', '软粘', '是'], ['乌黑', '稍蜷', '浊响', '稍凹', '硬滑', '是'], ['青绿', '硬挺', '清脆', '平坦', '软粘', '否'], ['乌黑', '稍蜷', '浊响', '稍凹', '软粘', '否']], '稍糊': [['乌黑', '稍蜷', '浊响', '稍凹', '软粘', '是'], ['乌黑', '稍蜷', '沉闷', '稍凹', '硬滑', '否'], ['青绿', '稍蜷', '浊响', '凹陷', '硬滑', '否'], ['浅白', '稍蜷', '沉闷', '凹陷', '硬滑', '否'], ['青绿', '蜷缩', '沉闷', '稍凹', '硬滑', '否']], '模糊': [['浅白', '硬挺', '清脆', '平坦', '硬滑', '否'], ['浅白', '蜷缩', '浊响', '平坦', '软粘', '否'], ['浅白', '蜷缩', '浊响', '平坦', '硬滑', '否']]}
[Finished in 0.3s]

更新后的属性标签列attribute_name_new:

['色泽', '根蒂', '敲声', '脐部', '触感']
[Finished in 0.3s]

现在一切就绪,我们不断迭代上述过程,将找到的最佳的属性,放到树的结点中,构造一个树形结构就OK了

树的创建: 

def create_tree(tree, dataset, attribute_name):
	#当数据集的信息熵为正无穷大时,数据集分类唯一
	#创建叶子结点,结点数据为类别标签
	if EntD(dataset) == 999:
		tree.append(dataset[0][-1])
	else:
		#数据集不是唯一分类时,选择当前数据集的最优划分属性
		data_set, attribute_name_new, label = choose(dataset, attribute_name)
		if len(attribute_name_new) != 0:
			#划分后,每一个划分子集,对应一个中间结点,结点数据为属性标签
			for i in data_set:
				tree.append([label+i])
				create_tree(tree[-1], data_set[i], attribute_name_new)

最终的模型如下:

[['纹理清晰', ['根蒂蜷缩', '是'], ['根蒂稍蜷', ['色泽青绿', '是'], ['色泽乌黑', ['触感硬滑', '是'], ['触感软粘', '否']]], ['根蒂硬挺', '否']], ['纹理稍糊', ['触感软粘', '是'], ['触感硬滑', '否']], ['纹理模糊', '否']]
[Finished in 0.3s]

这里有一个问题,例如:颜色属性中的浅白,模型中没有浅白的属性分类,因为这些数据,在其他属性分类中已经分好了类,这样的属性取值在模型中是缺失的,但是可以人工加上去,其分类标签要由编程者自己判断了。

整体代码如下:

import xlrd
import math
import copy
 
def loaddataset(filename):
	wb = xlrd.open_workbook(filename)
	ws = wb.sheet_by_name('Sheet1')
	dataset = []
	for r in range(ws.nrows):
		co1 = []
		for c in range(1, ws.ncols):
			co1.append(ws.cell(r,c).value)
		dataset.append(co1)
 
	#记录所有的属性名
	attribute_name = dataset.pop(0)
	del(attribute_name[-1])
	return dataset, attribute_name
 
def EntD(dataset):
	#对正例数量计数
	count = 0
	for i in dataset:
		if i[-1] == '是':
			count += 1
 
	#计算正反例所占比例
	p0 = 1 - count / len(dataset)
	p1 = 1 - p0
 
	#当占比为0时,根据信息熵的公式趋近于正无穷
	#这里我们用999代替正无穷
	if p0 == 0:
		entd0 = 999
		entd1 = 0
	elif p1 == 0:
		entd0 = 0
		entd1 = 999
	else:
		entd0 = -p0 * math.log(p0, 2)
		entd1 = -p1 * math.log(p1, 2)
	return entd0 + entd1
 
#n表示统计的属性的位置
def statistics(dataset, n):
	#记录统计结果
	count = {}
	for i in dataset:
		if i[n] not in count:
			#列表第一个位置为正例个数,第二个位置是反例个数
			if i[-1] == '是':
				count[i[n]] = [1, 0]
			else:
				count[i[n]] = [0, 1]
		else:
			if i[-1] == '是':
				count[i[n]][0] += 1
			else:
				count[i[n]][1] += 1
	return count
 
def EntDv(count):
	#记录结果
	entdv = []
	for i in count:
		p0 = count[i][1] / sum(count[i])
		p1 = count[i][0] / sum(count[i])
 
		#根据信息熵的定义,占比为0是应该是正无穷,占比为1应该是0
		#但是我们认为在该情况下,我们可以忽略该取值的信息对属性整体信息量的影响
		#所以出现这种情况时,该取值的信息熵为0
		#所以这里不再使用if判断,而是使用差错控制语句实现
		try:
			entd0 = -p0 * math.log(p0, 2)
			entd1 = -p1 * math.log(p1, 2)
			entdv.append([entd0 + entd1, sum(count[i])])
		except:
			entdv.append([0, sum(count[i])])
	return entdv
 
def GainD(entd, entdv, n):
	m = 0
	for i in entdv:
		m += i[1] / n * i[0]
	return entd - m
 
def choose(dataset, attribute_name):
	#记录所有属性的信息增益
	gaind_set = []
	for i in range(len(attribute_name)):
		entd = EntD(dataset)
		count = statistics(dataset, i)
		entdv = EntDv(count)
		gaind_set.append(GainD(entd, entdv, len(dataset)))
 
	#找其中的最大值
	a = max(gaind_set)
 
	#确定最大值的位置,从而确定是哪个属性
	k = gaind_set.index(a)
 
	#记录属性名
	label = attribute_name[k]
 
	#更新数据集,根据选择的属性的不同取值,分为对个子数据集
	#使用字典类型存储
	data_set = {}
	for i in dataset:
		#选择过的属性,不再使用,所以我们把它删了
		if i[k] not in data_set:
			a = i.pop(k)
			data_set[a] = [i]
		else:
			a = i.pop(k)
			data_set[a].append(i)
 
	#属性标签的列表中也将选择的属性删除,不再使用
	#为了不改变原始的数据,使用deepcopy更新出新的属性标签列表
	attribute_name_new = copy.deepcopy(attribute_name)
	del(attribute_name_new[k])
	return data_set, attribute_name_new, label
 
def create_tree(tree, dataset, attribute_name):
	#当数据集的信息熵为正无穷大时,数据集分类唯一
	#创建叶子结点,结点数据为类别标签
	if EntD(dataset) == 999:
		tree.append(dataset[0][-1])
	else:
		#数据集不是唯一分类时,选择当前数据集的最优划分属性
		data_set, attribute_name_new, label = choose(dataset, attribute_name)
		if len(attribute_name_new) != 0:
			#划分后,每一个划分子集,对应一个中间结点,结点数据为属性标签
			for i in data_set:
				tree.append([label+i])
				create_tree(tree[-1], data_set[i], attribute_name_new)
 
if __name__ == '__main__':
	dataset , attribute_name = loaddataset('西瓜.xlsx')
	tree = []
	create_tree(tree, dataset, attribute_name)
	print(tree)