数据挖掘算法.docx

分类Classification:分类是指将目标对象按照不同的标记进行分组，所有的标记都是已知的，这些对象往往都具有不同的特点。也就是说对于一个 classifier ，通常需要你告诉它“这个东西被分为某某类”这样一些例子。理想情况下，一个 classifier 会从它得到的训练集中进行“学习”，从而具备对未知数据进行分类预测的能力，这种提供训练数据的过程通常叫做supervised learning(监督学习)。应用场景：银行贷款安全和风险、信用卡持卡用户进行分类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只可能取两个值（即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，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.971Entropy(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.918Entropy(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)-(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为根节点。子节点也重复以上的步骤。就可以建立下以下这可决策树：OutlookHumidityWindWinWinWinLoseWinSunnyOvercastRainHighNormalStrong扫描所有的交易记录对每个候选计数Weak因此，将样本X 指派给类C1：Result =“Win”。即在Outlook = Sunny,Temperature = Hot, Humidity = High, Wind = Strong的情况下这场比赛会赢。 朴素贝叶斯分类算法： 朴素贝叶斯分类基于贝叶斯定理,假设一个属性值对给定类的影响独立于其他属性的值。设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, , Cm。给定一个未知类标号的数据样本X，朴素贝叶斯分类将其分类到类Ci ，当且仅当P(Ci|X) P(Cj|X) 1jm，ji P(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 中属性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(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=“Yes”) = 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=“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.2220.2220.3330.333 = 0.005P(X | PlayTennis =“No”) = 0.6000.4000.8000.600 = 0.115P(X | PlayTennis =“Yes”) P(PlayTennis =“Yes”) = 0.0050.643 = 0.003P(X | PlayTennis =“No”) P(PlayTennis =“No”)= 0.1150.357 = 0.041因此，将样本X 指派给类C2：PlayTennis =“No”。即在Outlook = Sunny,Temperature = Hot, Humidity = High, Wind = Strong的情况下不去打球。支持向量机（SVM）算法： 支持向量机（support vector machine），是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。因此最大化几何间隔成了我们训练阶段的目标。如下图所示：为了简化问题，我们用二维空间来解释这个分类问题。要将图中黑白圆圈分类，中间的直线就是一个分类函数，它可以完全将这些样本分开。一般的，如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。实际上，一个线性函数是一个实值函数（即函数的值是连续的实数），而我们的分类问题（例如这里的二元分类问题回答一个样本属于还是不属于一个类别的问题）需要离散的输出值，例如用1表示某个样本属于类别C1，而用0表示不属于，这时候只需要简单的在实值函数的基础上附加一个阈值即可，通过分类函数执行时得到的值大于还是小于这个阈值来确定类别归属。 例如我们有一个线性函数g(x)=wx+b我们可以取阈值为0，这样当有一个样本xi需要判别的时候，我们就看g(xi)的值。若g(xi)0，就判别为类别C1，若g(xi)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)”那么例子中的频繁项集将产生以下关联规则：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分析算法：一种无监督的机器学习算法，对没有标记（分类）的训练样本进行学习，以发现训练样本集中的结构性知识。这里，所有的标记（分类）是未知的。而聚类则是指将物理或抽象对象的集合分到不同组的分析过程。这些组内成员具有很大的相似性，而组间成员具有很大的相异性。同分类（Classification）不同，聚类不依赖事先预定义的类标记，而需要自己标识。K-Means算法：K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。算法过程如下：1）从N个集合对象随机选取K个对象作为圆心；2）对剩余的每个集合对象测量其到每个质心的距离，并把它归到最近的圆心的类；3）重新计算已经得到的各个类的圆心；4）迭代23步直至新的圆心与原圆心相等或小于指定阈值，即算法收敛结束。PageRank算法：Google的网页排名算法，是一种由根据网页之间相互的超链接计算等级（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（有向图如下：）。 BCCDA 如上图的话，我们可以得到4个网页的PR值如下：PRA=PRB2+PRCPRB=PRA3+PRD2PRC=PRA3+PRD2 PRD=PRA3+PRB2也可以用n*n的矩阵表示该有向图，其中每行代表的是元素指向的节点，如第一行表示存在A节点指向B、C和D的链接。列表示对于指定的节点有多少个指向该节点的节点，如第一列则表示指向A节点的有B和C节点。 M=0111001001100110因为PR值要平均到每个链接，因此将矩阵每行除以每行的链接数可以得到新的矩阵如下： M=01313120010013120012120将矩阵M转置后得到MT M=01211300130001212131200由此我们可以得到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算法的计算是一个迭代的过程，递归直到最后两次的结果近似或者相同，即PR最终收敛，算法结束。人工神经网络：人工神经网络（ANN）简称神经网络，是由具有适应性的简单单元组成的广泛并行互联的网络，它的组织能够模拟生物神经系统对真实世界物体做出的交互反应。可以说人工神经网络是利用人工的方式对生物神经网络的模拟。最早的神经元模型M-P模型如下图所示：其中Ii-1,1表示输入，Y-1,1输出，权值Wi-1,1表示输入的连接强度，证书权值表示兴奋性输入，负数权值表示抑制性输入。表示神经元兴奋时的阈值，当神经元输入的加权和大于时，神经元处于兴奋状态。单输出神经元（感知器）的工作过程：1、从输入端接受输入信息Xi2、根据连接