数据挖掘课程内容整理

1、1、 数据挖掘：（定义）从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程称为数据挖掘。（功能）概念描述、关联分析、分类与预测、聚类分析、趋势分析、孤立点分析以及偏差分析等。（典型数据挖掘系统组成）数据库，数据仓库或其他信息库；数据库或数据仓库服务器；知识库；数据挖掘引擎；图形用户界面。（步骤）（1）数据清理：消除重复的、不完全的、违反语义约束的数据（2）数据集成：多种数据源可以组合在一起（3）数据选择：从数据库中检索与分析任务相关的数据（4）数据变换：数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作（5）数据挖掘：使用

2、智能方法提取数据模式（6）模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式（7）知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识（前4个是数据预处理步骤）2、 据预处理：（原因）原始业务数据来自多个数据库或数据仓库，它们的结构和规则可能是不同的，这将导致原始数据非常的杂乱、不可用，即使在同一个数据库中，也可能存在重复的和不完整的数据信息，为了使这些数据能够符合数据挖掘的要求，提高效率和得到清晰的结果，必须进行数据的预处理。（内容）a数据清洗：包括填充空缺值，识别孤立点，去掉噪声和无关数据。b数据集成：将多个数据源中的数据结合起来存放在一个一致的数据存储中。需要注意不同数据源的

3、数据匹配问题、数值冲突问题和冗余问题等。c数据变换：将原始数据转换成为适合数据挖掘的形式。包括对数据的汇总、聚集、概化、规范化，还可能需要进行属性的重构。d数据归约：缩小数据的取值范围，使其更适合于数据挖掘算法的需要，并且能够得到和原始数据相同的分析结果。（数据清理基本内容）1尽可能赋予属性名和属性值明确的含义；2统一多数据源的属性值编码；3去除无用的惟一属性或键值(如自动增长的id)；4去除重复属性(在某些分析中，年龄和出生日期可能就是重复的属性，但在某些时候它们可能又是同时需要的)5去除可忽略字段(大部分为空值的属性一般是没有什么价值的，如果不去除可能造成错误的数据挖掘结果)6合理选择关联

4、字段(对于多个关联性较强的属性，重复无益，只需选择其中的部分用于数据挖掘即可，如价格、数据、金额)7去掉数据中的噪音、填充空值、丢失值和处理不一致数据。（处理空缺值方法）忽略该记录；去掉属性；手工填写空缺值；使用默认值；使用属性平均值；使用同类样本平均值；预测最可能的值。（常见分箱方法）统一权重法(又称等深分箱法) ；统一区间法(又称等宽分箱法) ；最小熵法；自定义区间法。（数据平滑处理方法）平均值法、边界值法和中值法。（数据规约定义）保持原来数据的完整性，将数据集变小，并不影响对结果的分析（规约方法）数据立方体聚集；维归约；数据压缩；数值压缩；离散化和概念分层。（规约原因）维归约可以去掉不重

5、要的属性，减少数据立方体的维数，从而减少数据挖掘处理的数据量，提高挖掘效率（数据规范化定义）将数据按比例缩放(如更换大单位)，使之落入一个特定的区域（如0.01.0），称为规范化。（常见方法）(1) 最大最小规范化：(2) 零均值规范化：(3) 小数定标规范化：xx0/103、 数据仓库：（定义）数据仓库是一种新的数据处理体系结构，是面向主题的、集成的、相对稳定的、反映历史变化的数据集合，为企业决策支持系统提供所需的集成信息。（建立目的）一是为了解企业决策分析中的系统响应问题，数据仓库能提供比传统事务数据库更快的大规模决策分析的响应速度。二是解决决策分析对数据的特殊需求问题。决策分析需要全面的

6、、正确的集成数据，这是传统事务数据库不能直接提供的。三是解决决策分析对数据的特殊操作要求。决策分析是面向专业用户而非一般业务员，需要使用专业的分析工具，对分析结果还要以商业智能的方式进行表现，这是事务数据库不能提供的。（方法）自顶向下方法；自底向上方法；二者结合的混合方法（基本步骤）选取待建模的商务处理；选取商务处理的粒变；选取用于每个事实表记录的维；选取事实表中每条记录的变量（特点精）面向主题的，时变的，集成的，非易失的（特点全）（1）面向对象指数据仓库中的数据是按照一定的主体域进行组织的。主题是一个抽象的概念，是指用户使用数据仓库进行决策时所关心的重点方面。（2）集成的指数据仓库中的数据是

7、对原有分散的数据库数据抽取、清理的基础上进行系统加工、汇总和整理得到的，必须消除源数据中的不一致性，以保证数据仓库内的信息是关于整个企业的一致的全局信息。（3）相对稳定的。操作型数据库中的数据通常实时更新，数据根据需要及时发生变化。数据仓库的数据主要供单位决策分析之用，对所涉及的数据操作主要是数据查询和加载，一旦某个数据加载到数据仓库以后，一般情况下将作为数据档案长期保存，几乎不再做修改和删除操作，也就是说针对数据仓库，通常有大量的查询操作及少量定期的加载（或刷新）操作。（4）反映历史变化。操作型数据库（OLTP）主要关心当前某一个时间段内的数据，而数据仓库中的数据通常包含较久远的历史数据，因

8、此总是包括一个时间维，以便可以研究趋势和变化。数据仓库系统通常记录了一个单位从过去某一时点(如开始启用数据仓库系统的时点)到目前的所有时期的信息，通过这些信息，可以对单位的发展历程和未来趋势做出定量分析和预测。（与数据集市的区别）数据仓库收集了关于整个组织的主题信息，因此是企业范围的。对于数据仓库，通常使用星座模式，因为它能对多个相关的主题建模；数据集市是数据仓库的一个部门子集，它针对选定的主题，因此是部门范围的。对于数据集市，流行星型或雪花模式，因为它们都适合对单个主题建模。（数据库不同）数据仓库是面向主题的,集成的,不易更改且随时间变化的数据集合,用来支持管理人员的决策,数据库由一组内部相

9、关的数据和一组管理和存取数据的软件程序组成,是面向操作型的数据库,是组成数据仓库的源数据.它用表组织数据,采用ER数据模型.（数据库相同）它们都为数据挖掘提供了源数据,都是数据的组合。（系统结构）底层是仓库数据服务器，总是关系数据库系统。（2）中间层是OLAP服务器，有ROLAP和MOLAP（3）顶层是前端客户端4、 数据仓库常见数据模型：（1）星形模式：在此模型下，数据仓库包括一个大的包含大批数据并且不含冗余的中心表，一组小的附属表，维表围绕中心事实表显示的射线上。例子：sales数据仓库的星形模式，此模式包含一个中心事实表sales，它包含四个维time, item, branch和loc

10、ation。（2）雪花型模式：它是星形模式的变种，其中某些维表是规范化的，因而把数据进一步分解到附加的表中。例子同上，只不过把其中的某些维给扩展了。（3）事实星座形：复杂的应用可能需要多个事实表共享维表，这种模式可看作星形模式的汇集。例子：有两个事实表sales和shipping，它们可以共享维表time, item和location。（特征）星型模型四周的实体是维度实体，其作用是限制和过滤用户的查询结果，缩小访问范围。每个维表都有自己的属性，维表和事实表通过关键字相关联。雪花模型通过最大限度地减少数据存储量和联合较小的维表来改善查询性能，增加了用户必须处理的表数量和某些查询的复杂性，但同时提

11、高了处理的灵活性，可以回答更多的商业问题，特别适合系统的逐步建设要求。事实星座模型能对多个相关的主题建模。5、 数据仓库设计的三级模型及其基本内容：（1）概念模型设计是在较高的抽象层次上的设计，其主要内容包括：界定系统边界和确定主要的主题域。（2）逻辑模型设计的主要内容包括：分析主题域、确定粒度层次划分、确定数据分割策略、定义关系模式、定义记录系统。（3）物理数据模型设计的主要内容包括：确定数据存储结构、确定数据存放位置、确定存储分配以及确定索引策略等。要考虑的因素有: I/O存取时间、空间利用率和维护代价等6、 OLAP：即联机分析处理，是在OLTP基础上发展起来的、以数据仓库基础上的、面向

12、高层管理人员和专业分析人员、为企业决策支持服务。OLAP的特点有：1.实时性要求不是很高。2.数据量大。3.因为重点在于决策支持，所以查询一般是动态的，也就是说允许用户随机提出查询要求。OLTP即联机事务处理，是以传统数据库为基础、面向操作人员和低层管理人员、对基本数据进行查询和增、删、改等的日常事务处理。OLTP的特点有：a.实时性要求高；b.数据量不是很大。C.交易一般是确定的，是对确定性数据进行存取。d.并发性要求高且严格的要求事务的完整性，安全性。OLTP和OLAP的区别：用户和系统的面向性:OLTP面向顾客，而OLAP面向市场；数据内容：OLTP系统管理当前数据，而OLAP管理历史的

13、数据；数据库设计：OLTP系统采用实体-联系（ER)模型和面向应用的数据库设计，而OLAP系统通常采用星形和雪花模型；视图：OLTP系统主要关注一个企业或部门内部的当前数据，而OLAP 系统主要关注汇总的统一的数据；访问模式：OLTP访问主要有短的原子事务组成，而OLAP系统的访问大部分是只读操作，尽管许多可能是复杂的查询。OLAP操作（上卷）通过沿一个维的概念分层向上攀登，或者通过维归约，对数据立方体进行类聚。下钻：是上卷的逆操作，它由不太详细的数据得到更详细的数据，下钻可以通过沿维的概念分层向下或引入附加的维来实现。切片：对给定方体的一个维进行进行选择，导致一个子立方体。切块：通过对两个或

14、多个维执行选择，定义子立方体。转轴：是一种可视化操作，它转动数据的视角，提供数据的替代表示。7、 聚类：（定义）聚类是将物理或抽象对象的集合分组成为多个类或簇(cluster)的过程，使得在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。（与分类异同）聚类与分类不同，聚类要划分的类是未知的，分类则可按已知规则进行；聚类是一种无指导学习，它不依赖预先定义的类和带类标号的训练实例，属于观察式学习，分类则属于有指导的学习，是示例式学习。（数据挖掘对聚类的典型要求）可伸缩性；处理不同类型属性的能力；发现任意形状的聚类；用于决定输入参数的领域知识最小化；处理“噪声”数据的能力；对于输入记

15、录的顺序不敏感；高维度；基于约束的聚类（常见数据类型）区间标度变量、比例标度型变量、二元变量、标称型、序数型以及混合类型等。（相异度矩阵）是用于存储所有对象两两之间相异度的矩阵，为一个nn维的单模矩阵。其特点是d(i,j)=d(j,i)，d(i,i)=0，d(j,j)=0。如下图所示：8、 聚类分析：（定义）是将物理的或者抽象的数据集合划分为多个类别的过程，聚类之后的每个类别中任意两个数据样本之间具有较高的相似度，不同类别的数据样本之间具有较低的相似度（应用领域）是数据挖掘应用的主要技术之一，它可以作为一个独立的工具来使用，将未知类标号的数据集划分为多个类别之后，观察每个类别中数据样本的特点，

16、并且对某些特定的类别作进一步的分析。此外，聚类分析还可以作为其他数据挖掘技术（例如分类学习、关联规则挖掘等）的预处理工作。聚类分析在科学数据分析、商业、生物学、医疗诊断、文本挖、Web 数据挖掘等领域都有广泛应用。在科学数据分析中，比如对于卫星遥感照片，聚类可以将相似的区域归类，有助于研究人员根据具体情况做进一步分析；在商业领域，聚类可以帮助市场分析人员对客户的基本数据进行分析，发现购买模式不同的客户群，从而协助市场调整销售计划；在生物学方面，聚类可以帮助研究人员按照基因的相似度对动物和植物的种群进行划分，从而获得对种群中固有结构的认识；在医疗诊断中，聚类可以对细胞进行归类，有助于医疗人员发现

17、异常细胞的聚类，从而对病人及时采取措施；在文本挖掘和Web数据挖掘领域中，聚类可以将网站数据按照读者的兴趣度进行划分，有助于网站内容的改进。9、 分类：（定义）指把数据样本映射到一个事先定义的类中的学习过程，即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类（挖掘方法）决策树法、贝叶斯法、人工神经网络法、粗糙集法和遗传算法。（过程）2步：首先在已知训练数据集上，根据属性特征，为每一种类别找到一个合理的描述或模型，即分类规则；然后根据规则对新数据进行分类。（应用领域）是数据挖掘领域中研究和应用最为广泛的技术之一，许多分类算法被包含在统计分析工具的软件包中，作为专门的分类工具来使用

18、。分类问题在商业、银行业、医疗诊断、生物学、文本挖掘、因特网筛选等领域都有广泛应用。例如，在银行业中，分类方法可以辅助工作人员将正常信用卡用户和欺诈信用卡用户进行分类，从而采取有效措施减小银行的损失；在医疗诊断中，分类方法可以帮助医疗人员将正常细胞和癌变细胞进行分类，从而及时制定救治方案，挽救病人的生命；在因特网筛选中，分类方法可以协助网络工作人员将正常邮件和垃圾邮件进行分类，从而制定有效的垃圾邮件过滤机制，防止垃圾邮件干扰人们的正常生活。10、 决策树：（定义）是用样本的属性作为结点，用属性的取值作为分支的树结构。它是利用信息论原理对大量样本的属性进行分析和归纳而产生的。决策树的根结点是所有

19、样本中信息量最大的属性。树的中间结点是以该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。（如何分类）决策树用于对新样本的分类，即通过决策树对新样本属性值的测试，从树的根结点开始，按照样本属性的取值，逐渐沿着决策树向下，直到树的叶结点，该叶结点表示的类别就是新样本的类别。决策树方法是数据挖掘中非常有效的分类方法。11、 连续数值数据根据直观划分离散化的3-4-5规则可以用来将数值数据分割成相对一致，看上去自然的区间。一般，该规则根据最高有效位的取值范围，递归逐层地将给定的数据区域划分成3，4或5个相对等宽的区间。12、 ID3算法：（基本思想）首先找出最有判别力

20、的因素，然后把数据分成多个子集，每个子集又选择最有判别力的因素进一步划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树，可以用它来对新的样例进行分类。（优点）1、理论清晰，算法简单，很有实用价值的示例学习算法。2、计算时间是例子个数、特征属性个数、节点个数之积的线性函数，总预测准确率较令人满意（缺点）（1）ID3算法在选择根结点和各内部结点中的分枝属性时，使用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息（2）ID3算法只能对描述属性为离散型属性的数据集构造决策树（主算法基本步骤）从训练集中随机选择一个既含正例

21、又含反例的子集(称为窗口)；用“建树算法”对当前窗口形成一棵决策树；对训练集(窗口除外)中例子用所得决策树进行类别判定，找出错判的例子；若存在错判的例子，把它们插入窗口，重复步骤，否则结束。（建树基本步骤）对当前例子集合，计算各特征的互信息；选择互信息最大的特征Ak；把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集；对既含正例又含反例的子集，递归调用建树算法；若子集仅含正例或反例，对应分枝标上P或N，返回调用处。13、 C4.5：（优点）产生的分类规则易于理解，准确率较高（缺点）在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。14、 神经元：（基本特征

22、）多输入、单输出；突触兼有兴奋和抑制两种性能；可时间加权和空间加权；可产生脉冲；脉冲可进行传递；非线性，有阈值。（M-P方程并说明其含义）M-P方程：，Wij是神经元之间的连接强度，是阈值，f(x)是阶梯函数。15、 遗传算法与传统寻优算法相比特点：遗传算法为群体搜索，有利于寻找到全局最优解；遗传算法采用高效有方向的随机搜索，搜索效率高；遗传算法处理的对象是个体而不是参变量，具有广泛的应用领域；遗传算法使用适应值信息评估个体，不需要导数或其他辅助信息，运算速度快，适应性好；遗传算法具有隐含并行性，具有更高的运行效率。16、 K-平均算法：（输入）簇的数目k和包含n个对象的数据集（输出）k个簇，

23、使平方误差准则最小（聚类过程）1.任意选择k个对象作为初始的簇中心；2.计算其它对象与这k个中心的距离，然后把每个对象归入离它“最近”的簇；3.计算各簇中对象的平均值，然后重新选择簇中心(离平均值“最近”的对象值)；4.重复第2第3步直到簇中心不再变化为止。优点：算法速度快，计算简单缺点：（1）必须输入聚类个数k（2）只有当簇均值有定义的情况下，这个方法才能使用（3）不能处理噪声和孤立点数据（4）不适合发现大小差别很大的簇17、 K-中心点算法：（输入）结果簇的数目k，包含n个对象的数据集。（输出）k个簇，使得所有对象与其最近中心点的相异度总和最小。（聚类过程）（1）随机选择k个对象作为初始中

24、心点；（2）计算其它对象与这k个中心的距离，然后把每个对象归入离它“最近”的簇；（3）随机地选择一个非中心点对象Orandom，并计算用Orandom代替Oj的总代价S；（4）如果S0,则用Orandom代替Oj，形成新的k个中心点集合；（5）重复迭代第3、4步，直到中心点不变为止。（改进算法CLARANS思想）为了处理大的数据集，可以采用一种基于抽样的方法CLARA，它的思想：不考虑整个数据集合，而是选择实际数据的一小部分作为数据的代表，抽取数据集合中的多个样本，对每个样本使用PAM算法。它的有效性取决于样本的大小18、 朴素贝叶斯分类：（为什么朴素）朴素贝叶斯分类假定一个属性值对给定类的影

25、响独立于其它属性的值。该假定称作类条件独立。做此假定是为了简化所需计算，并在此意义下称为“朴素的”（主要思想）设为一个类别未知的数据样本，H为某个假设，若数据样本X属于一个特定的类别C，分类问题就是决定P（H|X），即在获得数据样本X时假设成立的概率。（定义）贝叶斯分类法是统计学分类方法，可以预测类成员关系的可能性。朴素贝叶斯分类法假定一个属性值对给定类的影响独立于其他属性值。它表示属性子集间的依赖（优点）（1）理论上，贝叶斯分类具有最小的错误率（2）可以用来为不直接使用贝叶斯定理的其他分类法提供理论判定（3）有着坚实的数学基础，以及稳定的分类效率（4）模型所需估计的参数很少，对缺失数据不太敏

26、感，算法也比较简单（5）网格结构一旦确定下来后，添加新变量容易（5）适合处理不完整的数据（6）对过分拟合问题鲁棒。（缺点）（1）实际上，由于对其使用的假定的不正确性，以及缺乏可用的概率，此分类法并不具有最小的错误率（2）有可能遇到零概率值，需要修正（3）构造网格费时、费力19、 神经网络：（优点）其对噪音数据的高承受能力，以及它对未经过训练的数据的分类能力（缺点）需要很长的训练时间，因而对于有足够长训练时间的应用更合适。20、 聚类算法：（划分方法）给定一个n个对象或元组的数据库，一个划分方法构造数据的k个划分，每个划分表示一个聚类，并且k n。（层次方法）对给定数据对象集合进行层次的分解。（

27、基于密度的方法）只要是临近区域的密度超过某个阀值，就继续聚类。（基于网格的方法）把对象空间量化为有限数目的单元。（基于模型的方法）试图优化给定的数据和某些数学模型之间的适应性。21、 关联规则：（定义）最初由R.Agrawal 等人提出，用来发现超级市场中用户购买的商品之间的隐含关联关系，并用规则的形式表示出来，称为关联规则(Association Rule)（应用）关联规则除了可以发现超市购物中隐含的关联关系之外，还可以应用于其他很多领域。关联规则的应用还包括文本挖掘、商品广告邮寄分析、网络故障分析等。（分类）（1）基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。（2）基于规则

28、中数据的抽象层次，可以分为单层关联规则和多层关联规则。（3）基于规则中处理的变量的类型不同，关联规则可以分为布尔型和数值型。（挖掘步骤）1）找出交易数据库中所有大于或等于用户指定的最小支持度的频繁项集；（2）利用频繁项集生成所需要的关联规则，根据用户设定的最小可信度进行取舍，产生强关联规。（挖掘步骤）（1）找出交易数据库中所有大于或等于用户指定的最小支持度的频繁项集；（2）利用频繁项集生成所需要的关联规则，根据用户设定的最小可信度进行取舍，产生强关联规则。22、 Apriori算法：（基本思想）算法使用频繁项集知识的先验知识。Apriori使用一种逐层搜索的迭代方法，K项集用来搜索K+1项集。

29、首先通过扫描数据库，累积每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记为L1.然后，L1用于找频繁2项集的集合L2，L2用于找L3，如此下去，直到不能在找到频繁K项集（优点）Apriori的候选产生-检验的方法显著压缩了候选项集的大小，并导致很好的性能（缺点）1.它可能需要产生大量的候选项集。2.它可能需要重复的扫描数据库，通过模式匹配检查一个很大的候选项集。23、 支持向量机：（思想）使用一种非线性映射。将原训练集映射到较高的维。在新的维上，它搜索最佳分离超平面（即将一类元组与其他类分离的“决策边界。”）使用一个适合的对足够高维的非线性映射，两类数据总可以被超平面分开

30、。（缺点）训练时间长（优点）1.对复杂的非线性决策边界的建模能力是高度准确的。2.不太容易过分拟合。3.提供了学习模型的紧凑表示。24、 人工神经网络：（分类方法）1.依学习策略（Algorithm）分类主要有：监督式学习网络为主、无监督式学习网络、混合式学习网络、联想式学习网络、最适化学习网络2.依网络架构分类主要有:前向式架构、回馈式架构、强化式架构（优点）包括对噪声数据的高承受能力，以及对未经训练的数据的模式分类能力（缺点）1、需要很长的训练时间，对于有足够长训练时间的应用更为合适。2、需要大量参数，通常主要靠经验确定，如网络拓扑或“结构”。3、常常因其可解释性差而受到批评，例如，人们很

31、难解释网络中学习的权重和“隐藏单元”的符号含义。25、 KNN：（定义）即K最近邻分类法，它是基于类比学习，即通过给定的检验元组与和他相似的训练元组进行比较来学习（优点）1）算法简单直观，易于实现；（2）不需要产生额外的数据来描述规则，并且可以存在噪音；（3）可以较好地避免样本数量的不平衡问题；（4）减少了类别特征选择不当对分类结果造成的不利影响，可以最大程度地减少分类过程中的误差项（5）适合增量学习（缺点）（1）分类速度慢（2）样本库容量依赖性较强（3）必须指定K值，K值选择不当则分类精度不能保证。（4）计算开销大（5）需要有效的存储技术和并行硬件的支撑。26、 EM：（定义）EM(期望最大化)算法是一种流行的迭代求精算法，可以用来求得参数的估计