数据挖掘考试重点.

Review数据预处理3度量数据的中心趋势•均值(代数度量)(样本vs.总体):Note:n样本大小，N总体大小.–加权算术均值:–截断均值:去掉高低极端值•中位数:–奇数则为有序集的中间值,否则为中间两个数的平均–(基于分组数据)可以插值估计•众数Mode–出现频率最高的值(不惟一/每个值出现一次则没有)–1/2/3个众数-〉单峰的,双峰的,三峰的–Empiricalformula:niixnx11niiniiiwxwx11widthfreqfreqnLmedianmediansmall))(2/(1)(3medianmeanmodemeanNx4闵可夫斯基距离特殊形式•h=1:Manhattan(cityblock,L1norm)distance曼哈顿距离（L1范数）–E.g.,theHammingdistance:thenumberofbitsthataredifferentbetweentwobinaryvectors•h=2:(L2norm)Euclideandistance•h.上确界“supremum”(Lmaxnorm,Lnorm)distance.–Thisisthemaximumdifferencebetweenanycomponent(attribute)ofthevectors)||...|||(|),(2222211ppjxixjxixjxixjid||...||||),(2211ppjxixjxixjxixjid5Example:MinkowskiDistanceDissimilarityMatricespointattribute1attribute2x112x235x320x445Lx1x2x3x4x10x250x3360x46170L2x1x2x3x4x10x23.610x32.245.10x44.2415.390Lx1x2x3x4x10x230x3250x43150Manhattan(L1)Euclidean(L2)Supremum6相关分析(名义数据NominalData)•Χ2(chi-square)test开方检验–σij是(ai,bj)的观测频度（实际计数）–eij是(ai,bj)的期望频度–N数据元组的个数属A性a1a2iacb1Bb2jbr(A=ai,B=bj)rjijijijciee1212)(NbBcountaAcountejiij)(*)(Χ2值越大,相关的可能越大对Χ2值贡献最大的项，其实际值与期望值相差最大的相相关不意味着因果关系7Chi-Square卡方值计算:例子•Χ2(chi-square)计算(括号中的值为期望计值，由两个类别的分布数据计算得到)•结果表明like_fiction和play_chess关联93.507840)8401000(360)360200(210)21050(90)90250(22222PlaychessNotplaychessSum(row)看小说250(90)200(360)450不看小说50(210)1000(840)1050Sum(col.)30012001500901500300*450)(*)(11Ncountcounte下棋看小说关联规则挖掘9Apriori算法的步骤•Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。•Apriori算法将发现关联规则的过程分为两个步骤：–通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；–利用频繁项集构造出满足用户最小信任度的规则。•挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。10频繁项集•为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），Apriori算法引入潜在频繁项集的概念。•若潜在频繁k项集的集合记为Ck，频繁k项集的集合记为Lk，m个项目构成的k项集的集合为，则三者之间满足关系LkCk。•构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。kmCkmC11关联规则的性质•性质1：频繁项集的子集必为频繁项集。•性质2：非频繁项集的超集一定是非频繁的。•Apriori算法运用性质1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。–潜在频繁k项集的集合Ck是指由有可能成为频繁k项集的项集组成的集合。•以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。12Apriori:一种候选产生-测试方法•频繁项集的任何子集必须是频繁的–如果{beer,diaper,nuts}是频繁的,{beer,diaper}也是–每个包含{beer,diaper,nuts}的事务也包含{beer,diaper}•Apriori剪枝原则:–如果一个项集不是频繁的,将不产生/测试它的超集!•方法:–由长度为k的频繁项集产生长度为(k+1)的候选项集,并且–根据DB测试这些候选•性能研究表明了它的有效性和可伸缩性13Apriori算法—一个例子数据库TDB第1次扫描C1L1L2C2C2第2次扫描C3L3第3次扫描TidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2分类和预测•简答题：–朴素贝叶斯分类的主要思想–决策树分类的主要步骤•选择题：–SVM使用一个非线性映射把原始训练数据变换到高维空间中–在新的维上,搜索线性优化分离超平面hyperplane(i.e.,“决策边界”)–使用supportvectors(“基本”选择元组)和边缘margins(由支持向量定义)发现超平面16支持向量机的一般哲学SupportVectorsSmallMargin边界LargeMargin聚类分析•主要聚类方法分类•划分方法（PartitioningMethods）•K-means（算法步骤）、k-中心点•层次方法（HierarchicalMethods）•Birch、CURE、Chameleon•基于密度的方法（Density-BasedMethods）•DBSCAN、OPTICS•基于网格的方法（Grid-BasedMethods）•STING、CLIQUE•基于模型的聚类方法（Model-BasedClustering离群点分析方法基于统计学方法基于距离的方法基于偏差的方法基于密度的方法辨析在信用卡欺诈或者电信欺诈检测中，哪种离群点方法更加可靠序列数据挖掘•序列模式挖掘–GSP–SPADE–PrefixSpan名词填空•SVM、OLAP、OutlierDetection、NaïveBayesianClassifier、DecisionTree