数据挖掘算法.docx

分类Classification:
分类是指将目标对象按照不同的标记进行分组，所有的标记都是已知的，这些对象往往都具有不同的特点。也就是说对于一个classifier，通常需要你告诉它“这个东西被分为某某类”这样一些例子。理想情况下，一个classifier会从它得到的训练集中进行“学习”，从而具备对未知数据进行分类预测的能力，这种提供训练数据的过程通常叫做HYPERLINK"http://en.wikipedia.org/wiki/Supervised_learning"\t"_blank"supervisedlearning(监督学习)。
应用场景：银行贷款安全和风险、信用卡持卡用户进行分类
KNN算法：
K最邻近分类算法（K-NearestNeighbor），最简单的机器学习算法之一。思路是：如果一个样本在特征空间中的k个最相似的样本中的大多数属于某个类，则该样本也属于某个类别。

如上图所示，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。

决策树分类算法ID3：
ID3算法是由Quinlan首先提出的。该算法是以HYPERLINK"http://baike.baidu.com/view/15076.htm"\t"_blank"信息论为基础，以HYPERLINK"http://baike.baidu.com/view/401605.htm"\t"_blank"信息熵和HYPERLINK"http://baike.baidu.com/view/1231985.htm"\t"_blank"信息增益度为衡量标准，从而实现对数据的归纳分类。具体流程如下：
输入：样本集合S,属性集合A
输出：ID3决策树
=1\*GB2⑴若所有种类的属性都处理完毕，返回：否则执行2
=2\*GB2⑵计算出信息增益最大属性a，把该属性作为一个节点，如果仅凭属性a就可以对样本进行分类，则返回；否则执行3。
=3\*GB2⑶对属性a的每个可能的取值v，执行下一操作：
=1\*GB3①将所有属性a的值是v的样本作为S的一个子集Sv；
=2\*GB3②生产新的属性集合AT=A-{a}
=3\*GB3③以样本集合Sv和属性集合AT为输入，递归执行id3算法。

分类系统的信息熵和信息增益：
对分类系统来说，类别C是变量，可能的取值是C1，C2，C3......Cn，而每个类别出现的概率为P(C1),P(C2),P(C3).....P(Cn)，N就是系统的类别，因此分类系统的熵代表包含系统所有特征属性时系统的信息量（熵），就可以表示为：
HC=-i=1nP(Ci)×log2P(Ci);P(Ci)即类别Ci出现的概率
对分类系统来说，一个特征属性，系统有它和没它时信息量将发生变化，而前后信息量的差值就是这个特征给系统带来的信息量，即信息增益。系统包含特征属性时的信息量有了，那么就要求系统不包含该特征属性时的信息量，这个问题等价于系统包含了特征属性X，但特征属性X已经固定不能变化时的信息量，此时的信息量即条件熵需要用特征属性X每个可能的值出现的概率来表示：
HCX=P1HCX=x1+P2HCX=x2+…+PnHCX=xn
=i=1nPiH(C|X=Xi)
具体到分类系统，分类系统的特征属性T的固定值t只可能取两个值（即t出现或t不出现），例如湿度这个特征属性的固定值（高）只可能取两个值，即高要么出现，要么不出现。
HCT=PtHCt+PtHCt
=-Pti=1nP(Ci|t)×log2P(Ci|t)-Pti=1nP(Ci|t)×log2P(Ci|t)

因此特征T给系统带来的信息增益就可以写成系统原本的熵与固定特征T后的条件熵之差：IG(C)=H(C)-H(C|T)

应用举例：使用ID3分类算法预测未知样本的类标号。给定球队球类比赛结果的训练样本集见下表。根据天气（Outlook），温度（Temperature），湿度（Humidity），风强度（Windy）
来判断该球队比赛结果是否会赢。类标号属性比赛结果具有两个不同值{Win,Lose}。设C1对应于类Result=“Win”,而C2对应于类Result=“Lose”。使用ID3分类算法来预测样本为
＜Outlook=Sunny,Temperature=Hot,Humidity=High,Wind=Strong＞的情况下，比赛的输赢结果。

首先，类别是（输赢结果）。取值yes的记录有9个，取值为no的记录有5个，那么P(C1)=9/14，