定义
是一种树形结构,其中每个内部节点表示一个属性上的判断,每个分支代表一个判断结果的输出,最后每个叶节点代表一种分类结果,本质是一颗由多个判断节点组成的树。
示例如下:
问题:
概念
物理学上,熵 Entropy 是“混乱”程度的量度。
1948年香农提出了信息熵(Entropy)的概念。
假如事件A的分类划分是(A1,A2,…,An),每部分发生的概率是(p1,p2,…,pn),那信息熵定义为公式如下:(log是以2为底,lg是以10为底)
系统越有序,熵值越低;系统越混乱或分散,熵值越高
案例
案例一
如果一颗骰子的六个面都是1 ,投掷它不会给你带来任何新信息,因为你知道它的结果肯定是1,它的信息熵为?? 答案: - log(1) = 0 。
案例二
假设我们没有看世界杯的比赛,但是想知道哪支球队会是冠军, 我们只能猜测某支球队是或不是冠军,然后观众用对或不对来回答, 我们想要猜测次数尽可能少,你会用什么方法? 答案: 二分法: 假如有 16 支球队,分别编号,先问是否在 1-8 之间,如果是就继续问是否在 1-4 之间, 以此类推,直到最后判断出冠军球队是哪只。 如果球队数量是 16,我们需要问 4 次来得到最后的答案。那么世界冠军这条消息的信息熵就是 4。 如果有32个球队,准确的信息量应该是: H = -(p1 * logp1 + p2 * logp2 + ... + p32 * logp32), 其中 p1, ..., p32 分别是这 32 支球队夺冠的概率。 当每支球队夺冠概率相等都是 1/32 的时:H = -(32 * 1/32 * log1/32) = 5 每个事件概率相同时,熵最大,这件事越不确定。
练习
篮球比赛里,有4个球队 {A,B,C,D} ,获胜概率分别为{1/2, 1/4, 1/8, 1/8} 求H(X) 答案: H(X) = 1\2log(2)+1\4log(4)+1\8log(8)+1\8log(8)=(1\2+1\2+3\8+3\8)log(2)=7\4bits tips: 以2为底,记做lb,单位bit 以e为底,记做ln,单位nat
概念
信息增益
以某特征划分数据集前后的熵的差值。
熵可以表示样本集合的不确定性,熵越大,样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。
信息增益 = entroy(前) - entroy(后)
定义&公式
特征A对训练数据集D的信息增益g(D,A),定义为集合D的信息熵H(D)与特征A给定条件下D的信息条件熵H(D|A)之差
注:信息增益表示得知特征X的信息而使得类Y的信息熵减少的程度
公式为:
公式详细解释如下:
案例
如下图,第一列为论坛号码,第二列为性别,第三列为活跃度,最后一列用户是否流失。我们要解决一个问题:性别和活跃度两个特征,哪个对用户流失影响更大?
通过计算信息增益可以解决这个问题,统计上右表信息。
其中Positive为正样本(已流失),Negative为负样本(未流失),下面的数值为不同划分下对应的人数。
计算三个熵值:
整体熵
性别熵
性别信息增益
活跃度熵
活跃度信息增益
活跃度的信息增益比性别的信息增益大,也就是说,活跃度对用户流失的影响比性别大。
在做特征选择或者数据分析的时候,我们应该重点考察活跃度这个指标。
增益率
增益比率度量是用前面的增益度量Gain(S,A)和所分离信息度量SplitInformation(如上例的性别,活跃度等)的比值来共同定义的。
概念
基尼值
从数据集D中随机抽取两个样本,其类别标记不一致的概率。故,Gini(D)值越小,数据集D的纯度越高。
基尼系数
一般,选择使划分后基尼系数最小的属性作为最优化分属性。
案例
根据下图列表,按照基尼指数的划分依据,做出决策树。
对数据集非类标号属性{是否有房,婚姻状况,年收入}分别计算它们的Gini系数增益,取Gini系数增益值最大的属性作为决策树的根节点属性。
根节点的Gini系数为:
当根据是否有房来进行划分时,Gini系数增益计算过程为:
若按婚姻状况属性来划分,属性婚姻状况有三个可能的取值{married,single,divorced},分别计算划分后的Gini系数增益。
{married} | {single,divorced}
{single} | {married,divorced}
{divorced} | {single,married}
分组为{married} | {single,divorced}时:
当分组为{single} | {married,divorced}时:
当分组为{divorced} | {single,married}时:
对比计算结果,根据婚姻状况属性来划分根节点时取Gini系数增益最大的分组作为划分结果,即:{married} | {single,divorced}
同理可得年收入Gini:
对于年收入属性为数值型属性,首先需要对数据按升序排序,然后从小到大依次用相邻值的中间值作为分隔将样本划分为两组。例如当面对年收入为60和70这两个值时,我们算得其中间值为65。以中间值65作为分割点求出Gini系数增益。
最大化增益等价于最小化子女结点的不纯性度量(Gini系数)的加权平均值,现在我们希望最大化Gini系数的增益。根据计算知道,三个属性划分根节点的增益最大的有两个:年收入属性和婚姻状况,他们的增益都为0.12。此时,选取首先出现的属性作为第一次划分。
接下来,采用同样的方法,分别计算剩下属性,其中根节点的Gini系数为(此时是否拖欠贷款的各有3个records)
对于是否有房属性,可得:
对于年收入属性则有:
总结
决策树构建
决策树变量
评估分割点好坏
如果一个分割点可以将当前的所有节点分为两类,使得每一类都很“纯”,也就是同一类的记录较多,那么就是一个好分割点。
ID3算法
C4.5算法
CART算法
CART算法相比C4.5算法的分类方法,采用了简化的二叉树模型,同时特征选择采用了近似的基尼系数来简化计算。
C4.5不一定是二叉树,但CART一定是二叉树。
无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策,但是大多数,**分类决策不应该是由某一个特征决定的,而是应该由一组特征决定的。**这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候,多变量决策树不是选择某一个最优特征,而是选择最优的一个特征线性组合来做决策。
图示说明:
出现这种情况的原因:
将任意数据(如文本或图像)转换为可用于机器学习的数字特征
注:特征值化是为了计算机更好的去理解数据
分类
API
sklearn.feature_extraction
对字典数据进行特征值化
API
流程分析
- 实例化类DictVectorizer
- 调用fit_transform方法输入数据并转换(注意返回格式)
- 对于特征当中存在类别信息的我们都会做one-hot编码处理
from sklearn.feature_extraction import DictVectorizer def dict_demo(): """ 对字典类型的数据进行特征抽取 :return: None """ data = [{'city': '北京','temperature':100}, {'city': '上海','temperature':60}, {'city': '深圳','temperature':30}] # 1、实例化一个转换器类 transfer = DictVectorizer(sparse=False) # 2、调用fit_transform data = transfer.fit_transform(data) print("返回的结果:\n", data) # 打印特征名字 print("特征名字:\n", transfer.get_feature_names()) return None
对文本数据进行特征值化
API
应用分析
- 实例化类CountVectorizer
- 调用fit_transform方法输入数据并转换 (注意返回格式,利用toarray()进行sparse矩阵转换array数组)
from sklearn.feature_extraction.text import CountVectorizer def text_count_demo(): """ 对文本进行特征抽取,countvetorizer :return: None """ data = ["life is short,i like like python", "life is too long,i dislike python"] # 1、实例化一个转换器类 # transfer = CountVectorizer(sparse=False) # 注意,没有sparse这个参数 transfer = CountVectorizer() # 2、调用fit_transform data = transfer.fit_transform(data) print("文本特征抽取的结果:\n", data.toarray()) print("返回特征名字:\n", transfer.get_feature_names()) return None
问题:如果我们将数据替换成中文?
"人生苦短,我喜欢Python","生活太长久,我不喜欢Python"
得到的结果:
为什么会得到这样的结果呢,仔细分析之后会发现英文默认是以空格分开的。其实就达到了一个分词的效果,所以我们要对中文进行分词处理
jieba分词处理
jieba.cut()
- 返回词语组成的生成器
案例分析
对以下三句话进行特征值化:
今天很残酷,明天更残酷,后天很美好, 但绝对大部分是死在明天晚上,所以每个人不要放弃今天。 我们看到的从很远星系来的光是在几百万年之前发出的, 这样当我们看到宇宙时,我们是在看它的过去。 如果只用一种方式了解某样事物,你就不会真正了解它。 了解事物真正含义的秘密取决于如何将其与我们所了解的事物相联系。
分析
from sklearn.feature_extraction.text import CountVectorizer import jieba def cut_word(text): """ 对中文进行分词 "我爱北京天安门"————>"我 爱 北京 天安门" :param text: :return: text """ # 用结巴对中文字符串进行分词 text = " ".join(list(jieba.cut(text))) return text def text_chinese_count_demo2(): """ 对中文进行特征抽取 :return: None """ data = ["一种还是一种今天很残酷,明天更残酷,后天很美好,但绝对大部分是死在明天晚上,所以每个人不要放弃今天。", "我们看到的从很远星系来的光是在几百万年之前发出的,这样当我们看到宇宙时,我们是在看它的过去。", "如果只用一种方式了解某样事物,你就不会真正了解它。了解事物真正含义的秘密取决于如何将其与我们所了解的事物相联系。"] # 将原始数据转换成分好词的形式 text_list = [] for sent in data: text_list.append(cut_word(sent)) print(text_list) # 1、实例化一个转换器类 # transfer = CountVectorizer(sparse=False) transfer = CountVectorizer() # 2、调用fit_transform data = transfer.fit_transform(text_list) print("文本特征抽取的结果:\n", data.toarray()) print("返回特征名字:\n", transfer.get_feature_names()) return None
但如果把这样的词语特征用于分类,会出现什么问题?
请看问题:
该如何处理某个词或短语在多篇文章中出现的次数高这种情况?
Tf-idf文本特征提取
主要思想是:如果某个词或短语在一篇文章中出现的概率高,并且在其他文章中很少出现,则认为此词或者短语具有很好的类别区分能力,适合用来分类。
作用:用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。
重要性:分类机器学习算法进行文章分类中前期数据处理方式
公式:
词频tf:指的是某一个给定的词语在该文件中出现的频率
逆向文档频率idf:是一个词语普遍重要性的度量。某一特定词语的idf,可以由总文件数目除以包含该词语之文件的数目,再将得到的商取以10为底的对数得到
最终得出结果可以理解为重要程度。
举例如下:
假如一篇文章的总词语数是100个,而词语"非常"出现了5次,那么"非常"一词在该文件中的词频就是5/100=0.05。 而计算文件频率(IDF)的方法是以文件集的文件总数,除以出现"非常"一词的文件数。 所以,如果"非常"一词在1,0000份文件出现过,而文件总数是10,000,000份的话, 其逆向文件频率就是lg(10,000,000 / 1,0000)=3。 最后"非常"对于这篇文档的tf-idf的分数为0.05 * 3=0.15
案例:
from sklearn.feature_extraction.text import TfidfVectorizer import jieba def cut_word(text): """ 对中文进行分词 "我爱北京天安门"————>"我 爱 北京 天安门" :param text: :return: text """ # 用结巴对中文字符串进行分词 text = " ".join(list(jieba.cut(text))) return text def text_chinese_tfidf_demo(): """ 对中文进行特征抽取 :return: None """ data = ["一种还是一种今天很残酷,明天更残酷,后天很美好,但绝对大部分是死在明天晚上,所以每个人不要放弃今天。", "我们看到的从很远星系来的光是在几百万年之前发出的,这样当我们看到宇宙时,我们是在看它的过去。", "如果只用一种方式了解某样事物,你就不会真正了解它。了解事物真正含义的秘密取决于如何将其与我们所了解的事物相联系。"] # 将原始数据转换成分好词的形式 text_list = [] for sent in data: text_list.append(cut_word(sent)) print(text_list) # 1、实例化一个转换器类 # transfer = CountVectorizer(sparse=False) transfer = TfidfVectorizer(stop_words=['一种', '不会', '不要']) # 2、调用fit_transform data = transfer.fit_transform(text_list) print("文本特征抽取的结果:\n", data.toarray()) print("返回特征名字:\n", transfer.get_feature_names()) return None
今天的重点是决策树算法,对于熵、信息增益、信息增益率、基尼值等决策树的划分依据都有了初步的认知。此外对于ID3、C4.5算法的区别也有了认识,那么在工作中,C4.5应用相对广泛,然后我们又了解了CART剪枝,它一定是二叉树,有预剪枝和后剪枝。
最后呢,我们对特征工程的提取也做了总结,如字典特征提取,文本特征提取,还有jieba分词处理,tf-idf文本特征抽取,在分类机器学习算法中,对文章前期数据处理中tf-idf应用很多。
理论+实践才是高效学习的基石,在总结了这么多理论的基础下,我们可以通过kaggle,学习冠亚军的代码,然后自己练习,肯定会收获更多。
加油!加油!!加油!!!