数据挖掘算法

分类类别ification :分类是将目标对象按不同的标签进行分组，由此所有标签都是已知的，这些对象通常具有不同的特征。 也就是说，对于某个classifier，通常必须告诉他们“这个被分类到某个类别”的例子。 理想情况下，一个classifier从其训练集进行“学习”，并且提供训练数据，该训练数据具有分类和预测未知数据的能力的过程通常被称为专业学习(监督学习)。应用场景：分类银行贷款安全与风险，信用卡持卡人KNN算法：k最近分类算法(K-Nearest Neighbor )，最简单的机器学习算法之一。 想法是，如果一个样本属于特征空间中k个最类似的样本之中有许多类，那么其样本也属于一个类。如上图所示，决定绿色圆赋予哪个种类，红色三角形还是蓝色四角形的K=3时，红色三角形所占的比例为2/3，因此绿色圆赋予红色三角形的类，K=5时，蓝色四角形的比例为3/5，因此绿色圆赋予蓝色四角形的类。决策树分类算法ID3 :ID3算法是Quinlan首先提出的。 该算法基于信息理论，以信息熵和信息增益度为测量标准，实现数据归纳分类。 具体流程如下：输入：样本集s、属性集a输出： ID3决策树如果处理完所有类型的属性，则返回：否则执行2计算信息增益最大属性a，将该属性作为一个节点，只要属性a能够对样本进行分类，则返回其他情况下，执行3。对于属性a的每个可能值v，进行以下操作。将所有属性a的值为v的样本作为s的子集Sv产生新的属性集合AT=A-a将样本集合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只能取2个值(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分类算法预测未知样本的类标签。 给定队球赛结果的训练样本集如下表所示。 “天气”、“温度”、“湿度”和“风强度”判断球队的比赛结果是否获胜。 级别属性比赛的结果具有两个不同的值Win，Lose。 假设C1对应于类Result=“Win”，C2对应于类Result=“Lose”。 使用ID3分类算法按如下方式预测样本时，比赛的胜负结果。首先，类别是(胜负结果)。 计算分类系统熵：其中具有“是”值的记录有9个，具有“否”值的记录有5个，P(C1)=9/14，P(C2)=5/14企业(s )=-(9/14 ) * log2 (9/14 )-(5/14 ) * log2 (5/14 )然后，计算将各个属性作为根节点信息增益.Outlook信息增益：企业(sunny )=-(2/5) * log2 (2/5)-(3/5) * log2 (3/5)=0.971企业级(rain )=-(2/5) * log2(2/5)-(3/5) * log2(3/5)=0. 971企业(overcast )=-(4/4) * log2 (4/4)=0gain (outlook )=entropy (s )-(5/14 ) * entropy (sunny )-(5/14 ) * entropy (rain )-(4/14 ) * entropy (overcast )=0. 247模板信息增益：企业(hot )=-(2/4) * log2 (2/4)-(2/4) * log2 (2/4)=1企业级(mild )=-(4/6) * log2(4/6)-(2/6) * log2(2/6)=0. 918企业(cool )=-(3/4) * log2 (3/4)-(1/4) * log2 (1/4)=0.811gain (temperature )=entropy (s )-(4/14 ) * entropy (hot )-(6/14 ) * entropy (mild )-(4/14 ) * entropy (cool )=0. 247Humidity信息增益：entropy (high )=-(3/7) * log2(3/7)-(4/7) * log2(4/7)=0. 985企业(正常)=-(6/7) * log2 (4/6)-(6/7) * log2 (1/7)=0.592gain (humidity )=entropy (s )-(7/14 ) * entropy (high )-(7/14 ) * entropy (normal )=0. 151Wind信息增益：entropy (strong )=-(3/6) * log2(3/6)-(3/6) * log2(3/6)=1企业(weak )=-(6/8) * log2 (6/8)-(2/8) * log2 (2/8)=0.811gain (wind )=entropy (s )-(6/14 ) * entropy (strong )-(8/14 ) * entropy (weak )=0. 048这样，得到与上述四个属性相应的信息增益值，最后选择outlook作为根节点，使得信息增益值最大。 子节点也重复上述步骤。 可以创建以下决策树OutlookHumidity窗口WinWinWin罗斯WinSunny公司OvercastRainHigh正常(标准)Strong市扫描所有交易记录按候补进行计数威凯因此，样本x被分配给类别C1:Result=“Win”。 即在，这场比赛将获胜。朴素贝叶斯分类算法：朴素贝叶斯分类根据贝叶斯定理，假设一个属性值对给定类产生的影响不依赖于其它属性的值。 将x作为类标签未知的数据样本。 假设h是一个假设，例如，数据样本x属于某个特定类别c。 因此，给出P(H|X )，即观测数据样本x，以确定h成立的概率(后验概率)。贝叶斯定理(公式):PHX=PXHP(H)P(X )朴素贝叶斯分类的工作如下1 .每个数据样本由n维特征向量X=x1，x2，xn表示，其描述了针对这些样本的n个属性A1，A2，An的测量值。2 .假设数据样本可以被分类在m个类C1、C2、c-m中。 给出未知类标签的数据样本x，朴素贝叶斯分类为类Ci，仅在那时P(Ci|X) P(Cj|X) 1jm，jiP(Ci|X )最大的类别Ci称为最大后假设。 从贝叶斯公式中可以看出PCiX=PXCiP(Ci)P(X )3.p(x )对于所有类都是常数，因此P(X|Ci)P(Ci )最大即可。 如果类别的先验概率是未知的，则通常基于贝叶斯假设取P(C1)=P(C2)=P(Cm )以使只有P(X|Ci )最大化。 也可以用P(Ci )=si /s来计算。 但是，si是类别Ci中的训练样本数，s是训练样本总数。4 .当数据集的属性大时，计算P(X|Ci )的开销可能大。 假设班级条件是独立的，简化整合分布并降低P(X|Ci )计算开销。 如果属性值之间的条件不同，则指定示例的类标签即，当在属性之间不存在依赖性时PXCi=k=1nP(Xk|Ci )这里，可以根据训练样本评估概率P(x1|Ci )、P(x2|Ci )、P(xn|Ci )。 在Ak是离散值情况下性，P(xk|Ci)=sik/si。 这里，sik是类Ci中的属性a-k的值为xk的训练样本的数目，并且si是Ci中的属性a-k的值训练样本数。 如果Ak是连续值属性，通常假定该属性遵循高斯分布(正态分布)。 所以有PXkCi=gXk，Ci，Ci=12Ciexp(-12Ci2(Xk-Ci)2)这里，给定类Ci的训练样本属性a-k的值是gXk、Ci、Ci或属性a-k的高斯密度函数，Ci、Ci分别是平均值和标准偏差。5 .计算每个类别Ci的P(X|Ci)P(Ci )。 将样本x分配给类Ci的充分条件是P(X|Ci)P(Ci)P(X|Cj)P(Cj) 1jm，ji也就是说，x被分配给使P(X|Ci)P(Ci )最大的类别Ci。应用实例：用朴素贝叶斯分类预测未知样本的类标签。 指定的PlayTennis培训样本集如下表所示。 使用朴素贝叶斯分类，预测了样本为时是否打球。分类的未知样本如下所示X=。根据naiveBayes分类法，需要将P(X|Ci)P(Ci )、I=1、2最大化。 可以根据培训样本计算每个类的先验概率P(Ci )p (播放列表=“是”)=9/14=0.643p (播放列表=“否”)=5/14=0.357要计算P(X |Ci )、i=1和2，请首先计算以下条件概率p (outlook=“sunny”| play tennis=“是”)=2/9=0. 222p (outlook=“sunny”| play tennis=“否”)=3/5=0. 600p (temperature=“hot”| play tennis=“yes”)=2/9=0. 222p (模板=“热”| play tennis=“否”=2/5=0. 400p (humidity=“high”| play tennis=“是”)=3/9=0. 333p (humidity=“high”| play tennis=“否”)=4/5=0. 800p (windy=“strong”| play tennis=“是”)=3/9=0. 333p (windy=“strong”| play tennis=“否”)=3/5=0. 600利用以上概率，能够实现以下效果p (x|play tennis=“是”)=0. 2220.2220.3330.333=0. 005p (x|play tennis=“否”)=0. 6000.4000.8000.600=0. 115p (x|play tennis=是) p (play tennis=是)=0. 0050.643=0. 003p (x|play tennis=“否”) p (play tennis=“否”)=0. 1150.357=0. 041因此，样本x被分配给类别C2:PlayTennis=“No”。 即在的情况下不玩。支持向量机(SVM )算法：支持向量机(support vector machine )是将基本模型定义为特征空间上间隔最大的线性分类器，使学习策略间隔最大化，最终解决凸二次规划问题的两类分类模型。支持向量机将向量映射到更高维空间，并且在该空间中创建最大间隔的超平面。 在分割数据的超平面的两侧，建设了相互平行的2个超平面。 分离超平面时，两个平行超平面之间的距离最大。 假设平行超平面间的距离和差越大，分类器的总误差越小。 因此，最大化几何间隔