数据挖掘算法

1、分类Classification:分类是指将目标对象按照不同的标记进行分组，所有的标记都是已知的，这些对象往往都具有不同的特点。也就是说对于一个 classifier ，通常需要你告诉它“这个东西被分为某某类”这样一些例子。理想情况下，一个 classifier 会从它得到的训练集中进行“学习”，从而具备对未知数据进行分类预测的能力，这种提供训练数据的过程通常叫做 supervised learning (监督学习)。应用场景：银行贷款安全和风险、信用卡持卡用户进行分类KNN算法：K最邻近分类算法（K-Nearest Neighbor），最简单的机器学习算法之一。思路是：如

2、果一个样本在特征空间中的k个最相似的样本中的大多数属于某个类，则该样本也属于某个类别。如上图所示，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。决策树分类算法ID3：ID3算法是由Quinlan首先提出的。该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。具体流程如下：输入：样本集合S,属性集合A输出：ID3决策树若所有种类的属性都处理完毕，返回：否则执行2计算出信息增益最大属性a，把该属性作为一个节点，如果仅

3、凭属性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出现的概率对分类系统来说，一个特征属

4、性，系统有它和没它时信息量将发生变化，而前后信息量的差值就是这个特征给系统带来的信息量，即信息增益。系统包含特征属性时的信息量有了，那么就要求系统不包含该特征属性时的信息量，这个问题等价于系统包含了特征属性X，但特征属性X已经固定不能变化时的信息量，此时的信息量即条件熵需要用特征属性X每个可能的值出现的概率来表示：HCX=P1HCX=x1+P2HCX=x2+PnHCX=xn=i=1nPiH(C|X=Xi)具体到分类系统，分类系统的特征属性T的固定值t只可能取两个值（即t出现或t不出现），例如湿度这个特征属性的固定值（高）只可能取两个值，即高要么出现，要么不出现。HCT=PtHCt+PtHCt=

5、-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

6、”。使用ID3分类算法来预测样本为Outlook=Sunny, Temperature=Hot, Humidity=High, Wind=Strong的情况下，比赛的输赢结果。首先，类别是（输赢结果）。取值yes的记录有9个，取值为no的记录有5个，那么P(C1)=9/14，P(C2)=5/14，那么计算分类系统的熵:Entropy(S)=-(9/14)*log2(9/14) -(5/14)*log2(5/14);然后分别计算以各个属性作为根节点的信息增益Outlook的信息增益：Entropy(Sunny)=-(2/5)*log2(2/5)-(3/5)*log2(3/5)=0.971Entr

7、opy(Rain)=-(2/5)*log2(2/5)-(3/5)*log2(3/5) =0.971Entropy(Overcast)=-(4/4)*log2(4/4)=0Gain(Outlook)=Entropy(S)-(5/14)*Entropy(Sunny)-(5/14)*Entropy(Rain)- (4/14)* Entropy(Overcast)=0.247Temperature的信息增益：Entropy(Hot)=-(2/4)*log2(2/4)-(2/4)*log2(2/4)=1Entropy(Mild)=-(4/6)*log2(4/6)-(2/6)*log2(2/6)=0.91

8、8Entropy(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.985Entropy(Normal)=-(6/7)*log2(4/6)-(6/7)*log2(1/7)=0.592Gain(Humidity)= Entropy(S)

9、-(7/14)*Entropy(High)-(7/14)* Entropy(Normal) =0.151Wind的信息增益：Entropy(Strong)=-(3/6)*log2(3/6)-(3/6)*log2(3/6)=1Entropy(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这样我们就得到以上4个属性相应的信息增益值，最后安装信息增益值最大的原则选择outlook为根节点。子节点也重复以上的步骤。

10、就可以建立下以下这可决策树：OutlookHumidityWindWinWinWinLoseWinSunnyOvercastRainHighNormalStrong扫描所有的交易记录对每个候选计数Weak因此，将样本X 指派给类C1：Result =“Win”。即在Outlook = Sunny,Temperature = Hot, Humidity = High, Wind = Strong的情况下这场比赛会赢。 朴素贝叶斯分类算法： 朴素贝叶斯分类基于贝叶斯定理,假设一个属性值对给定类的影响独立于其他属性的值。设X是类标号未知的数据样本。设H为某种假定，如，数据样本X属于某特定的类C。因此

11、我们希望确定P(H|X)，即给定观测数据样本X,假定H成立的概率（后验概率）。贝叶斯定理（公式）：PHX=PXHP(H)P(X)朴素贝叶斯分类的工作过程如下： 1、用n 维特征向量X=x1, x2, xn表示每个数据样本，用以描述对该样本的n 个属性A1, A2, , An 的度量。2、假定数据样本可以分为m 个类C1, C2, , Cm。给定一个未知类标号的数据样本X，朴素贝叶斯分类将其分类到类Ci ，当且仅当P(Ci|X) > P(Cj|X) 1jm，ji P(Ci|X)最大的类Ci 称为最大后验假定。由贝叶斯公式可知PCiX=PXCiP(Ci)P(X) 3、由于P(X) 对于所有类

12、都为常数，只需要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

13、是离散值属性，则P(xk|Ci)=sik/si 。其中，sik 是类Ci 中属性Ak 的值为xk 的训练样本数，而si 是Ci 中的训练样本数。如果Ak 是连续值属性，通常假定该属性服从高斯分布（正态分布）。从而有PXkCi=gXk,Ci,Ci=12Ciexp(-12Ci2(Xk-Ci)2)其中，给定类 Ci的训练样本属性 Ak的值，gXk,Ci,Ci是属性 Ak的高斯密度函数，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

14、(X|Ci)P(Ci)最大的类Ci中。应用举例：使用朴素贝叶斯分类预测未知样本的类标号。给定PlayTennis 的训练样本集见下表。使用朴素贝叶斯分类来预测样本为Outlook=Sunny, Temperature=Hot, Humidity=High, Wind=Strong的情况下，是否打球。要分类的未知样本为：X =Outlook=Sunny, Temperature=Hot, Humidity=High, Wind=Strong。根据朴素贝叶斯分类方法，需要最大化P(X|Ci)P(Ci)，i =1, 2。每个类的先验概率P(Ci)可以根据训练样本计算：P(PlayTennis=“Ye

15、s”) = 9/14 = 0.643P(PlayTennis=“No”) = 5/14 = 0.357为计算P(X |Ci)，i=1, 2，先计算下面的条件概率：P(Outlook=“Sunny”| PlayTennis =“Yes”) = 2/9 = 0.222P(Outlook=“Sunny”| PlayTennis =“No”) = 3/5 = 0.600P(Temperature=“Hot”| PlayTennis =“Yes”) = 2/9 = 0.222P(Temperature=“Hot”| PlayTennis =“No”) = 2 /5 = 0.400P(Humidity=“

16、High”| PlayTennis =“Yes”) = 3/9 = 0.333P(Humidity=“High”| PlayTennis =“No”) = 4/5 = 0.800P( Windy=“Strong”| PlayTennis =“Yes”) = 3/9 = 0.333P( Windy=“Strong”| PlayTennis =“No”) = 3/5 = 0.600利用以上概率，可以得到：P(X | PlayTennis =“Yes”) = 0.222×0.222×0.333×0.333 = 0.005P(X | PlayTennis =“No”) =

17、 0.600×0.400×0.800×0.600 = 0.115P(X | PlayTennis =“Yes”) P(PlayTennis =“Yes”) = 0.005×0.643 = 0.003P(X | PlayTennis =“No”) P(PlayTennis =“No”)= 0.115×0.357 = 0.041因此，将样本X 指派给类C2：PlayTennis =“No”。即在Outlook = Sunny,Temperature = Hot, Humidity = High, Wind = Strong的情况下不去打球。支持向量

18、机（SVM）算法： 支持向量机（support vector machine），是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。因此最大化几何间隔成了我们训练阶段的目标。如下图所示：为了简化问题，我们用二维空间来解释这个分类问题。要将图中黑白圆圈分类，中间的直线就是一个分类函数，它可以完全

19、将这些样本分开。一般的，如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。实际上，一个线性函数是一个实值函数（即函数的值是连续的实数），而我们的分类问题（例如这里的二元分类问题回答一个样本属于还是不属于一个类别的问题）需要离散的输出值，例如用1表示某个样本属于类别C1，而用0表示不属于，这时候只需要简单的在实值函数的基础上附加一个阈值即可，通过分类函数执行时得到的值大于还是小于这个阈值来确定类别归属。 例如我们有一个线性函数g(x)=wx+b我们可以取阈值为0，这样当有一个样本xi需要判别的时候，我们就看g(xi)的值。若g(xi)>0，就判别为类

20、别C1，若g(xi)<0，则判别为类别C2（等于的时候我们就拒绝判断）。但实际上这个线性函数（分类函数）可以平移或者稍微旋转，同样可以将样本分割成两类，所以就需要有个度量标准来判断哪个分类函数更好。通常使用“分类间隔”，即我们要求最大化这个分类间隔。在二元的线性分类中，这个表示分类的标记只有两个值，1和-1（用来表示属于还是不属于这个类）。有了这种表示法，我们就可以定义一个样本点到某个超平面的间隔：i=yi(wxi+b)现在把w和b进行一下归一化，即用w/|w|和b/|w|分别代替原来的w和b，那么间隔就可以写成，归一化w和b之后得到的间隔称为几何间隔，即：那么由于间隔：=y(wx+b)

21、=|g(x)|几何间隔：，可以得出=|w|几何 ，这样w和几何是成反比的，这样求几何间隔的最大化问题就转成求最小化|w|。Adaboost算法：Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器 (强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。使用adaboost分类器可以排除一些不必要的训

22、练数据特徵，并将关键放在关键的训练数据上面。算法的具体步骤如下：1、给定训练样本集S，其中X和Y分别对应于正例样本和负例样本；T为训练的最大循环次数；2、初始化样本权重为1/n，即为训练样本的出事概率分布；3、第一次迭代：（1）训练样本的概率分布相当，训练弱分类器；（2）计算弱分类器的错误率；（3）选取合适阈值，是的误差最小；（4）更新样本权重。经过T此循环后，得到T个弱分类器，按更新的权重叠加，最终的到强分类器。具体步骤如下：给定m个样本(x1,y1),.(xm,ym)，其中xiX，yiY=-1,+1 Xi表示X中的第i个元素，yi表示与Xi对应元素的属性值，+1表示Xi属于某个分类，-1表

23、示Xi不属于与某个分类。初始化训练样本xi的权重D(i): i=1,.,m;（1）若正负样本数目一致，D1(i) = 1/m（2）若正负样本数目m+，m-则正样本D1(i)=1/m+, 负样本D1(i)=1/m-.进行多次迭代，用t=1,2.,T表示迭代的轮次。（1）计算该弱分类器的权值Dt下的错误率：t=i=1mDt(Xi) (yiht(xi)。若划分正确，则不计入误差；若划分错误，则计入误差。（2）IF t0.5, then stop（3）更新分类器权重：t=12ln1-tt（4）根据上述错误率更新样本权值： Dt+1i=Dt(i)Zt×exp-t, htxi=yiexpt, h

24、t(xi)yi Zt是规范化因子（5）最后得到强分类器：HX=sign(t=1Ttht(x)应用于二分类或者多分类的应用场景以及一些特征选择（目前有基于Haar特征的Adaboost人脸检测技术）分类回归树（CART）：预测： 预测是构造和使用模型评估无标号的样本，或评估给定样本可能具有的属性值或值区间。分类和回归是两类主要预测的问题。其中，分类是预测离散或者标称值，而回归用于预测连续或者有序值。观点任务：预测类标号为分类，预测连续值（例如：使用回归方法）为预测。连续值的预测一般用回归统计技术建模。回归方法包括线性回归（LinearRegression）、多元回归（Multiple Regre

25、ssion）、非线性回归（Polynomial Regression）、泊松回归（Poisson Regression）、对数回归（Log-linear Regression，有的称为逻辑线性回归）等。许多问题可以用线性回归解决，不能解决的需要将非线性问题转换成线性问题来处理。回归分析算法：确定两种或两种以上变量间相互依赖的定量关系的统计分析算法。在预测系统中的应用主要是根据训练样本中的数据，分析属性间的相互关系（线性或者非线性关系），从而可以预测新样本数据相关的属性值。如线性回归算法，多元回归算法，非线性回归算法。这里举最简单的线性算法为例，在线性回归中，用直线建模，将一个随机变量Y看做另一

26、个随机变量X的线性函数。Y=+X，其中Y的方差为常数，和为回归系数，可以用最小平方法求解。给定s个样本(x1,y1)，(x2,y2). (xn,yn)，回归系数的计算公式如下：=i=1nxi-x(yi-y)i=1nxi-x2=y-x , x,y是平均数。应用举例：预测年薪下图给出了一组年薪数据以及对应相关的数据点，X,Y分别表示工作年数与收入，可以发现X和Y之间存在线性关系（如图）。用公式Y=+X表示。 那么根据回归系数的计算公式，就可以得到方程Y=23.6+3.5X。那么就可以求得例如具有10年工作经验的员工的年薪。关联规则分析算法：发现大量数据中项集之间有趣的关联或者相关关系。布尔关联规则

27、Apriori算法Apriori性质：频繁项集的所有非空子集都必须是频繁的。如果项集I不满足最小支持度阈值，则I不是频繁项，那么如果项A添加到I，结果项集IA不可能比I更频繁出现。因此IA也不是频繁的，即，则。Apriori算法：使用候选项集找频繁项集的逐层搜索的迭代方法，即K项集用于探索（k+1）项集。过程由连接和剪枝组成。连接：为找Lk，通过Lk-1*Lk-1(与自身的连接)产生候选k项集的集合。要求连接的项集共享k-1=0个项。剪枝：根据Apriori性质，频繁项集的所有子集都必须是频繁的，删除自身连接产生的不频繁项集。（我们只需要检查它们的k-1项子集是否频繁）重复连接和剪枝的过程，直

28、到不能再产生频繁k项集的集合，算法终止，即找出了所有的频繁项集。Apriori算法的应用实例：下图为某商场的交易记录，共有9个事务。假定最小事务支持计数为2，即min_sup=2/9=22%，利用Apriori算法寻找频繁项集的过程如下：频繁项集L1C候选集C1C项集比较候选支持度计数与最小支持度计数支持度计数I16I27I36I42I52项集支持度计数I16I27I36I42I52扫描所有的交易记录对每个候选计数候选集C2C候选集C2C频繁项集L2C项集(I1,I2)扫描事务，对每个候选计数(I1,I3)(I1,I4)(I1,I5)(I2,I3)(I2,I4)(I2,I5)(I3,I4)(I

29、3,I5)(I4,I5)项集(I1,I2)4(I1,I3)比较候选支持度计数与最小支持度计数4(I1,I4)1(I1,I5)2(I2,I3)4(I2,I4)2(I2,I5)2(I3,I4)0(I3,I5)1(I4,I5)0项集(I1,I2)4(I1,I3)4(I1,I5)2(I2,I3)4(I2,I4)2(I2,I5)2由L1产生候选C2频繁项集L2C候选集C2C候选集C2C比较候选支持度计数与最小支持度计数扫描事务，对每个候选计数由L1产生候选C2项集(I1,I2,I3)(I1,I2,I5)项集(I1,I2,I3)2(I1,I2,I5)2项集(I1,I2,I3)2(I1,I2,I5)2由上过

30、程可得到事务系统的频繁项集，因此我们可以由频繁项集生成事务系统的强关联规则（强关联规则满足最小支持度和最小置信度）。最小置信度公式表示如下：confidenceA=>B=PBA=support_count(AB)support_count(A)其中，support_count(AB)和support_count(A)表示包含项集AB、A的事务计数，根据以上公式，可以产生关联规则如下：1、对于每个频繁项集L，产生L的所有非空子集2、对于每个非空子集S，如果support_count(L)support_count(S)min_conf，则输入规则：“S=>(L-S)”那么例子中的频繁

31、项集将产生以下关联规则：I1I2=> I5confidence=2/4I1I5=> I5confidence=2/2I2I5=> I5confidence=2/2I1=>I2 I5confidence=2/6 I2=>I1 I5confidence=2/7I5=>I1 I2confidence=2/2假设置信度为70%，那么只有第2,3,6条满足强关联规则。聚类Clustering分析算法：一种无监督的机器学习算法，对没有标记（分类）的训练样本进行学习，以发现训练样本集中的结构性知识。这里，所有的标记（分类）是未知的。而聚类则是指将物理或抽象对象的集合分到不

32、同组的分析过程。这些组内成员具有很大的相似性，而组间成员具有很大的相异性。同分类（Classification）不同，聚类不依赖事先预定义的类标记，而需要自己标识。K-Means算法：K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。算法过程如下：1）从N个集合对象随机选取K个对象作为圆心；2）对剩余的每个集合对象测量其到每个质心的距离，并把它归到最近的圆心的类；3）重新计算已经得到的各个类的圆心；4）迭代23步直至新的圆心与原圆心相等或小于指定阈值，即算法收敛结束。PageRank算法：Google的网页排名算法，是一种由

33、根据网页之间相互的超链接计算等级（PR值）的排序算法。其基本思想如下：如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/L(T)。其中PR（T）为T的PageRank值，L(T)为T的出链数。即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面PageRank值是由所有链向它的页面（链入页面）的重要性经过递归算法得到的。简单的PageRank模型如下，A,B,C,D分别代表网页节点，如果网页A存在链接到网页B，则存在一条有向边A->B（有向图如下：）。 BCC

34、DA 如上图的话，我们可以得到4个网页的PR值如下：PRA=PRB2+PRCPRB=PRA3+PRD2PRC=PRA3+PRD2 PRD=PRA3+PRB2也可以用n*n的矩阵表示该有向图，其中每行代表的是元素指向的节点，如第一行表示存在A节点指向B、C和D的链接。列表示对于指定的节点有多少个指向该节点的节点，如第一列则表示指向A节点的有B和C节点。因为PR值要平均到每个链接，因此将矩阵每行除以每行的链接数可以得到新的矩阵如下：将矩阵M'转置后得到MT由此我们可以得到PageRank的计算公式： PR(i)=(1-d)/n+dj=1nPR(j)L(j)用矩阵的形式表示如下：PR=(1-d)/n(1-d)/n+dL(1,1)L(1,n)L(n,1)L(n,n)PR（PR代表PageRank值，这里引入了d阻尼因素，是为了解决终止点和陷阱问题）PageRank算法的计算是一个迭代的过程，递归直到最