云南大学数据仓库与数据挖掘重点.docx

1、云南大学数据仓库与数据挖掘重点KDD定义及七个步骤 记步骤名字，单词1. Data Cleaning2. Data Integration3. Data Selection4. Data Transformation5. Data Mining6. Pattern Evaluation(模式评估)7. Knowledge定义：从大型数据库中的大量数据中提取有趣的（非平凡的，隐含的，以前未知的和可能有用的）信息或模式5-number summaryMinimum, Q1(第一个四分位数), M(中位数), Q3(第三个四分位数), Maximum分箱的方法(计算)Numeric Nominal

2、属性的取值(string)怎么放入聚类算法里算皮尔逊系数，卡方校验卡方校验：卡方检验就是统计样本的实际观测值与理论推断值之间的偏离程度，实际观测值与理论推断值之间的偏离程度就决定卡方值的大小，卡方值越大，越不符合；卡方值越小，偏差越小，越趋于符合，若两个值完全相等时，卡方值就为0，表明理论值完全符合。皮尔逊系数：rA，B 0，A和B正相关（A的值随B增加）。值越高，相关性越强。rA，B = 0：独立; rA，B 0：负相关A和B是A和B的相应标准偏差n是元组的个数数据间的离散化三种属性：Nominal - 来自无序集合的值，例如颜色，职业Ordinal - 来自有序集合的值，例如军事或学术级别

3、Continuous - 实数，例如整数或实数离散化：1.将连续属性的范围划分为间隔2.一些分类算法仅接受分类属性。3.通过离散化减少数据大小4.准备进一步分析apriori,fp-tree算法计算详细步骤，以及这两个算法的区别常见的决策树算法的终止条件(1)：属性不是纯的怎么区分终止条件：Tree-Growth实际上是一个递归过程,终止有两种方式：第一种方式是如果某一节点的分支所覆盖的样本都属于同一类的时候,那么递归就可以终止,该分支就会产生一个叶子节点.还有一种方式就是，如果某一分支覆盖的样本的个数如果小于一个阈值，那么也可产生叶子节点，从而终止Tree-Growth。如何防治overfi

4、tting：在决策树构造时，由于训练数据中的噪音或孤立点，许多分枝反映的是训练数据中的异常，使用这样的判定树对类别未知的数据进行分类，分类的准确性不高。因此试图检测和减去这样的分支，检测和减去这些分支的过程被称为树剪枝。树剪枝方法用于处理过分适应数据问题。通常，这种方法使用统计度量，减去最不可靠的分支，这将导致较快的分类，提高树独立于训练数据正确分类的能力。朴素贝叶斯原理，算法(0概率事件如何纠正)贝叶斯公式：在X发生的条件下，事件Cj发生的概率拉普拉斯校准由于训练量不足，分类器质量会大大降低。为了解决这个问题，我们引入Laplacian校准，它的思想非常简单，就是对每类别下所有划分的计数加1

5、，这样如果训练样本集数量充分大时，并不会对结果产生影响，并且解决了上述频率为0的尴尬局面。基尼系数，信息增益，xxxxx,优缺点的区别D:数据集 n:类的数量 pj:D中的某个类D如果被分成两个类:规则的覆盖度和准确度trigger相关方面(if 和 then规则)ncovers为覆盖的元组数ncorrect为R正确分类的元组数 如果规则被X满足，则称该规则被触发。例如，假设有：X=(age=youth,income=medium,student=yes,credit_rating=fair)想根据buys_computer对X分类。X满足R1，触发该规则。 如果R1是唯一满足的规则，则该规则

6、被激活，返回X的分类预测。注意，触发并不总意味着激活，因为可能有多个规则被满足！ 可能存在的问题：（1）如果多个规则被触发，但是它们指定了不同的类（2）没有一个规则被X满足。 解决办法：（1）如果多个规则被触发，则需要一种解决冲突的策略来决定激活哪一个规则，并对X指派它的类预测。由许多可能的策略。我们考察两种，即规模序和规则序。 规模序：把最高优先权赋予具有“最苛刻”要求的被触发的规则，其中苛刻性用规则前件的规模度量。也就是说，激活具有最多属性测试的被触发的规则。 规则序：预先确定规则的优先次序。这种序可以是基于类的或基于规则的。 基于类的序：类按“重要性”递减排序，如按普遍性的降序排序。作为

7、选择，它们也可以根据每个类的误分类代价排序。每个类中的规则（可能有很多）是无序的，当然，它们也不必要有序，因为它们都预测相同的类，所以不会存在冲突问题。 基于规则的序：根据规则质量的度量，如准确率、覆盖率或规模（规则前件中属性测试数），或者根据领域专家的建议，把规则组织成一个优先权列表。在使用规则排序时，规则集称为决策表。使用规则序，最先出现在决策表中的被触发的规则具有最高优先权，因此激活它的类预测。满足X的其他规则都被忽略。大部分基于规则的分类系统都使用基于类的规则序策略。 （2）没有一个规则被X满足的条件下，我们可以建立一个省缺或默认规则（条件为空），根据训练集指定一个默认类。这个类可以是

8、多数类，或者不被任何规则覆盖的元组的多数类。当且仅当没有其他规则覆盖X时，最后才使用默认规则（该规则被激活）。k-means计算方法，适用环境，优缺点，复杂度，kmeans，elkan kmeans，mini batch kmeansk-means算法四步骤：1.将对象分区为k个非空子集2.计算种子点作为当前分区的簇的质心（质心是簇的中心，即平均点）3.使用最近的种子点将每个对象分配给群集4.回到第2步，在没有新的任务时停止当结果簇是密集的，而且簇和簇之间的区别比较明显时，K-Means的效果较好。对于大数据集，K-Means是相对可伸缩的和高效的，它的复杂度是 O(nkt)，n 是对象的个数

9、，k 是簇的数目，t 是迭代的次数，通常 k n，且 t n，所以算法经常以局部最优结束。缺点：1.仅在平均值已定义时适用。(分类数据不适用)2.需要事先指定k，簇的数量3.无法处理嘈杂的数据和异常值(由于具有极大值的对象可能实质上扭曲数据的分布)4.不适合发现具有非凸形状的簇平均值mean，众数mode，中值medianJaccard系数：jaccard index又称为jaccard similarity coefficient用于比较有限样本集之间的相似性和差异性jaccard相似度的缺点是值适用于二元数据的集合。聚类算法中的方法都要了解PAM算法在存在噪声和异常值的情况下，Pam比k均

10、值更稳健，因为中位数受到异常值或其他极值的影响小于均值Pam可以有效地处理小型数据集，但对于大型数据集不能很好地扩展。BRICH算法cf treeCF树是一种高度平衡树，用于存储层次聚类的聚类功能 树中的非叶节点具有后代或“子”非叶节点存储其子节点的CF的总和CF树有两个参数分支因子：指定最大子项数。threshold：存储在叶节点处的子簇的最大直径ROCK算法similiardifferent什么时候使用link算法要掌握第二章：平均值，中位数，模式；5数概括；数据类型的对应处理与转换；判定属性是否关联（例如生日与年龄）皮尔森，卡方校验；抽样方法； 345规则数据离散化第六章：朴素贝叶斯；分

11、类标签纯化；0概率事件；if-then 的准确度覆盖度，触发与激活；分裂规则；第七章：kmeans实现及其复杂度；算法的分类；相似度相异度结合二进制计算；杰科达。；交叉验证fp-tree 重复问题的解决+支持度排序+条件模式基Closed pattern and max pattern 闭频繁项集（closed frequent itemset）：当项集X是频繁项集，且数据集D中不存在X的真超集Y，使得X和Y的支持度相等，则X是闭频繁项集。闭频繁项集的表示是无损压缩，不会丢失支持度的信息。通过闭频繁项集可以反推出所有的频繁项集以及相应的支持度 极大频繁项集（maximal frequent i

12、temset）：当项集X是频繁项集，且数据集D中不存在X的真超集Y，使得Y是频繁项集，则X是极大频繁项集。极大频繁项集的表示是有损压缩，失去了频繁项集的支持度信息，我们可以根据极大频繁项集判断任意项集是否是频繁的，但无法得到相应的支持度联机事务处理OLTP（on-line transaction processing） 主要是执行基本日常的事务处理，比如数据库记录的增删查改。比如在银行的一笔交易记录，就是一个典型的事务。OLTP的特点一般有：1.实时性要求高。我记得之前上大学的时候，银行异地汇款，要隔天才能到账，而现在是分分钟到账的节奏，说明现在银行的实时处理能力大大增强。2.数据量不是很大，

13、生产库上的数据量一般不会太大，而且会及时做相应的数据处理与转移。3.交易一般是确定的，比如银行存取款的金额肯定是确定的，所以OLTP是对确定性的数据进行存取4.高并发，并且要求满足ACID原则。比如两人同时操作一个银行卡账户，比如大型的购物网站秒杀活动时上万的QPS请求。联机分析处理OLAP（On-Line Analytical Processing） 是数据仓库系统的主要应用，支持复杂的分析操作，侧重决策支持，并且提供直观易懂的查询结果。典型的应用就是复杂的动态的报表系统。OLAP的特点一般有：1.实时性要求不是很高，比如最常见的应用就是天级更新数据，然后出对应的数据报表。2.数据量大，因为

14、OLAP支持的是动态查询，所以用户也许要通过将很多数据的统计后才能得到想要知道的信息，例如时间序列分析等等，所以处理的数据量很大;3.OLAP系统的重点是通过数据提供决策支持，所以查询一般都是动态，自定义的。所以在OLAP中，维度的概念特别重要。一般会将用户所有关心的维度数据，存入对应数据平台。区别：OLTP即联机事务处理，就是我们经常说的关系数据库，增删查改就是我们经常应用的东西，这是数据库的基础；TPCC(Transaction Processing Performance Council)属于此类。OLAP即联机分析处理，是数据仓库的核心部心，所谓数据仓库是对于大量已经由OLTP形成的数据的一种分析型的数据库，用于处理商业智能、决策支持等重要的决策信息；3-4-5 rule