数据挖掘知识点.doc

数据挖掘知识点：1、 数据挖掘是从大量的数据中挖掘那些令人感兴趣的有用的隐含的先前未知的和不可能有用的模式和知识。数据库DB系统最主要的功能：数据存储、查询处理、事物处理。数据挖掘的主要功能：关联分析、时序模式、聚类分析、分类、偏差检测、预测数据预处理：是从大量的数据属性中提取出对目标有重要影响的属性来降低原始数据的维数，或者是处理一些不好的数据，从而改善实例数据的质量和提高数据挖掘的速度。数据预处理功能：数据集成，数据清理，数据变换，数据简化。2、 数据挖掘的基本算法：1、分类：分类的目的是构造一个分类函数或分类模型（分类器），该模型能把数据库中的数据项映射到某一个给定类别。 分类定义：给定数据库Dt1,t2,tn，元组tiD，类的集合CC1,Cm，分类问题定义为从数据库到类集合的映射f：DC，即数据库中的元组ti分配到某个类Cj中，有Cj ti|f(ti) = Cj，1in，且tiD。ID3算法：ID3算法是国际上最具影响和最早的决策树算法。首先通过检验数据库中的所有字段，找出具有最大信息增益Gian（A)的字段作为决策树碑的一个结点，再根据字段的不同取值建立树的分支，对每个子集分支重复建立下层结点和分支，直到某一子集的结果属于同一类。信息量计算公式： I(s1,s2,sm)=Pi log2(pi) （i=1,m） （S是s个数据样本的集合。类别属性具有m个不同值Ci。si是类Ci中的样本数。pi是任意样本属于类别Ci的概率，并用si/s估计。）由非类别属性A划分为子集的熵(也叫做信息熵)计算公式为：E(A)= (s1j+ +smj)/s * I(s1j， ，smj) （非类别属性A具有v个不同值a1，a2，av。利用属性A将集合S划分为v个子集S1，S2，Sv；其中Sj包含S集合中在属性A上具有值aj的数据样本。 Sij是子集Sj中类Ci的样本数(Sij是子集Sj中类Ci的样本数)。 ）信息增益：Gain(A)= I(s1,s2,sm) E(A)例题：DayoutlookTemperatureHumidityWindPlay ball1晴HotHighWeakNo2晴HotHighStrongNo3多云HotHighWeakYes4有雨mildHighWeakYes5有雨CoolNormalWeakYes6有雨CoolNormalStrongNo7多云CoolNormalStrongYes8晴mildHighWeakNo9晴CoolNormalWeakYes10有雨mildNormalWeakYes11晴mildNormalStrongYes12多云mildHighStrongYes13多云hotNormalWeakYes14有雨mildHighStrongNo类C1运动“适合”，类C2对运动“不适合”I(s1, s2) = I(9, 5) =0.940计算属性天气的熵:：贝叶斯分类方法:贝叶斯分类方法是一种基于统计的学习方法，利用概率统计进行学习分类，如预测一个数据对象属于某个类别的概率。贝叶斯定理：主要算法：朴素贝叶斯分类、贝叶斯信念网络分类算法等。朴素贝叶斯分类:朴素贝叶斯分类算法利用贝叶斯定理来预测一个未知类别的样本属于各个类别的可能性，选择可能性最大的一个类别作为该样本的最终类别。 原理：（1）设样本有n个属性(A1,A2,.,An)，每个样本可看作是n维空间的一个点X=(x1,x2,.,xn)。（2）假定有m个不同的类别，C1,C2,.Cm。X是一个未知类别的样本。预测X的类别为后验概率最大的那个类别，即算法将未知类别的样本X归到类Ci，当且仅当P(Ci|X) P(Cj|X),对于所有的j成立（1jm，ji）即P(Ci|X)最大。（3）根据贝叶斯定理得知 P(Ci|X)=P(X|Ci)P(Ci)/P(X)。P(X)对于所有类为常数，因此只需 P(X|Ci)P(Ci)取最大即可 类的先验概率P(Ci)由P(Ci)=si/s估算 Si训练样本中属于类Ci的样本数，s全部训练样本的样本数。（4）给定具有多属性的数据集，计算P(x|Ci)的开销可能非常大，为降低计算P(x|Ci)的开销，朴素贝叶斯做了类条件独立假设，即假定一个属性值对给定类的影响独立于其他属性值，属性之间不存在依赖关系，则：P(X|Ci)P(x1|Ci)P(x2|Ci).P(xn|Ci)（5）对未知样本X分类，对每个类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。算法描述：函数名：NaiveBayes输入：类别号未知的样本X=x1,x2,xn输出：未知的样本X所属类别号 (1) for j=1 to m (2) 计算X属于每个类别Cj的概率 P(X|Cj)P(x1|Cj)P(x2|Cj).P(xn|Cj); (3) 计算训练集中每个类别Cj的概率P(Cj)； (4) 计算概率值Q = P(X|Cj)* P(Cj); (5) end for (6) 选择计算概率值Q最大的Ci (1=i=m)作为类别 输出。例题：DayoutlookTemperatureHumidityWindPlay ball1晴HotHighWeakNo2晴HotHighStrongNo3多云HotHighWeakYes4有雨mildHighWeakYes5有雨CoolNormalWeakYes6有雨CoolNormalStrongNo7多云CoolNormalStrongYes8晴mildHighWeakNo9晴CoolNormalWeakYes10有雨mildNormalWeakYes11晴mildNormalStrongYes12多云mildHighStrongYes13多云hotNormalWeakYes14有雨mildHighStrongNo使用朴素贝叶斯算法预测未知样本：x=rainy，hot，normal，weak，？属性play为yes还是no的概率。1、 P（play=yes | x）=P（x | play=yes）* P（play=yes） =P（x1| play=yes）* P（x2|play=yes）*.*P(x4 | play=yes)*P(play=yes) P(x1| play=yes)=P(outlook=rainy | play=yes)=3/9 P(x2| play=yes)=P(tem=hot | play=yes)=2/9 P(x3| play=yes)=P(humidity=normal | play=yes)=6/9 P(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/5 P(x2| play=no)=P(tem=hot | play= no)=2/5 P(x3| play=no)=P(humidity=normal | play= no)=1/5 P(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(Xi|Yj)=(nc+l*p)/(n+l)N是类 Yj中的实例总数，nc是类 Yj的训练样例中取值为Xi的样例数，l p例题：序号是否有房婚姻状况年收入拖欠贷款1YesSingle 125KNo2NoMarried100KNo3NoSingle 70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle 85KYes9NoMarried75KNo10NoSingle 90KYes当条件概率为0时，用Laplace估计求X=（yes，single，80k,?）拖欠贷款的属性为yes还是no的概率。设是否有房为x1，婚姻状况为x2,年收入为x3. 1)P(拖欠贷款=yes | x)=P（x | 拖欠贷款=yes） P（拖欠贷款=yes） =P（x1|拖欠贷款=yes） P（x2|拖欠贷款=yes）P(x3|拖欠贷款=yes)P(拖欠贷款=yes)P(x1|拖欠贷款=yes)=(0+31/3)/3+3=1/6P(x2|拖欠贷款=yes)=2/3P(x3|拖欠贷款=yes)= =0.589x3（平均）=(95k+85k+90k)/3=90k2)P(拖欠贷款=no | x)=P(x | 拖欠贷款=no)P(拖欠贷款=no) =P(x1|拖欠贷款=no)P(x2|拖欠贷款=no)P(x3|拖欠贷款=no)P(拖欠贷款=no)P(x1|拖欠贷款=no)=3/7P(x2|拖欠贷款=no)=2/7P(x3|拖欠贷款=no)=X3（平均）=（125k+100k+70k+120k+60k+220k+75k）=110k2、聚类a）聚类（Clustering）是一个将数据集划分为若干组（class）或类（cluster）的过程，并使得同一个组内的数据对象具有较高的相似度；而不同组中的数据对象是不相似的。b）有关的聚类方法（类型）主要有：划分类方法、分层类方法、基于密度类方法、基于网格类方法和基于模型类方法。c）聚类和分类的相同点和不同点分析：一是按照定义区分；二是聚类不依赖于预先定义好的类，它要划分的是未知的；是无指导学习，聚类是观察式学习，而不是示例式学习。（聚类又称分段，是一种对具有共同趋势和模式的数据元组进行分组的方法。） d）无论如何最大程度的实现类中对象相似度最大，类间相似度最小是聚类分析的指导思想。e）数据挖掘对聚类算法的典型要求如下：可伸缩性处理不同类型属性的能力发现任意形状的聚类需要（由用户）决定的输入参数最少处理噪声数据的能力对输入记录顺序不敏感高维问题基于约束的聚类可解释性和可用区间标度变量计算方法：数据标准化：计算绝对偏差的平均值 计算标准度量值 (z-score)：二元变量计算方法：一个二元变量只有两个状态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的变量数目。s 是对象i为0对象j为1的变量数目，t是对象i和j都为0的变量数目。变量的总数是p=q+r+s+t。例题：计算相异度：Name是对象标识，gender是对称的二元变量，其余的属性都是非对