精品文档
数据挖掘重点整理 选择数据挖掘函数
汇总, 分类, 回归, 关联, 聚类 知识点概括
1、 聚类（Clustering）就是将数据分组成为多个类（Cluster）。在同一个类内对象之间具有
较高的相似度，不同类之间的对象差别较大 2、聚类分析中“类”的特征：
聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分 聚类的数目和结构都没有事先假定 3、 聚类方法的目的是寻找数据中：
潜在的自然分组结构a structure of “natural” grouping 感兴趣的关系relationship 4、 聚类分析的研究对象
R型分析----对变量进行分类 Q型分析----对样品进行分类 5、离群点数据挖掘方法简介
? 基于统计的方法 ? 基于距离的方法 ? 基于密度的方法 ? 基于聚类的方法
6、 离群点挖掘中需要处理的几个问题 (1) 全局观点和局部观点
离群点与众不同，但具有相对性。 (2) 点的离群程度
可以通过定义对象的偏离程度来给对象打分——离群因子(Outlier Factor)或离群值得分(Outlier Score)，即都为离群点的情况下，也还有分高和分低的区别。 (3) 离群点的数量及时效性
正常点的数量远远超过离群点的数量，离群点的数量在大规模数据集中所占的比例较低，小于5%甚至1%
7、 离群点的概率定义：
离群点是一个对象，关于数据的概率分布模型，它具有低概率 8、离群点挖掘问题由两个子问题构成：
(1)定义在一个数据集中什么数据是不一致或离群的数据；
(2)找出所定义的离群点的有效挖掘方法。离群点挖掘问题可以概括为如何度量数据偏离的程度和有效发现离群点的问题。
9、为什么会出现离群点？
? 测量、输入错误或系统运行错误所致 ? 数据内在特性所决定 ? 客体的异常行为所致
由于离群点产生的机制是不确定的，离群点挖掘算法检测出的“离群点”是否真正对应实际的异常行为，不是由离群点挖掘算法来说明、解释的，只能由领域专家来解释，离群点挖掘算法只能为用户提供可疑的数据，以便用户引起特别的注意并最后确定是否真正的异常。对于异常数据的处理方式也取决于应用，并由领域专家决策。 精品文档
精品文档
10、离群点挖掘中需要处理的几个问题 (1) 全局观点和局部观点 离群点与众不同，但具有相对性。 (2) 点的离群程度
可以通过定义对象的偏离程度来给对象打分——离群因子(Outlier Factor)或离群值得分(Outlier Score)，即都为离群点的情况下，也还有分高和分低的区别。 (3) 离群点的数量及时效性
正常点的数量远远超过离群点的数量，离群点的数量在大规模数据集中所占的比例较低，小于5%甚至1%
11、一个对象可能相对于所有对象看上去离群，但它相对于它的局部近邻不是离群的
12、通过定义对象的离群程度来给对象打分 ，如都为离群点的情况下，也还有分高和分低的区别。——离群点得分(outlier score)或离群因子(Outlier Factor) 13概率分布模型通过估计用户指定的分布的参数，由数据创建。 14、离群点检测方法准确性的两个指标：检测率、误报率 15、关联规则
关联规则是形如 X ? Y的蕴含表达式, 其中 X 和 Y 是不相交的项集 例子: {Milk, Diaper} ? {Beer} 16、关联规则的强度
– 支持度 Support (s)
? 确定项集的频繁程度
– 置信度 Confidence (c)
? 确定Y在包含X的事务中出现的频繁程度
17、挖掘关联规则
大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务:
1） 频繁项集产生（Frequent Itemset Generation）
– 其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁
项集。
2） 规则的产生（Rule Generation）
其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strong rule） 18、先验原理:
如果一个项集是频繁的，则它的所有子集一定也是频繁的
相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的:
a) 这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪枝
（support-based pruning）
b) 这种剪枝策略依赖于支持度度量的一个关键性质，即一个项集的支持度决不会超过
它的子集的支持度。这个性质也称为支持度度量的反单调性（anti-monotone）。
19、信息的定量描述
衡量信息多少的物理量称为信息量。
若概率很大，受信者事先已有所估计，则该消息信息量就很小； 若概率很小，受信者感觉很突然，该消息所含信息量就很大。
精品文档
精品文档
抛一枚畸形硬币，出现正面与反面的概率分别是1/4，3/4，出现正面与反面时的信息量是多少？
解：出现正面与反面的概率分别是1/4，3/4，它们的信息量是 I(正)= -log p(正)= -log1/4=2 I(反)= -log p(反)= -log3/4=0.415 20、信源含有的信息量是信源发出的所有可能消息的平均不确定性，香农把信源所含有的信息量称为信息熵，是指每个符号所含信息量的统计平均值。m种符号的平均信息量为 H(X)?p(xi)I(xi)??p(xi)logp(xi) ii??21、抛一枚畸形硬币，出现正面与反面的概率分别是1/4，3/4，出现正面与反面时的信息量是多少？
解：出现正面与反面的概率分别是1/4，3/4，信息熵是
q
Hx??pxilogpxi i?1 ??(1/4log1/4?3/4log1/4) ?0.811b/symbol
22、条件熵
在给定yj条件下，xi的条件自信息量为I(xi| yj), X集合的条件熵H(X|yj)为 H(X|y)?p(xi|yj)I(xi|yj)ji 在给定Y(即各个yj )条件下,X集合的条件熵H(X|Y) H(X|Y)?p(yj)H(X|yj) j条件熵H(X|Y)表示已知Y后，X的不确定度 23、ID3算法小结
ID3算法主要针对属性选择问题。是决策树学习方法中最具影响和最为典型的算法。 该方法使用信息增益度选择测试属性。
当获取信息时，将不确定的内容转为确定的内容，因此信息伴着不确定性。 从直觉上讲，小概率事件比大概率事件包含的信息量大。
ID3算法是一种经典的决策树学习算法，由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变为最小的属性，以构造一颗熵值下降最快的决策树，到叶子节点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于同一类。 24、决策树基础
有向无环 二叉/多叉树
父节点：没有子节点的节点
内部节点：有父节点、子节点的节点 叶节点：有父节点没有子节点的节点 25、决策树算法
决策树的表示
决策树的基本组成部分：决策结点、分支和叶子。
?????????精品文档
精品文档
决策树中最上面的结点称为根结点。是整个决策树的开始。每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或者决策.通常对应待分类对象的属性。 每个叶结点代表一种可能的分类结果
在沿着决策树从上到下的遍历过程中，在每个结点都有一个测试。对每个结点上问题的不同测试输出导致不同的分枝，最后会达到一个叶子结点。这一过程就是利用决策树进行分类的过程，利用若干个变量来判断属性的类别 26、决策树作用：
? 通过训练集 ? 算法指导下 ? 生成决策树 ? 新数据进行划分 ? 否则是“三拍”决策
27、决策树的优点
1、推理过程容易理解，决策推理过程可以表示成If Then形式； 2、推理过程完全依赖于属性变量的取值特点；
3、可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量的数目提供参考
28、1）决策树技术发现数据模式和规则的核心是归纳算法。归纳是从特殊到一般的过程。归纳推理从若干个事实中表征出的特征、特性和属性中，通过比较、总结、概括而得出一 个规律性的结论。归纳推理试图从对象的一部分或整体的特定的观察中获得一个完备且正确的描述。即从特殊事实到普遍性规律的结论。归纳对于认识的发展和完善具有重要的意义。人类知识的增长主要来源于归纳学习
2）归纳学习的过程就是寻找一般化描述的过程。这种一般性描述能够解释给定的输入数据，并可以用来预测新的数据。
3）归纳学习由于依赖于检验数据，因此又称为检验学习。归纳学习存在一个基本的假设：任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函数。该假定是归纳学习的有效性的前提条件。 29、与决策树相关的重要算法：CLS, ID3，C4.5，CART 30、决策树解决分类问题的一般方法
通过以上对分类问题一般方法的描述，可以看出分类问题，一般包括两个步骤： 1、模型构建（归纳）
通过对训练集合的归纳，建立分类模型。 2、预测应用（推论）
根据建立的分类模型，对测试集合进行测试。
一、判断题（10*2=20分） 二、简答题（4*5=20分）
1）什么是数据挖掘（汇总） 数据挖掘（从数据中发现知识）
数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在精品文档
精品文档
其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 2）K-均值原理（聚类）
是一种得到最广泛使用的聚类算法。 它是将各个聚类子集内的所有数据样本
的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。
K-均值聚类的处理流程如下。首先，随机选择k个对象，每个对象都初始地代
表一个类的平均值或中心。对剩余的对象，根据其与各自类中心的距离，将它赋给最近的类。然后重新计算每个类的平均值。这个过程不断重复，直到准则函数收敛。
3）Apriori算法（关联规则中先验算法，关联）
Apriori算法是一种最有影响的挖掘布尔关联规则大（频繁）项目集的算法。
它使用一种称作逐层搜索的迭代算法，通过k-项集用于探索（k+1）-项集。已经为大部分商业产品所使用。
4）先验、后验概率（分类）
设X表示属性集，Y表示类变量，如果类变量和属性之间的关心不确定，那么我们可以 把X和Y看作随机变量，用P（Y|X）以概率的方式捕捉二者之间的关系，这个条件概率又称为Y的后验概率，与之相对的P(Y)称为Y的先验概率。
5）决策树、熵的定义（分类）
决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成
可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。
信源含有的信息量是信源发出的所有可能消息的平均不确定性，香农把信源所含有的信息量称为信息熵，是指每个符号所含信息量的统计平均值。
6）离群点和离群点检测
Hawkins的定义：离群点是在数据集中偏离大部分数据的数据，使人怀疑这些数据
的偏离并非由随机因素产生，而是产生于完全不同的机制。
Weisberg的定义：离群点是与数据集中其余部分不服从相同统计模型的数据。 Samuels的定义：离群点是足够地不同于数据集中其余部分的数据。 Porkess的定义：离群点是远离数据集中其余部分的数据
7）分类和聚类的区别（异同点）
答： 聚类是非监督分类，仅根据在数据中发现的描述对象及其关系的信息，用
类（簇）标号创建对象的标记，而分类是监督分类，使用由类标号已知的对象开发的模型，对新的、无标记的对象赋予类标号。
三、应用题（4*15=60分）
1）系统聚类法
系统聚类法的基本思想 精品文档
(整理)数据挖掘复习
