数据挖掘知识点

《数据挖掘知识点》由会员分享，可在线阅读，更多相关《数据挖掘知识点（12页珍藏版）》请在装配图网上搜索。

1、数据挖掘知识点：一、数据挖掘是从大量的数据中挖掘那些令人感兴趣的有用的隐含的先前未知 的和不可能有用的模式和知识。数据库DB系统最主要的功能：数据存储、查询处理、事物处理。数据挖掘的主要功能：关联分析、时序模式、聚类分析、分类、偏差检测、预测数据预处理:是从大量的数据属性中提取出对目标有重要影响的属性来降低原始 数据的维数，或者是处理一些不好的数据，从而改善实例数据的质量和提高数据 挖掘的速度。数据预处理功能：数据集成，数据清理，数据变换，数据简化。二、数据挖掘的基本算法：1、分类：分类的目的是构造一个分类函数或分类模型(分类器)，该模型能把数 据库中的数据项映射到某一个给定类别。分类定义:给

2、定数据库D = t1,t2,tn，元组ti D，类的集合C = C1, ,Cm， 分类问题定义为从数据库到类集合的映射 D C，即数据库中的元组ti分配 到某个类 Cj 中，有 Cj = tilf(ti) = Cj，IWiWn，且 tiD。ID3算法：ID3算法是国际上最具影响和最早的决策树算法。首先通过检验数据库中的所有字段，找出具有最大信息增益Gian (A)的字段作 为决策树碑的一个结点，再根据字段的不同取值建立树的分支，对每个子集分支 重复建立下层结点和分支，直到某一子集的结果属于同一类。信息量计算公式：I(s1,s2,sm)=EPi log2(pi) (i=1,m)(S是s个数据样本

3、的集合。类别属性具有m个不同值Ci。si是类Ci中的样本数。pi是任意样本属于类别Ci的概率，并用si/s估计。) 由非类别属性A划分为子集的熵(也叫做信息熵)计算公式为： E(A)= E (s1j+ +smj)/s * I(s1j， ，smj)(非类别属性A具有v个不同值a1，a2,，av。利用属性A将集合S划Da youtlookTemperatu Humidity reWindPlay ball1晴HotHighWeakNo2晴HotHighStrong No3多云HotHighWeakYes4有雨mildHighWeakYes5有雨CoolNormalWeakYes6有雨CoolNor

4、malStrongNo7多云CoolNormalStrong Yes8晴mildHighWeakNo9晴CoolNormalWeakYes10有雨mildNormalWeakYes11晴mildNormalStrong Yes12多云mildHighStrong Yes13多云hotNormalWeakYes14有雨mildHighStrong No分为v个子集S1, S2,，Sv；其中Sj包含S集合中在属性A上具有值aj 的数据样本。Sij是子集Sj中类Ci的样本数(Sij是子集Sj中类Ci的样本数)。)信息增益：Gain(A)= I(s1,s2,sm) - E(A)例题：类C1运动=“适合

5、”，类C2对运动=“不适合”I(s1, s2) = I(9, 5) =0.940计算属性天气的熵:：54E(天气)=14 /(23) + 14 /(4，0)+ 乏 I (3,2) = 0.97114Gain (天气)=I (s1,s2) - E (天气) =0.246天气C1C2l(p n)晴朗230.971多云400有雨320.971Gain (温度)=0.029Gain (湿度)=0.151Gain (风况)=0.048贝叶斯分类方法：贝叶斯分类方法是一种基于统计的学习方法，利用概率统计进行学习分类，如预 测一个数据对象属于某个类别的概率。贝叶斯定理:P( H | X)=P(X | H)P

6、(H)主要算法：朴素贝叶斯分类、贝叶斯信念网络分类算法等。朴素贝叶斯分类：朴素贝叶斯分类算法利用贝叶斯定理来预测一个未知类别的样本属于各个类别 的可能性，选择可能性最大的一个类别作为该样本的最终类别。原理：(1) 设样本有n个属性(A1,A2,.,An)，每个样本可看作是n维空间的一个点 X=(x1,x2,.,xn)。(2) 假定有m个不同的类别，C1,C2,.Cm。X是一个未知类别的样本。预测X 的类别为后验概率最大的那个类别，即算法将未知类别的样本X归到类Ci，当 且仅当P(Ci|X) P(CjlX),对于所有的成立(1WjWm，j尹i)即 P(CilX)最大。(3) 根据贝叶斯定理得知P

7、(CilX)=P(XlCi)P(Ci)/P(X)。P(X)对于所有类为常数，因此只需P(XlCi)P(Ci)取最大即可类的先验概率P(Ci)由P(Ci)=si/s估算Si训练样本中属于类Ci的样本数，s全部训练样本的样本数。(4) 给定具有多属性的数据集，计算P(xlCi)的开销可能非常大，为降低计算 P(xlCi)的开销，朴素贝叶斯做了类条件独立假设，即假定一个属性值对给定类的 影响独立于其他属性值，属性之间不存在依赖关系，则：P(XlCi)=P(x1lCi)P(x2lCi).P(xnlCi)(5) 对未知样本X分类，对每个类Ci，分别计算P(XlCi)P(Ci)。样本X被指派到类Ci，当且

8、仅当P(XlCi)P(Ci) P(XlCj)P(Cj), (IWjWm，j尹i)即 X 被指派到其 P(XlCi)P(Ci) 最大的类Ci。算法描述：函数名：NaiveBayes输入：类别号未知的样本X=x1,x2,xn输出：未知的样本X所属类别号(1) for j=1 to m(2) 计算X属于每个类别Cj的概率P(XlCj)=P(x1lCj)P(x2lCj).P(xnlCj);(3) 计算训练集中每个类别Cj的概率P(Cj)；(4) 计算概率值 Q = P(XlCj)* P(Cj);(5) end for(6) 选择计算概率值Q最大的Ci (1=i=m)作为类别输出。例题：Da youtl

9、ookTemperatu Humidity reWindPlay ball1晴HotHighWeakNo2晴HotHighStrong No3多云HotHighWeakYes4有雨mildHighWeakYes5有雨CoolNormalWeakYes6有雨CoolNormalStrongNo7多云CoolNormalStrong Yes8晴mildHighWeakNo9晴CoolNormalWeakYes10有雨mildNormalWeakYes11晴mildNormalStrong Yes12多云mildHighStrong Yes13多云hotNormalWeakYes14有雨mildHi

10、ghStrong No使用朴素贝叶斯算法预测未知样本：x= rainy, hot, normal, weak,? 属性 play 为 yes 还是 no 的概率。1、P (play=yes I x) =P (x I play=yes) * P (play=yes)=P ( xj play=yes ) * P ( x2Iplay=yes ) *.*P(x4 I play=yes)*P(play=yes)P(x1| play=yes)=P(outlook=rainy | play=yes)=3/9P(x2| play=yes)=P(tem=hot | play=yes)=2/9P(x3| play

11、=yes)=P(humidity=normal | play=yes)=6/9P(x4| play=yes)=P(wind=weak | play=yes)=6/9所以，P(play=yes | x)=3/9 * 2/9 * 6/9 * 6/9 * 9/14=0.0212、P(play=no | x)=P(x | play=no) * P(play=no)=P(x1|play=no) * P(x2|play=no) * P(x4|play=no) * P(play=no)P(x1| play=no)=P(outlook=rainy | play=no)=2/5P(x2| play=no)=P(

12、tem=hot | play= no)=2/5P(x3| play=no)=P(humidity=normal | play= no)=1/5P(x4| play=no)=P(wind=weak | play=no)=2/5所以，P (play=no| x) =2/5 * 2/5 * 1/5 * 2/5 * 5/14=0.0045拉普拉斯（Laplace ）：朴素贝叶斯分类算法在计算概率的时候存在概率=0,及 概率值可能很小的情况，所以，在某些情况下，需要考虑条件概率的Laplace估 计和解决小概率相乘溢出问题。条件概率=0，用条件概率的Laplace估计。Laplace估计定义：P（Xil

13、Yj）=（nc+l*p）/（n+l）N是类Yj中的实例总数，nc是类Yj的训练样例中取值为Xi的样例数，l p 例题：序号是否有房婚姻状况年收入拖欠贷款1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes当条件概率为0时，用Laplace估计求X=（yes，single，80k,?）拖欠贷款的属 性为yes还是no的概率。设是否有房

14、为X1，婚姻状况为x2,年收入为x3.1）P（拖欠贷款=yes | x）=P （x |拖欠贷款=yes）X P （拖欠贷款=yes）=P （x1|拖欠贷款=yes）X P （x2|拖欠贷款=yes）XP（x3|拖欠贷款=yes） X P（拖欠贷款=yes）P（x1| 拖欠贷款=yes）=（0+3 X 1/3）/3+3=1/6P（x21 拖欠贷款=yes）=2/3P（x3l拖欠贷款=yes）= / 算=0.58912兀。yescix3 （平均）=（95k+85k+90k）/3=90k2）P（拖欠贷款=眼l x）=P（x l拖欠贷款=no） X P（拖欠贷款=no）=P（x11拖欠贷款=no） X

15、 P（x21拖欠贷款=no） X P（x3|拖欠贷款=no）X P（拖欠贷款=no）P（x11 拖欠贷款=no）=3/7P（x21 拖欠贷款=no）=2/7180-110P（x3|拖欠贷款=no）=。2% =34 2冗。ciX3 （平均）=（125k+100k+70k+120k+60k+220k+75k） =110k2、聚类a）聚类（Clustering）是一个将数据集划分为若干组（class）或类（cluster）的 过程，并使得同一个组内的数据对象具有较高的相似度；而不同组中的数据对象 是不相似的。b）有关的聚类方法（类型）主要有：划分类方法、分层类方法、基于密度类方 法、基于网格类方法和

16、基于模型类方法。c）聚类和分类的相同点和不同点分析：一是按照定义区分；二是聚类不依赖于 预先定义好的类，它要划分的是未知的；是无指导学习，聚类是观察式学习，而 不是示例式学习。（聚类又称分段，是一种对具有共同趋势和模式的数据元组进 行分组的方法。）d）无论如何最大程度的实现类中对象相似度最大，类间相似度最小是聚类分析 的指导思想。e）数据挖掘对聚类算法的典型要求如下： 可伸缩性处理不同类型属性的能力发现任意形状的聚类需要(由用户)决定的输入参数最少处理噪声数据的能力对输入记录顺序不敏感高维问题基于约束的聚类可解释性和可用区间标度变量计算方法：数据标准化：计算绝对偏差的平均值s = n(I x

17、m I +1 x m I +.+1 x m I)f 1f f2ffnf fmf=+.+%).计算标准度量值(z-score)：x - mZ = 祈。 fifSf二元变量计算方法：一个二元变量只有两个状态0或1,0表示该变量为空，1表示该变量存在。两个变量0和1没有优先权，则二元变量为对称，相反，如果两个状态输出不是 同等重要，那么该二元变量是不对称的。对称的二元变量计算其相异度公式d(i,j) = (r+s)/(q+r+s+t)非对称的二元变量：d(i,j) = (r+s)/(q+r+s)其中q表示对象i和j都为1的变量数目，r是对象i为1而对象j为0的变量 数目。，是对象i为0对象j为1的变

18、量数目，t是对象i和j都为0的变量数 目。变量的总数是p=q+r+s+t。例题：计算相异度：Name是对象标识，gender是对称的二元变量，其余的属性都是非对称的二元变 量。(计算非对称二元变量)NameGenderFeverCoughTest-1Test-2Tcst-3Test-4JackMYNPNNNMaryFYNPNP J酒看原图JimMYPNNNM d(Jack,Mary) = (0+1)/(2+0+1)=0.33d(Jack,Jim) = (1+1)/(1+1+1)=0.67d(Jim,Mary) = (1+2)/(1+1+2)=0.75上面的值显示Jim和Mary不可能有相似的疾病，因为他们有着最高的相似度。在这三人中，Jack和Mary最有可能有类似的疾病。相对于对称的二元变量，不对称的二元变量基于不对称的二元变量的相似度称为 非恒定的相似度，且变量的两个状态的重要性不同，可用d(i,j)=(b+c)/(a+b+c)