《数据仓库与数据挖掘分解.docx》由会员分享，可在线阅读，更多相关《数据仓库与数据挖掘分解.docx（16页珍藏版）》请在三一文库上搜索。
1、数据仓库与数据挖掘1. 数据挖掘（Data Mining）概念从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在价值的信息和知识的过程。简单的说，数据挖掘就是从大量数据中提取或“挖掘”知识，因此又被称为数据库中的知识发现(Knowledge Discovery in Database, KDD) 2. 数据挖掘的类型按方法分：直接数据挖掘：对某个变量建立一个模型；包括分类、估值和预测间接数据挖掘：在所有的变量中建立起某种关系； 如相关性分组或关联规则，聚类，描述和可视化，及复杂数据挖掘按任务分：Prediction MethodsUse
2、some variables to predict unknown or future values of other variables.Description MethodsFind human-interpretable patterns/rules that describe given data. 3. 数据挖掘&知识发现kDD的关系：知识发现（Knowledge Discovery in Databases）是用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后隐藏的知识，称为数据库中的知识发现。所谓基于数据库的知识发现（KDD）是指从大量数据中提取有效的、新颖
3、的、潜在有用的、最终可被理解的模式的非平凡过程。 (1) KDD 是 “数据挖掘”的一种更广义的说法；(2) 数据挖掘是整个 KDD 过程的核心。4. 频繁模式 数据库中出现频繁的模式(项集,序列,等等)可信度（Confidence） 设W 中支持物品集A 的事务中，有c 的事务同时也支持物品集B，c称为关联规则AB 的可信度。支持度（Support） 设W中有s的事务同时支持物品集A 和B，s 称为关联规则AB 的支持度。 最小支持度 表示规则中的所有项在事务中出现的频度最小可信度 表示规则中左边的项(集)的出现暗示着右边的项(集)出现的频度频繁集 支持度大于或等于supmin的项集称为频繁
4、项集，满足最小支持度的项集5. FP-树 构建1） 扫描事务数据库D一次,得到频繁项的集合F及它们的支持度.将F按支持度降序排列成L,L是频繁项的列表.2） 创建FP-树的根, 标注其为NULL.对D中的每个事务进行以下操作:3） 根据 L中的次序对事务中的频繁项进行选择和排序. 设事务中的已排序的频繁项列表为p|P,其中p表示第一个元素,P表示剩余的列表.调用insert_Tree(p|P,T).6. 分类的定义分类是指把数据样本映射到一个事先定义的类中的学习过程，即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类. 7. 分类过程获取数据：数据的表示（图像文字、指纹，波形-
5、脑电图、心电图、机械振动波等，物理数据-既包含数值型数据，也包含描述型数据，逻辑数据-只有两种取值的描述型的数据）输入数据、对数据进行量化预处理：去除噪声数据、对缺失值进行处理数据集成或者变换 （维数灾难，降维）分类器设计：划分数据集（给定带类标号的数据集，并且把数据集划分为两个部分：训练集和测试集）分类器构造（利用训练集构造分类器，也就是建立分类模型）分类器测试（利用测试集对分类器的分类性能进行评估）分类决策：对未知类标号的数据样本（测试样本）进行分类8. 分类的评价准则给定测试集Xtest=(xi,yi)|i=1,2,NN表示测试集中的样本个数xi表示测试集中的数据样本yi表示数据样本xi
6、的类标号对于测试集的第j个类别，假设被正确分类的样本数量为TPj被错误分类的样本数量为FNj其他类别被错误分类为该类的样本数据量为FPj 精确度：代表测试集中被正确分类的数据样本所占的比例 查全率：表示在本类样本中被正确分类的样本所占的比例 查准率：表示被分类为该类的样本中，真正属于该类的样本所占的比例 F-measure：是查全率和查准率的组合表达式 几何均值 ：是各个类别的查全率的平方根 9. 决策树的基本概念适用于离散值属性、连续值属性采用自顶向下的递归方式产生一个类似于流程图的树结构在根节点和各内部节点上选择合适的描述属性，并且根据该属性的不同取值向下建立分枝 10. 决策树的优点：1
7、）进行分类器设计时，决策树分类方法所需时间相对较少2）决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式3）可以将决策树中到达每个叶节点的路径转换为IFTHEN形式的分类规则，这种形式更有利于理解 决策树的难点： 1）如何选择一个好的分支取值 好的分支取值可以加快决策树的生长，更重要的是产生结构好的决策树 相反，差的分支取值不但影响决策树的生长，更重要的是产生的决策树分支过细、结构差，难以发 现有用的规则信息。2）取信息增益（Information Gain）较大的对应划分11. ID3是采用“信息增益”来选择分裂属性的。虽然这是一种有效的方法，但其具有明显的倾向性，即它倾向于选择取
8、值较多的属性; C4.5算法使用信息增益比来选择分枝属性，克服了ID3算法使用信息增益时偏向于取值较多的属性的不足12. Which one is better? B1 or B2? Why? How do you define better? Find hyperplane maximizes the margin = B1 is better than B213.14. 4种核函数 Simple linear kernel: K(Xi, Xj) = Xi *Xj15. 2种多类Multiclass16. 惰性学习与积极学习的概念与区别Lazy vs. eager learning (惰性学
9、习 vs. 积极学习)Lazy learning : Simply stores training data (or only minor processing) and waits until it is given a test tupleEager learning: Given a set of training tuples, constructs a classification model before receiving new data to classifyLazy: less time in training but more time in predictingAccu
10、racyLazy: effectively uses a richer hypothesis space since it uses many local linear functions to form an implicit global approximation to the target functionEager: must commit to a single hypothesis that covers the entire instance space17. k-NN是 惰性、分类、基于instance 的学习方法18. Top 10 Data Mining Algorith
11、m 1. C4.5 6. PageRank (网页排名)2. k-means 7. AdaBoost3. SVM (Support Vector Machines) 8. kNN 4. Apriori 9. Naive Bayes 5. EM (Expectation Maximization) 10. CART19. kNN Classification: Advantages1）Simple technique that is easy to be implemented2）Building model is inexpensive 3）Extremely flexible classif
12、ication scheme does not involve preprocessing 4）Well suited for Multi-modal classes (classes of multiple forms) Records with multiple class labels5）Can sometimes be the best method Michihiro Kuramochi and George Karypis, Gene Classification using Expression Profiles: A Feasibility Study, Internation
13、al Journal on Artificial Intelligence Tools. Vol. 14, No. 4, pp. 641-660, 2005K nearest neighbor outperformed SVM for protein function prediction (蛋白质功能预测) using expression profiles kNN Classification: Disadvantages1） Classifying unknown records are relatively expensiveRequires distance computation
14、of k-nearest neighborsComputationally intensive, especially when the size of the training set grows2） Accuracy can be severely degraded by the presence of noisy or irrelevant features3） NN classification expects class conditional probability to be locally constant bias of high dimensions20. 贝叶斯概念，组成
15、贝叶斯网络：描述随机变量（事件）之间依赖关系的一种图形模式是一种用来进行推理的模型网络结构和条件概率表两部分组成（网络结构是一个有向无环图 结点和有向弧）Bayesian belief network (also known as Bayesian network, probabilistic network): allows class conditional independencies between subsets of variablesTwo components: (1) A directed acyclic graph 有向无环图 (called a structure) (2
16、) a set of conditional probability tables (CPTs)21. 贝叶斯决策概念与过程利用贝叶斯定理求得后验概率，据以进行决策的方法，称为贝叶斯决策方法。已具备先验概率的情况下，贝叶斯决策过程的步骤为：（1）进行预后验分析，取得条件概率，包括历史概率和逻辑概率，对历史概率要加以检验，辨明其是否适合计算后验概率。（2）用概率的乘法定理计算联合概率，用概率的加法定理计算边际概率,用贝叶斯定理计算后验概率（3）用后验概率进行决策分析。第一阶段 准备工作阶段，这个阶段的任务是为朴素贝叶斯分类做必要的准备。第二阶段 分类器训练阶段。第三阶段 应用阶段。这个阶段的任务
17、是使用分类器对待分类项进行分类，其输入是分类器和待分类项，输出是待分类项与类别的映射关系。22. 贝叶斯3概率3公式先验概率：根据历史的资料或主观判断所确定的各种时间发生的概率后验概率：通过贝叶斯公式，结合调查等方式获取了新的附加信息，对先验概率修正后得到的更符合 实际的概率条件概率：某事件发生后该事件的发生概率条件概率公式： A1和 B表示在一个样本空间中的两个事件，给定B 条件下A1发生的条件概率公式 为： 全概率公式 ：B1，B2,， Bn为样本空间中的一组事件，对于每一次试验，B1，B2,，Bn中只有 一个事件发生：贝叶斯公式：独立互斥且完备的后验事件概率可以由先验事件的概率和相应条件
18、概率决定23. 贝叶斯网络的3个主要议题贝叶斯网络预测：从起因推测一个结果的推理贝叶斯网络诊断：从结果推测一个起因的推理贝叶斯网络学习：由先验的Bayes网络得到后验的Bayes网络的过程24. 神经网络概念与结构Artificial neural network (ANN) is a machine learning approach that models human brain and consists of a number of artificial neurons.An artificial neural network (ANN) consists of a pool of si
19、mple processing units which communicate by sending signals to each other over a large number of weighted connections. 25. 人工神经网络的发展与类型人工神经网络的发展：启蒙阶段：感知器模型 低潮时期：线性不可分问题 复兴时期：Hopfield模型神经网络的类型：前向型 反馈型 随机型 自组织竞争型26. 神经网络作为分类器的优缺点Strength1）High tolerance to noisy data 2）Ability to classify untrained pat
20、terns 3）Well-suited for continuous-valued inputs and outputs4）Successful on an array of real-world data, e.g., hand-written letters5）Algorithms are inherently parallel6）Techniques have recently been developed for the extraction of rules from trained neural networksWeakness1）Long training time 2）High
21、 complexity of the network structure: require a number of parameters typically best determined empirically, e.g., the network topology or “structure.”3）Poor interpretability: Difficult to interpret the symbolic meaning behind the learned weights and of “hidden units” in the network27. 人工神经网络特点1）初步的自
22、适应与自组织能力 在学习或训练过程中改变突触权重值，以适应周围环境的要求2）泛化能力 泛化能力指对没有训练过的样本，有很好的预测能力和控制能力3）非线性映射能力 系统很复杂，或者系统未知，系统信息量很少时，建立精确的数学模型很困难时，神经网络的非线 性映射能力则表现出优势4）高度并行性 从功能的模拟角度上看，神经网络也应具备很强的并行性 28. Comparison of Brains and Traditional ComputersBrains 200 billion neurons, 32 trillion synapsesElement size: 10-6 mEnergy use:
23、25WProcessing speed: 100 HzParallel, Distributed (并行，分布)Fault TolerantLearns: YesIntelligent/Conscious: UsuallyTraditional Computers1 billion bytes RAM but trillions of bytes on diskElement size: 10-9 mEnergy watt: 30-90W (CPU)Processing speed: 109 HzSerial, Centralized (串行，集中)Generally not Fault To
24、lerantLearns: SomeIntelligent/Conscious: Generally No29. 单、多层解决的问题 Single Layer Feed-forward NNLinear NNOr, AndMulti-Layer Feed-forward NNNonlinear NNXORBack Propagation (BP)30. 遗传算法相关概念基因 基因（Gene）是遗传的基本单位，是个体的基本组成单元。个体 在生物学中，个体（Individual）由多个基因组成。遗传算法中，个体代表待优化问题的一个解。编码 将问题的解转换成基因序列的过程称为编码(Encoding)
25、，编码是由解空间到遗传算法空间的映射。解码 将基因型转换成问题的解的过程称为解码（Decoding)。种群 生物的遗传进化不能仅通过自身进行，而需要在一个群体中进行，这一群体称为种群 (Population)。种群中的单个组成元素是个体。种群规模是遗传算法的参数之一，种群规模的设置可能会影响到遗传算法的优化效果。适应度 在研究自然界中生物的遗传与进化现象时，生物学中使用适应度(Fitness)这个术语来衡量某 个物种对于生存环境的适应程度。代 在生物的繁衍过程中，个体从出生到死亡即为一代(Generation)，在遗传算法中，代的意思为遗传算法的迭代次数。可作为遗传算法的一个结束标志。遗传算子
26、 指作用在个体上的各种遗传操作。类型：选择算子、交叉算子和变异算子。选择(Selection)算子：在适应度的基础上，按照某种规则或方法从当前代的种群中选择出一 些适应度高的个体遗传到下一代种群中。交叉(Crossover)算子：以某一概率（交叉概率）选择种群中的个体，把两个父个体的部分基因加以替换、重组而生成新的个体。变异(Mutation)算子：以某一概率（变异概率）选择种群中的个体，改变其个体中某些基因的值或对其个体进行某种方式的重组。31. 遗传算法过程32. 适应度函数：体现了个体的生存环境，是通过对目标函数的转换而形成的。设计适应度函数一般主要满足的条件： 连续、非负 适应度函数设
27、计应尽可能简单 适应度函数对某一类具体问题，应尽可能通用33. One-point crossover Two-point crossover 34. 粗糙集1) 等价关系 设R为定义在集合A上的一个关系，若R是自反的，对称的和传递的，则称R为等价 关系。 2) 等价类 设R为集合A上的等价关系，对任何aA，集合aR=x|xA,aRx称为元素a形成的R等 价类。由等价类的定义可知aR是非空的，因为aaR3）知识 一种将现实或抽象的对象进行分类的能力4）知识库 当给定了一个数据上的等价关系集合，在等价关系集合下对该数据集合进行的划分，则 就会被称为知识库5）族集 论域U上的一族划分称为关于U的一
28、个知识库 一个知识库就是一个关系系统K=(U,R)，其中U是非空有限集，R为U上等价关系的一个族集6）不可辨识关系 若PR，且P，则P中所有等价关系的交集也是一个等价关系，称为P上的 不可辨识关系，记为ind(P)7）U/ind(P) 表示与等价关系P相关的知识，称为K中关于U的P 基本知识(基本集)，简称U/P。 （即等价关系ind(P)的所有等价类）8）下近似集 一个知识库K=(U,R)，令XU且R为U上一等价关系，X的下近似集就是对于知识R 能完全确定地归入集合X的对象的集合，记作R_(X) = x|xU,xRX9）上近似集知识R的在U中一定和可能归入集合X的对象的集合，记作R-(X)
29、= x|xU,xRX 10）正域（下近似） 是指知识R和知识U中所有包含在X的对象的集合，记作POSR(X) = R_(X)11）负域 是指知识U和知识U中肯定能包含在U-X中元素的集合，记作NEGR(X) = U-R-(X)12）边界 指的是知识R和知识U中既不能归入X，也不能肯定归入U-X的元素的集合， 记作BNR(X) = R-(X)-R_(X)13）由等价关系R描述的对象集X的近似精度为：（1） 如果dR(X)=0，则X是R全部不可定义的；（2）如果dR(X)=1，则X是R全部可定义的；（3）如果0dR(X)1，则X是R部分可定义的。 分别为X上近似集合、下近似集合中元素的个数。 X的
30、粗糙度PR(X)=1-dR(X)反映了定义集合X的粗糙程度，也即不被关系R所描述的程度。 14）对于知识库K = (U,R)，如果存在等价关系rR,使得ind(r)=ind(R)，则称r是可省略的，否则，称r是不可省略的。 （1）若任意rR是不可省略的，则称R是独立的 （2）独立等价关系的子集也是独立的 15）对于知识库K = (U, R)，R = (P, S)，将S的P正域定义为 16）如果存在r，使得 成立，则称r为P中相对于S是可省略的，否则称r为P中相对 于S是不可省略的 17）若Q=P-r, POSQ(S)=POSP(S), 且Q为最小集，则称Q为P相对于S的简化，记作redS(P)
31、。18）P相对于S的核是P相对于S的所有简化的交集 35. 聚类Attach the same label to data points that are “close” to each other in given set与分类的区别36. 如何度量聚类好坏A good clustering method will produce high quality clustershigh intra-class similarity: compactness within clusterslow inter-class similarity: separation between clusters
32、The quality of a clustering method depends onthe similarity measure usedits implementation, andIts ability to discover some or all of the hidden patterns37. 相似度，不相似度度量 3个距离计算点(i,j)和(h,k)间距离常采用的几种方法： （1）欧氏距离，用 来表示。 L2 norm distance （2）街区距离，也称为4-邻域距离。 L1 norm distance（3）棋盘距离，也称为8-邻域距离。 L norm distance
33、 这三种距离之间的关系： ，如图所示。 38. 距离定义、性质Distances, such as the Euclidean distance, have some well known properties.1）d(p, q) 0 for all p and q and d(p, q) = 0 only if p = q. (Positive definiteness)2）d(p, q) = d(q, p) for all p and q. (Symmetry)3）d(p, r) d(p, q) + d(q, r) for all points p, q, and r. (Triangle
34、 Inequality)where d(p, q) is the distance (dissimilarity) between points (data objects), p and q.A distance that satisfies these properties is a metric, and a space is called a metric spaceSimilarities, also have some well known properties.1）s(p, q) = 1 (or maximum similarity) only if p = q. 2）s(p,
35、q) = s(q, p) for all p and q. (Symmetry)where s(p, q) is the similarity between points (data objects), p and q.39. 层次聚类凝聚型层次聚类：自底向上（初始时每个数据样本单独一类，按相似性度量标准合并样本，直到都属于一类或满足终止条件）分解型层次聚类：自顶向下（初始时所有样本归为一类，按相似性度量标准将样本分解为不同类型，直到每个样本单独成类或满足终止条件）相似性度量：1）最小距离 2）最大距离 3）均值距离 4）平均距离书是我们时代的生命别林斯基书籍是巨大的力量列宁书是人类进步的阶梯高尔基书籍是人类知识的总统莎士比亚书籍是人类思想的宝库乌申斯基书籍举世之宝梭罗好的书籍是最贵重的珍宝别林斯基书是唯一不死的东西丘特书籍使人们成为宇宙的主人巴甫连柯书中横卧着整个过去的灵魂卡莱尔人的影响短暂而微弱，书的影响则广泛而深远普希金人离开了书，如同离开空气一样不能生活科洛廖夫书不仅是生活，而且是现在、过去和未来文化生活的源泉 库法耶夫书籍把我们引入最美好的社会，使我们认识各个时代的伟大智者史美尔斯书籍便是这种改造灵魂的工具。人类所需要的，是富有启发性的养料。而阅读，则正是这种养料雨果