数据挖掘课程复习提纲

《数据挖掘课程复习提纲》由会员分享，可在线阅读，更多相关《数据挖掘课程复习提纲（41页珍藏版）》请在装配图网上搜索。

1、数据挖掘课程复习提纲（ 12 级计算机、软件、网络）有关考试题型：一、填空题（ 15 分，每空 1 分）二、判断题（ 10 分，每题 1 分）三、计算题（ 55 分，4 大题， 13 大题各 15 分，第 4 大题 10 分）聚类、分类、 关联分析、异常挖掘各一题四、问答题（ 20 分， 3 题，分别是 7 分， 6 分，和 7 分题） 基本要求：掌握数据预处理、 分类、聚类、关联分析、异常挖掘的基本方法、 clementine 的基本使用方法，及每类方法的应用场景（每类方法理解、熟悉一个例子） 。算法重点 掌握 k-means 、一趟聚类、 DBSCAN 、 ID3（C4.5） 、Bayes

2、 、KNN 、 Apriori 及基于 距离、密度、聚类的异常检测方法。第一章 绪论1 数据挖掘的定义 技术层面：数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中， 提取隐含在其中、人们事先不知道的、但又潜在有用的信息和知识的过程。商业层面：数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务 数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。2 数据挖掘的任务预测任务：根据其它属性的值预测特定(目标)属性的值，如回归、分类、异常检测。描述任务：寻找概括数据中潜在联系的模式，如关联分析、演化分析、聚类分析、序列模式挖 掘。(1

3、) 关联 (Association) 分析关联分析，发现特征之间的相互依赖关系，通常是从给定的数据集中发现频繁出现的模式知识 (又称为关联规则 )。关联分析广泛用于市场营销、事务分析等领域。(2) 分类 (Classification) 分析分类分析就是通过分析示例数据库中的数据，为每个类别做出准确的描述或建立分析模型或挖 掘出分类规则，然后用这个分类规则对其它数据库中的记录进行分类。(3) 聚类 (Clustering) 分析“物以类聚，人以群分”。聚类分析技术试图找出数据集中的共性和差异，并将具有共性的对 象聚合在相应的类中。聚类可以帮助决定哪些组合更有意义。聚类与分类的区别? 聚类问题是

4、无指导的：没有预先定义的类。? 分类问题是有指导的：预先定义有类。(4) 演化 (Evolving) 分析演化分析就是对随时间变化的数据对象的变化规律和趋势进行建模描述。 如：商品销售的周期 (季节 )性。(5) 异常 (Outlier) 分析异常分析就是对异常数据的挖掘、分析。比如商业欺诈行为的自动检测，网络入侵检测，金融 欺诈检测，反洗钱，犯罪嫌疑人的调查等。(6) 序列模式 (Sequential Pattern) 挖掘分析数据间的前后序列关系3 数据挖掘的对象包括空间数据库、时间序列数据库、流数据、多媒体数据库、文本数据和万维网4.知识发现的主要步骤：(1) 数据清洗 (data cl

5、earing) 。其作用是清除数据噪声和与挖掘主题明显无关的数据。(2) 数据集成 (data integration) 。其作用是将来自多数据源中的相关数据组合到一起。(3) 数据转换 (data transformation) 。其作用是将数据转换为易于进行数据挖掘的数据存储形式。(4) 数据挖掘 (data mining) 。其作用是利用智能方法挖掘数据模式或规律知识。(5) 模式评估 (pattern evaluation) 。其作用是根据一定评估标准从挖掘结果筛选出有意义的相关知 识。(6) 知识表示 (knowledge presentation) 。其作用是利用可视化和知识表达技

6、术，向用户展示所挖 掘的相关知识。数据挖掘只是知识发现过程的一个步骤。5 数据挖掘产生背景及应用领域产生背景：“数据过剩” 、“信息爆炸”与“知识贫乏” 使得人们淹没在数据中， 难以制定合适 的决策 !应用领域：在许多行业都有广泛应用，有大量数据的领域就有应用。(1) 数据挖掘在商业领域中的应用市场分析和管理，公司分析和风险管理，欺诈行为检测和异常模式的发现，自动趋势预测，(2) 数据挖掘在计算机领域中的应用信息安全：入侵检测，垃圾邮件的过滤，互联网信息/使用挖掘，智能回答系统(3) 其它领域中的应用数据挖掘在工业制造方面的应用，生物信息或基因的数据挖掘，体育竞赛，天文学，军事情报分析(反恐)

7、，电视观众预测，多媒体、空间数据分析，6 数据挖掘使用的软件SPSS Clementine 、 SAS Enterprise Miner、 IBM Intelligent Miner 、 SQL Server 2005Oracle DM 等商用软件能够提供常规的挖掘过程和挖掘模式。Matlab ， Excel(Data mining in Excel: XLMiner) 等提供了数据挖掘模块。Weka ， RapidMiner(YALE) ， ARMiner 等为开源数据挖掘工具。7 数据挖掘领域 10 大挑战性问题：(1) 数据挖掘理论的构建(2) 高维、数据流数据挖掘 (高效、可扩展 )(

8、3) (时间 )序列数据挖掘(4) 从复杂数据中挖掘复杂知识(5) 网络环境下的数据挖掘技术(6) 分布式、多代理的数据挖掘(7) 生物及环境问题数据挖掘(8) 相关问题的数据挖掘处理(9) 安全、隐私及数据整合(10) 非静态、不平衡及代价敏感的数据挖掘第二章数据预处理1 数据挖掘中使用的数据(1) 数据挖掘中使用的数据是数据对象及其属性的集合。其中：属性是指对象的性质或特性，对象也称为数据对象、点、样本、观测或是实体等。数据集是数据对象的集合(同分布、同特征 )。(2) 不同的属性类型：分为分类属性和数值属性，分类属性又分标称型和序数型，而数值属性又分 区间型和比率型。如性别为标称型，好坏

9、等级为序数型，日期时间为区间型，分数为比率型。因此， 根据属性具有的不同性质，属性可分为四种：标称、序数、区间、比例 。(3) 数据集的类别：记录数据、基于图形的数据、有序的数据、序列数据。(4) 数据集的特性 :：维度 (Dimensionality) ，稀疏性 (Sparsity) ，分辨率 (Resolution) 。2 数据的质量问题现实世界中的原始数据往往存在一定的质量问题，如：噪声、离群点、缺失值、重复数据等， 需要对其进行“清洗”才能更高效地进行挖掘。中位数的定义： 设给定的 N 个不同值的数据集按数值升序排序， 如果 N 是奇数， 则中位数是有 序集的中间值，否则中位数是中间两

10、个值的平均值。众数的定义：数据集中出现次数最多的值。3 数据预处理(1) 为什么要预处理数据现实世界的数据是“不干净的”? 不完整的：有感兴趣的属性缺少属性值? 含噪声的：包含错误或“孤立点”? 不一致的：在命名或编码上存在差异没有高质量的数据，就没有高质量的挖掘效果? 高质量的决策必须依赖高质量的数据? 数据仓库需要对高质量的数据进行一致性地集成意义? 使挖掘过程更有效、更容易? 目的：提供干净、简洁、准确的数据，提高挖掘效率和准确性（2） 数据预处理工作一般包括 ：数据清理、数据集成、数据变换、数据归约、离散化及特征选择等。数据清理包括填写空缺数据，平滑噪声数据，识别、删除孤立点，数据集成

11、，抽样等。数据集成是集成多个数据库，数据立方体或文件。数据变换是对原始数据进行规范化和特征构造。数据归约是对数据集进行压缩表示及特征选择。数据离散化是通过概念分层和数据离散化来归约数据。（3） 抽样： 用数据较小的随机样本表示大的数据集抽样是一种选择数据对象子集进行分析的常用方法数据挖掘使用抽样是因处理所有数据的费用太高、太费时间有效抽样原理：如果样本是有代表性的，则使用样本与使用整个数据集的效果几乎一样抽样方法：简单随机抽样：无放回抽样，有放回的抽样分层抽样? 特点：总体由不同类别的对象组成，每种类型的对象数量差别很大? 先对数据集进行分组：数据集 D 被划分为互不一相交的“层”，则可通过对

12、每一层按一 定比例简单随机选样得到 D 的分层选样? 利用聚类实现分层抽样：将数据集 D 划分成 m 个不相交的簇，再在聚类结果的簇上进 行简单随机抽样抽样方法可以压缩数据量。如果数据的类别不均衡，通常采用的抽样方法是分层抽样。（4）噪声的处理方法包括：分箱（将数据落入箱中来平滑数据） 、聚类（通过聚类监测并且去除孤立点） 、计算机与人工结合（计算机检测可疑数据然后对可疑数据进行人工判断） 、回归（通过让数据适应回归函数来平滑数据）。? 规范化通过将属性数据按比例缩放，通过一个函数将给定属性的整个值域映射到一个新的值域中，即每个旧的值都被一个新的值替代。有3种规范化策略。规范化方法一最小最大

13、（min-max）规范化通过线性变换 Zf 勺 巴叫 将值转换到区间0,1，这里min f ,maxf分别为f的n个观测值的 maxf mi nf最小值和最大值。最小-最大规范化保持原有数据之间的联系。如果今后的输入落在A的原始数据值域之外，该方法将面临“越界错误”。规范化方法二z-score规范化Xi exZf 二L，其中f为属性标准差，EXf为属性平均值。f当属性f的实际最大和最小值未知，或异常点左右了最小一最大规范化时，该方法是有用的。规范化方法三一一小数定标规范化小数定标规范化通过移动属性 A的小数点位置进行规范化。A的值v被规范化为v，由下式,v计算：v 1Q7，其中，j是使Max（

14、|v|） 1的最小整数。（5）数据归约策略数据归约：数据归约用来得到数据集的简约表示，它小得多，但可以产生相同的（或几乎相同的）分析结果数据归约策略? 数据立方体聚集? 维归约：通过删除不相干的属性或维减少数据量? 数据压缩：用数据编码或者变换得到原始数据的压缩表示。典型的有小波变换和主成分 分析? 数值归约? 离散化和概念分层归约标准? 用于数据归约的时间不应当超过或“抵消”在归约后的数据上挖掘节省的时间? 归约得到的数据比原数据小得多，但可产生相同或几乎相同的分析结果(6) 特征提取 (Feature Extraction)： 由原始数据创建新的特征集映射数据到新的空间? 从不同视角提示重

15、要和有趣的特征? 傅里叶变换 (Fourier Transform)? 小波变换 (Wavelet Transform)特征构造? 由一个或多个原始特征共同构造新的特征(7) 特征选择从一组已知特征集合中选择最具代表性的特征子集，使其保留原有数据的大部分信息，即所选 特征子集可以像原来的特征全集一样用来正确区分数据集的每个数据对象。通过特征选择，一些和 任务无关或是冗余的特征被删除，从而提高数据处理的效率。特征选择可以用于解决维数灾难的问 题。? 特征选择目的：去除不相关和冗余的特征，降低时间空间复杂度，提高数据质量及数据泛化能力。? 理想的特征子集：每个有价值的非目标特征与目标特征强相关，而

16、非目标特征之间不相 关或是弱相关? 基本步骤：去掉与目标特征不相关的特征,删除冗余特征(8) 离散化与概念分层离散化：通过将属性域划分为区间，减少给定连续属性值的个数。包括等宽离散化，等频离散 化等方法。概念分层：通过使用高层的概念(比如：老年，中年，青年)来替代底层的属性值(比如：实 际的年龄数据值)来规约数据，概念分层可以用树来表示，树的每一个节点代表一个概念(比如： 按地区划分世界) 。4 距离与相似性属性之间的相似性度量(1) Cosine 相似度定义两个向量的夹角余弦为相似度，即： 对文档进行聚类时通常采用余弦相似度计算相似性。(2) 相关系数 (Correlation coeffi

17、cient) 相关系数是标准化后的对象之间的夹角余弦，它表示两个向量的线性相关程度。具有平移不变 性。(3) Pearson 相关系数对象之间的相似性度量常用距离函数 :(1) 间隔数值属性设m为样本空间的维数，对于任意样本对象p Pi,P2, , Pm与q qi,q2, , qm。m 2欧式(Euclidean)距离：d2(p,q) J | p q |im曼哈顿(Manhattan )距离：d1 (p,q)| pi qi 1值属性变量(binary variable)只有两种状态:0或1,表示属性的存在与否。一种差异计算方法就Can berra 距离：dcanb(P，q)J p| q |i

18、11 pi | |qi |(2)二值属性是根据二值数据计算。假设二值属性对象p和q的取值情况如表2-1所示。其中m表示对象p和q中均 取1的二值属性个数，no表示对象p取1而对象q取0的二值属性个数，n1表示对象p取0而对象q取1 的二值属性个数，n00表示对象p和q均取0的二值属性个数。表2-1二值属性对象p和q的取值情况10合计1nnn10n-niTi00n01n00n00合计nnn1n10n0对象q对象pJaccard系数定义如下:第三章 分类1分类的定义分类是对数据集进行学习并构造一个拥有预测功能的分类模型，用于预测未知样本的类标号，如：根据电子邮件的标题和内容预测该邮件是否为垃圾邮件

19、。分类和回归都有预测的功能，但是：分类预测的输出为离散或标称的属性；回归预测的输出为连续属性值，例如：预测未来某银行客户会流失或不流失，这是分类任务，预测某商场未来一年的总营业额，这是回归任务。2 分类的应用领域目前分类与回归方法已被广泛应用于各行各业，如：在金融领域中，分类器被用于预测股票未来的 走向。在医疗诊断中，使用分类模型预测放射学实验室医疗癌症的诊断、精神病的诊断、医疗影像 的诊断等。在市场营销中，利用历史的销售数据，预测某些商品是否可以销售、预测广告应该投放 到哪个区域、预测某客户是否会成为商场客户从而实施定点传单投放等。3 分类的步骤(1) 将数据集划分为训练集和测试集；(2)

20、对训练集进行学习，构建分类模型； (这个模型可以是决策树或分类规则等形式)(3) 用建好的分类模型对测试集进行分类；(4) 评估该分类模型的分类准确度及其它性能；(5) 使用分类准确度高的分类模型对类标号未知的未来样本数据进行分类。4 分类算法归类分类方法大体上有以下几类：基于决策树的分类方法、贝叶斯分类方法、最近邻分类方法、神 经网络方法、粗糙集、支持向量机等。回归则包括线性回归、非线性回归、逻辑回归等。5 决策树分类算法决策树分类方法的特点是对训练样本集进行训练，生成一棵形如二叉或多叉的决策树。决策树中每个非叶节点表示样本的一个属性，每个分支表示非叶结点属性取不同值下的样本子 集，每个叶结

21、点存放一个类标号值。决策树算法的关键环节是如何选择测试属性和划分样本集，目 前主要决策树学习算法包括 ID3 、 C4.5 、 CART 、SLIQ 、 SPRINT 、PUBLIC 等。5.1 ID3 决策树分类算法介绍ID3 分类算法由 Quinlan 于 1986 年提出，使用信息增益 (information gain) 作为属性的选择 标准。其基本思想如下：首先检测所有属性，选择信息增益最大的属性产生决策树结点，由该属性 的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅 包含同一个类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。

22、ID3 分类算法的伪代码如下：函数： DT(S,F)输入：训练集数据 S，训练集数据属性集合 F输出： ID3 决策树(1) if 样本 S 全部属于同一个类别 C then(2) 创建一个叶结点，并标记类标号为 C；(3) return ；(4) else(5) 计算属性集 F 中每一个属性的信息增益，假定增益值最大的属性为 A(6) 创建结点，取属性 A 为该结点的决策属性；(7) for 结点属性 A 的每个可能的取值 V do(8) 为该结点添加一个新的分支，假设 SV 为属性 A 取值为 V 的样本子集(9) if 样本 SV 全部属于同一个类别 C then(10) 为该分支添加一

23、个叶结点，并标记类标号为 C；(11) else(12) 递归调用 DT(SV, F-A) ，为该分支创建子树；(13) end if(11) end for(12) end ifID3 算法使用信息增益来获取最好的属性作为决策结点， 以使得训练记录被划分为较纯的子集。 信息增益是度量一个给定属性划分训练集到目标类的好坏程度。信息增益值最高的属性被选择作为 决策结点。ID3 建决策树例子见书本。熵 (entropy) 的定义： 熵用来度量一个属性信息的数量。假设训练集S的类标号属性 C具有m个可能的值，即 C=C1,C2,Cm，并且Ci在所有样本 中出现的频率为 Pi (i=1,2,3,m)，

24、则该训练集S所包含的信息熵 Entropy(S)为：如果所有记录都属于同一个类，则训练集 S 的熵值为 0，表示很纯。例如假定数据集S中有14个样本，目标属性 Play Ball有2个值：Play Ball=Yes, No。14 个样本的分布为： 9 个样本的类标号取值为 YES， 5 个样本的类标号取值为 NO ，因此： C1=Yes 在所有样本S中出现的概率为：9/14 , C2=NO 在所有样本S中出现的概率为：5/14，因此数据集 S 的熵为：信息增益的定义：ID3 中信息增益 (information gain )的定义是： 划分前样本的不纯程度 (熵)和划分后样本的不 纯程度(熵)

25、的差值。假设划分前样本数据集为S,现在假定用属性 A来划分样本S,则按属性A划分S的信息增益Gain(S,A)为：样本S的熵减去按属性 A划分S后的样本子集的熵。其中：按属性 A 划分 S 后的样本子集的熵定义如下：假定属性A有k个不同的取值，从而将 S划分为k个样本子集S1,S2,Sk，则按属性A划分 S 后的样本子集的信息熵为 :其中|Si|(i,=1,2，k)为划分后各样本子集中样本的个数，|S|是S中样本的个数。ID3 算法总结：ID3 算法是所有可能的决策树空间中一种自顶向下、贪婪的搜索方法。ID3 搜索的假设空间是可能的决策树的集合，搜索目的是构造与训练数据一致的一棵决策树， 搜索

26、策略是爬山法，在构造决策树时从简单到复杂，用信息熵作为爬山法的评价函数。ID3 算法的核心是在决策树各级结点上选择属性，用信息增益作为属性选择的标准，使得在每 个非叶节点进行测试时能获得关于被测数据最大的类别信息，使得该属性将数据集分成子集后，系 统的熵值最小。5.2 C基于 ID3 算法中存在的不足， Quinlan 于 1993 年对其做出改进，提出了改进的决策树分类算法 C4.5 ，该算法继承了 ID3 算法的优点，并在以下几个方面对 ID3 算法进行了改进：(1) 能够处理连续型属性数据和离散型属性数据；(2) 能够处理具有缺失值的数据；(3) 使用信息增益率作为决策树的属性选择标准；

27、(4) 对生成的树进行剪枝处理，以获取简略的决策树；(5) 从决策树到规则的自动产生。C4.5 算法的基本描述：1) 对数据集进行预处理，将连续型属性数据离散化；2) 计算每个属性的信息增益和信息增益率；3) 根结点属性每一个可能的取值对应一个子集，对样本子集递归地执行(2)过程，直到划分的每个子集中的观测数据都属于同一个类标号，生成决策树。4) 根据构造的决策树提取分类规则，对新的数据集进行分类。C4.5 算法的概念描述：假定S为训练集，目标属性 C具有m个可能的取值，C=C1,C2,Cm,即训练集S的目标属 性具有m个类标号值C1,C2,Cm , C4.5算法所涉及的概念描述如下：(1)

28、假定训练集S中，Ci在所有样本中出现的频率为pi(i=1,2,3，,m)，则该集合S所包含的信息熵为：设用属性A来划分S中的样本，计算属性A对集合S的划分熵值Entropy a(S)定义如下：若属性A为离散型数据，并具有k个不同的取值，则属性A依据这k个不同取值将S划分为kIS I|S|个子集S1,S2,Sk，属性靠划分斶的信息熵为：ggi 1丨S丨其中|Si|和|S|分别是Si和S中包含的样本个数。如果属性A为连续型数据，则按属性A的取值递增排序，将每对相邻值的中点看作可能的分裂点，对每个可能的分裂点，计算：其中SL和SR分别对应于该分裂点划分的左右两部分子集，选择Entropy a(S)值

29、最小的分裂点作为属性A的最佳分裂点，并以该最佳分裂点按属性A对集合S的划分熵值作为属性 A划分S的熵值。(3) C4.5以信息增益率作为选择标准，不仅考虑信息增益的大小程度，还兼顾为获得信息增益 所付出的“代价” ：C4.5通过引入属性的分裂信息来调节信息增益，分裂信息定义为：信息增益率定义为：这样如果某个属性有较多的分类取值，则它的信息熵会偏大，但信息增益率由于考虑了分裂信m息而降低，进而消除了属性取值数目所Op来(S影响。pi log2 pii 1C4.5算法例子见书本。C4.5算法对数值型属性数据的处理：C4.5可以处理数值型属性数据的分类，它的处理思想是，针对数值型属性，先对其进行递增

30、排 序，将没对相邻值的中点看做可能的分裂点，对每个可能的分裂点，计算分裂熵值，选取分裂熵值 最小的分裂点作为该数值属性的最佳分裂点。具体例子请参考书本。5.3 决策树分类算法的优缺点：总的来讲，基于决策树的分类算法的具有以下优点：(1) 构造的代价低；(2) 在分类未知记录时非常快；(3) 对于一些比较小的树非常容易解释；(4) 在许多简单数据集上测试发现，决策树分类技术其准确率和其它分类技术相当。6 贝叶斯分类算法贝叶斯分类方法是一种利用概率统计知识进行学习分类的方法， 属于基于统计的学习方法， 即： 预测一个数据对象属于某个类别的概率。 例 如：计算邮件是垃圾邮件或合法邮件的概率，取概率大

31、 的为预测结果。主要算法有：朴素贝叶斯分类算法，贝叶斯信念网络分类算法等。 朴素贝叶斯分类算法和贝叶斯信念网络分类算法都是建立在贝叶斯定理基础上的算法6.1 贝叶斯定理假设 X,Y 是一对随机变量， 它们的： 联合概率 P( X=x,Y=y )是指 X 取值 x 且 Y 取值 y 的概率， 条件概率是指一随机变量在另一随机变量取值已知的情况下取某一个特定值的概率。例如 P(Y=y|X=x )是指在变量 X 取值 x 的情况下，变量 Y 取值 y 的概率。贝叶斯定理是指 X 和 Y 的联合概率和条件概率满足如下关系：6.2 朴素贝叶斯算法朴素贝叶斯 ( na?ve bayes) 分类算法利用贝叶

32、斯定理来预测一个未知类别的样本属于各个类别的 可能性，选择其中可能性最大的一个类别作为该样本的最终类别。设数据集为D，对应属性集：A1,A2,An, CA1,A2,An是样本的属性变量，C是有m个取值C1,C2,.,Cm的类标号属性变量。数据集D中的每个样本 X可以表示为X=x1,x2，,xn,Ci朴素贝叶斯分类算法的概念描述如下： 假定朴素贝叶斯分类器将未知样本X分配给类Ci，则:根据贝叶斯定理有：P(Ci|X)号刖 由于P(X)对所有类为常数，最大化后验概率P(Ci|X)可转化为最大化先验概率P(X|Ci)P(Ci)。类的先验概率P(Ci)可以用si/s来估计，其中si是数据集D中属于类C

33、i的样本个数，s是数据集D 的样本总数 朴素贝叶斯假定一个属性值对给定类的影响独立于其他属性值，属性之间不存在依赖关系，这样：从数据集中求概率 P(Xi|Ci) P(X2 |Ci)P(Xn|Ci)这里xk表示样本X在属性Ak下的取值。对于每个属性，考察该属性是分类的还是连续的。? 如果属性Ak是分类属性，则：P(xk|Ci)=sik/si ，其中sik是D中属性Ak的值为xk的Ci 类的样本个数，si是D中属于Ci类的样本个数。? 如果属性Ak是连续值属性，则通常假定该连续值属性服从高斯分布，因而： 为对未知样本 X分类，对每个类Ci，计算P(X|Ci)，样本X被指派到类别 Ci中，当且仅当：

34、P(X|G)P(G) P(X |Cj)P(Cj)1 j m, j i 这样X被指派到最大的类别中。朴素贝叶斯分类算法的优缺点：朴素贝叶斯分类算法的优点在于：容易实现，在大多数情况下所获得的结果比较好。缺点：算法成立的前提是假设各属性之间互相独立，当数据集满足这种独立性假设时，分类准确度较高。而实际领域中，数据集可能并不完全满足独立性假设。7 K 最近邻分类算法K- 最近邻分类算法是一种基于实例的学习算法，它不需要先使用训练样本进行分类器的设计， 而是直接用训练集对数据样本进行分类，确定其类别标号。K-最近邻算法的基本思想为：对于未知类标号的样本，按照距离找出它在训练集中的k个最近邻，将未知样本

35、赋予 k 最近邻中出现次数最多的类别号。K- 最近邻分类算法的基本描述如下：令 D 为训练集， Z 为测试集， K 为最近邻数目，其中每个样本可以表示为 (x,y) 的形式，即 (x1,x2,.,xn,y)，其中(x1,x2,xn)表示样本的n个属性，y表示样本的类标号，则 KNN分类算法的 基本描述如下算法名： KNN输入：最近邻数目 K，训练集D，测试集Z输出：对测试集 Z 中所有测试样本预测其类标号值1. for每个测试样本 z=(x,y) D do2. 计算 z 和每个训练样本之间的距离 d3. 选择离 z 最近的 k 最近邻集合 D Z4. 采用投票机制返回 Dz中样本的多数类的类标

36、号5. end forK- 最近邻分类算法的优缺点：优点：算法思想简单，易于实现。缺点： 最近邻分类对每个属性指定相同的权重， 而数据集中不同属性可能需要赋予不同的权值； 由于 K-NN 存放所有的训练样本，直到有新的样本需要分类时才建立分类，因此当训练样本数量很大时，该学习算法的时间复杂度为 n2。K-NN 的扩展：对 K-NN 的改进主要从提高分类的速度和准确度两个方面进行。如先对训练样本中的每一类样本集进行聚类，然后用聚类后形成的子类代替属于该子类的所有 样本集，从而大大减少了训练样本的数量，提高了计算速度。也可以先对未知样本集进行预分类， 划分出训练集和测试集，然后采用 K-NN 分类

37、器进行分类，从而提高分类进度并降低时间复杂度。8 分类模型的评价8.1 分类模型性能评价标准：(1) 分类准确率，即模型正确地预测新的或先前未见过的数据的类标号的能力。一个分类模型 在测试集上的准确率越高说明这个模型越好。(2) 计算复杂度，由于在数据挖掘中的操作对象是海量的数据库，因而空间和时间的复杂度将 是非常重要的问题。(3) 可解释性，分类结果只有可解释性好，容易理解，才能更好地用于决策支持。(4) 可伸缩性，一个模型是可伸缩的，是指在给定内存和磁盘空间等可用的系统资源的前提下，算法的运行时间应当随数据库大小线性增加。(5) 稳定性，模型不随数据的变化而过于剧烈变化。(6) 强壮性，模

38、型在数据集中含有噪声和空缺值的情况下，仍具有较好的正确分类数据的能力。(7) 成本，这涉及预测错误代价所产生的计算花费8.2 分类准确度的定义分类模型的性能常根据模型正确预测和错误预测的检验记录的百分比来进行评估。 方法是建立一 个混合矩阵，根据混合矩阵来计算分类模型的分类准确率和分类差错率。一个描述二元分类问题的混淆矩阵如表：预测类别+-实际类别+正确的正例(TP)错误的负例(FN)-错误的正例(FP)正确的负例(TN)正确预测数 样本总数TP TN分类准确度(accuracy)为：Accuracy分类差错率(Errorate)为：Errorrate1 AccuracyTP TNCFN FP

39、查准率(Precision)定义为正确分类的正例个数占分类为正例的样本个数的比例:查全率(Recall)定义为正确分类的正例个数占实际正例个数的比例：8.3分类准确度度量的不足通常分类算法寻找的是分类准确率高的分类模型。分类准确度在一般情况下可以满足分类器模型的比较。但是，分类准确度：默认所有数据集都是平衡数据集，但很多数据集是不平衡的，即 不同类的样本分布不平均。默认所有的错误代价都是相同的，许多实际领域中往往代价不同。可 以采用ROC曲线分析方法来度量分类器的性能，与分类准确度评估方法相比，ROC曲线分析方法具有以下优点：(1) 充分利用了预测得到的概率值。(2) 给出不同类的不同分布情况

40、差别，即当是不平衡数据时，不同的数据分布，将得到不同的分 类结果，而准确率评估则默认所有的数据集都是平衡数据集。(3) 考虑了不同种类错误分类代价的不同。(4) 二类分类的Roc曲线通过斜率反映了正例和反例之间的重要关系，同时也反映出类的分布和代价之间的关系。(5) 可以使分类器的评估结果用曲线的形式更直观地展示在二维空间中。8.4分类模型评估方法我们已经知道如何度量分类模型的准确率或误差率。那么，如何使用以上度量得到分类器的准 确率的可靠估计？通常评估准确率的常用技术包括：保持方法、随机子抽样、交叉验证等。他们都 是基于给定数据的随机抽样划分来评估准确率的技术。保持方法 在这种方法中，给定数

41、据随机地划分为两个独立的集合，作为训练集和检验集，其中训练集用 于构造分类器，而测试集用于测试分类器的性能。其执行步骤如下：(1) 以不放回抽样方式把数据集分为两个相互独立的子集：训练集和测试集。通常情况下，指定 三分之二的数据分配到训练集，其余三分之一分配到测试集。(2) 使用训练集来训练构建分类模型，用测试集来评估分类模型的分类准确率。随机子抽样随机子抽样 (Random Subsampling) 方法可以看成是保持方法的多次迭代，并且每次都要把数 据集分开，随机抽样形成测试集和训练集。其执行步骤如下：(1) 以不放回抽样方式从数据集 D 中随即抽取样本；这些样本形成新的训练集D1，D 中

42、其余的样本形成测试集 D2。通常D中的2/3作为D1，而剩下的1/3作为D2 ;(2) 用 D1 来训练分类器，用 D2 来评估分类准确率。(3) 步骤(2)循环K次。K 越大越好，总准确率估计取每次迭代准确率的平均值。K- 折交叉验证k- 折交叉验证 (k-fold cross-validation) 方法中确保每个样本用于训练的次数相同，并且用于检大小大致相等，然后进行 k 次训练和检验的过程。与保持和随机子抽样方法不同，这里每个样本用于训练的次数相同，并且用于检验一次。对于分类， 准确率估计是 k 次迭代正确分类的总数除以初始数据中的样本总数。 对于回归预测， 误差估计可以用 k 次迭代

43、的总损失除以初始总样本来计算。第四章 聚类1 聚类的定义聚类 (Clustering) 是将数据集划分为若干相似对象组成的多个组 (group) 或簇 (cluster) 的过程， 使得同一组中对象间的相似度最大化，不同组中对象间的相似度最小化。或者说一个簇 (cluster) 就 是由彼此相似的一组对象所构成的集合，不同簇中的对象通常不相似或相似度很低。聚类分析中“簇”的特征：聚类所说的簇不是事先给定的，而是根据数据的相似性和距离来划 分，另外聚类的数目和结构都没有事先假定。聚类与分类的区别：聚类问题是无指导的：没有预先定义的类。分类问题是有指导的：预先定 义有类。聚类方法的 目的 是寻找数

44、据中：潜在的自然分组结构和感兴趣的关系。聚类分析应用领域：统计学与模式分析，金融分析，市场营销，决策支持，信息检索， WEB 挖 掘，网络安全，图象处理，地质勘探、城市规划，土地使用、空间数据分析，生物学，天文学，心 理学，考古学等。聚类有着广泛的应用，既可作为一种独立的数据挖掘方法使用，也可作为预处理工具，为其它 数据挖掘任务作数据准备。如在电信业务数据挖掘中，作为一种独立的方法用于客户细分，也可以 作为异常挖掘的预处理步骤。2 主要聚类方法分类聚类方法主要有：基于划分的方法，如 K-means 算法，一趟聚类算法；基于层次的方法如单 链算法、 BIRCH 算法； 基于密度的方法， 如 DB

45、SCAN 算法；基于图的方法， 如 Chameleon 和 SNN 算法； 基于网格的方法， 如 STING 算法；基于模型的方法， 如 EM 算法；基于神经网络的聚类算法、 谱聚类算法、蚁群聚类算法等。3 基于划分的方法给定 n 个对象或元组组成的数据库， 一个划分方法构建数据的 k 个划分， 每个划分表示一个聚 类，并且 k=n 。划分方法满足如下要求：(1) 每个组至少包含一个对象；(2) 每个对象必须属于且只属于一个组。 划分式聚类算法需要预先指定簇数目或簇中心，通过反复迭代运算，逐步降低目标函数的误差 值，当目标函数值收敛时，得到最终聚类结果。这类方法分为基于质心的 (Centroi

46、d-based) 划分方 法和基于中心的 (Medoid-based) 划分方法。k-means 算法用 表示一个簇， 其中 n 表示簇中包含的对象个数， Mean 表示簇中对 象的平均值(质心) 。k-means 是基于 质心的方法典型算法，算法描述如下：(1) 从数据集 D 中任意选择 k 个对象作为初始簇中心；(2) Repeat ；(3) 根据簇中对象的均值，将每个对象 (再 )指派到最相似的簇；(4) 更新簇均值，即计算每个簇中对象的均值；(5) until 簇不再发生变化。k-means 算法的优缺点：优点为算法描述容易、实现简单、快速，缺点如下：(1) 簇的个数 k 难以确定；(

47、2) 聚类结果对初始簇中心的选择较敏感；(3) 对噪音和异常数据敏感；(4) 不能用于发现非凸形状的簇，或具有各种不同大小的簇。4 层次聚类算法层次聚类算法分为凝聚层次聚类和分裂层次聚类。凝聚层次聚类的思想： 最初将每个对象 (自身 )作为一个簇， 然后将这些簇进行聚合以构造越来越 大的簇，直到所有对象均聚合为一个簇，或满足一定终止条件为止。绝大多数层次聚类方法属于这 一类，只是簇间相似度的定义有所不同。分裂层次聚类的思想：首先将所有对象看成一个簇的内容，将其不断分解以使其变成越来越小 但个数越来越多的小簇，直到所有对象均独自构成一个簇，或满足一定终止条件为止。典型层次聚类方法有： BIRCH

48、 、 ROCK 和 CURE 算法。BIRCH 算法简介如下：BIRCH 方法通过集成层次聚类和其它聚类算法来对大量数据进行聚类，其中层次聚类用于初始 的微聚类阶段，而其它方法如迭代划分用于在后面的宏聚类阶段。BIRCH 引入了两个概念： 聚类特征 CF(Clustering Feature) 和聚类特征树 (CF tree) ，它们用于概 括簇描述。这些结构帮助聚类方法在大型数据库中取得好的速度和伸缩性，使得 BIRCH 方法对对象 的增量和动态聚类也非常有效。聚类特征CF是一个三维向量，汇总了对象簇的信息。给定簇中n个m维对象或点xj，则该簇的nCF定义如下：CF n,LS,ss ，其中，

49、n是簇中点的数目，LS是n个数据点的线性和(即 x )，SS是i1n数据点的平方和(即 xj)。SS的作用在于计算误差平方和，线性和等价于平均值。聚类特征具有可i1加性。BIRCH 采用了一种多阶段聚类技术：数据集合的单遍扫描产生一个基本好的簇，一或多遍的额 外扫描可以用来进一步 (优化 )改进聚类质量。它主要包括两个阶段：阶段一： 扫描数据库，建立一棵存放于内存的初始 CF 树，它可以看作数据的多层压缩，试图 保留数据的内在聚类结构。阶段二： 采用某个 (选定的 )聚类算法对 CF 树的叶节点进行聚类，把稀疏的簇当作离群点删除而 把稠密的簇合并为更大的簇。5 基于密度的聚类算法将簇看作是数据

50、空间中被低密度区域(代表噪声 )分割开的稠密对象区域。 DBSCAN 是一种典型的基于密度的方法。DBSCAN 是一种基于高密度连通区域的聚类方法，该算法将具有足够高密度的区域划分为簇， 并在具有噪声的空间数据中发现任意形状的簇，它将簇定义为密度相连的样本点的最大集合。一些 基本概念如下。邻域：给定对象半径&内的邻域称为该对象的邻域。核心对象：如果对象的邻域至少包含最小数目Min Pts的对象，则称该对象为核心对象。直接密度可达：给定一个对象集合 D，如果p在q的邻域内，而q是一个核心对象，则称对象 p 从对象 q 出发时是直接密度可达的 (directly density-reachable

51、) 。密度可达：如果存在一个对象链pi,p2,pn,piq, pnp，对于PiD(1 i n) , Pi 1是从Pi关于和 MinPts 直接密度可达的， 则对象 p 是从对象 q 关于 和 MinPts 密度可达的 (density-reachable) 。密度相连：如果存在对象o D,使对象p和q都是从o关于和MinPts密度可达的，那么 对象 p 到 q 是关于 和 MinPts 密度相连的 (density-connected) 。密度可达是直接密度可达的传递闭包， 这种关系是非对称的。 只有核心对象之间相互密度可达。然而，密度相连性是一个对称关系。基于密度的簇是基于密度可达性的最大密

52、度相连对象的集合。不包含在任何簇中的对象认为是噪声。DBSCAN通过检查数据集中每点的&邻域来搜索簇。如果点p的&邻域包含的点多于 MinPts个，则创建一个以 p 为核心对象的簇。 然后， DBSCAN 迭代地聚集从这些核心对象直接密度可达的 对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点添加到任何簇时，该过程结束。具 体描述如下 :(1) 检查数据库中尚未检查过的对象 p ,如果 p 未被处理 (归入某个簇或标记为噪声 ) ,则检查其Eps 邻域 N Eps(p) ,若 NEps(p) 包含的对象数不小于 MinPts , 建立新簇 C ,将 NEps(p) 中所有点加入 C；(

53、2) 对 C 中所有尚未被处理的对象 q , 检查其 Eps 邻域 N Eps(q) ,若 N Eps(q) 包含至少 MinPts 个对 象,则将 NEps(q) 中未归入任何一个簇的对象加入 C；(3) 重复步骤 (2) ,继续检查 C 中未处理对象 ,直到没有新的对象加入当前簇C；(4) 重复步骤 (1) 、 (2)、 (3) ,直到所有对象都归入了某个簇或标记为噪声。如果使用空间索引，DBSCAN的计算复杂度是O(NlogN),否则，计算复杂度是0(N2)。如果用户 定义的参数&和Min Pts设置恰当，该算法可以有效地找出任意形状的簇。6 一趟聚类算法具体过程如下：(1) 初始时，簇

54、集合为空，读入一个新的对象；(2) 以这个对象构造一个新的簇；(3) 若已到数据库末尾，则转 (6)，否则读入新对象，利用给定的距离定义，计算它与每个已有 簇间的距离，并选择最小的距离；(4) 若最小距离超过给定的半径阈值r，转(2);(5) 否则将该对象并入具有最小距离的簇中并更新该簇的各分类属性值的统计频度及数值属 性的质心，转 (3) ；(6) 结束。聚类阈值 r 采用抽样技术确定范围，具体描述如下：(1) 在数据集 D 中随机选择 N0 对对象；(2) 计算每对对象间的距离；(3) 计算(2)中距离的平均值 EX 和标准差 DX；(4) 取 r 在 EX+0.25DX 到 EX-2DX

55、 之间 (不同的问题可能要求的范围不同！ ！ ) 一趟聚类算法，只需扫描数据集一遍即得到结果聚类，具有近似线性时间复杂度，高效，参数 选择简单，对噪声不敏感的优点；但这一算法本质上是将数据划分为大小几乎相同的超球体，不能 用于发现非凸形状的簇，或具有各种不同大小的簇。对于具有任意形状簇的数据集，算法可能将一 个大的自然簇划分成几个小的簇，而难以得到理想的聚类结果。7 聚类算法评价高质量的簇其特点是簇内相似度高和簇间相似度低。因此评估聚类结果质量的准则有两种 :(1) 内部质量评价准则，通过计算簇内部平均相似度、簇间平均相似度或整体相似度来评价聚类效 果。(2) 外部质量评价准则，基于一个已经存

56、在的人工分类数据集(已经知道每个对象的类别 )进行评价。如 k-means 算法的 SSE 属于内部质量评价准则；而聚类精度为外部质量评价准则。第五章 关联分析1 关联分析的定义关联分析 (Association Analysis) 用于发现隐藏在大型数据集中的令人感兴趣的联系。联系的表 示方式一般为关联规则或频繁项集，例：尿布T 啤酒。2 关联分析的应用挖掘商场销售数据，发现商品间的联系，帮助商场进行促销及货架的摆放； 挖掘医疗诊断数据，可以发现某些症状与某种病之间的关联，为医生进行疾病诊断和治疗提供 线索；网页挖掘揭示不同浏览网页之间的有趣联系；3 关联分析的基本概念项集：一个包含 k 个

57、数据项的项集就称为 k- 项集。 支持度计数：整个交易数据集中包含该项集的事务数。 频繁项集：一个项集在数据集中出现的次数大于某个阈值。关联规则：形如 X - Y的蕴涵式，其中 X I , Y I，并且X Y 。例：可乐，尿 布- 啤酒 支持度：s(X-Y)= d (XUY)/N置信度：c(X- Y)= d (XUY)/ d (X)4 关联分析的任务 找出数据集中隐藏的强规则，通常分为两个步骤，首先在数据集中找出频繁项集，然后从频繁项集中，提取所有高置信度的规则。5 频繁项集发现的 2 个经典算法 经典的发现频繁项集的算法包括： Apriori 算法和 FP-growth 算法。6 Aprio

58、ri 算法Apriori 算法具有一个 Apriori 性质，即先验原理来控制候选项集的指数增长。Apriori 性质 (先验原理 )：如果一个项集是频繁的，则它的所有子集也是频繁的，相反：如果一 个项集是非频繁的，则它的所有超集也一定是非频繁的。Apriori 算法描述：找出 1- 频繁项集；1- 频繁项集作为候选项集；重复直到没有新的频繁项集产生从长度为 k-1 的频繁项集中产生长度为 k 的候选项集 减掉那些长度为 k-1 但不频繁的项集的所有超集 扫描数据库计算每个 k 候选项集的支持度 去掉那些不频繁的 k 候选项集，留下频繁的 k 候选项集Apriori 算法的核心内容：候选项集的

59、产生，即如何从前 (k-1) 项集中提取出 k 项集 ?候选项集的剪枝，即如何通过剪枝的策略 ,来删除一些侯选 k 项集 ?Apriori 算法的候选项集的产生方法：Apriori算法采用Fk-i XFk-i方法来产生候选项集。该方法描述如下：通过合并一对频繁 (k-1)- 项集来产生频繁 k 项集。A=a1,a2,ak-1,B=b1,b2,bk-1是一对频繁(k-1)-项集，合并A和B,如果他们满足条件 ai=bi (i=1,2,k-2)且 ak-1 bk-1例:面包 , 尿布+面包 , 牛奶 - 面包, 尿布, 牛奶啤酒, 尿布 + 尿布, 牛奶 不合并 !Apriori 算法的候选项集的

60、剪枝：1 )利用先验原理，进行部分剪枝。2)使用 HASH 树进行支持度计数。候选集的计算：扫描交易数据库计算每个候选集的支持度，为了减少比较的次数，将候选集以hash 表的结构存储，不是将每个交易都去匹配候选集，而是将交易数据匹配 hash 桶中的候选集。7 关联规则的生成前面介绍的 Apriori 算法和 FP-growth 算法都是频繁项集提取算法。在提取出频繁项集的基础 上，就可以生成强关联规则，方法如下：给定频繁项集 X,取X的每个非空真子集 S,如果规则StX- S满足置信度阈值，则该规则为 强关联规则。8 关联规则的评估关联规则的评估通常有 2 种方式：一种通过统计论据来评估 ,

61、 支持度、置信度、提升度；另一 种通过主观论据来评估。统计论据评估： 支持度：反映了关联规则是否具有普遍性。支持度高说明这条规则可能适用于数据集中的大部 分事务。置信度：反映了关联规则的可靠性。置信度高说明如果满足了关联规则的前件,同时满足后件 的可能性也非常大。存在问题：支持度过高会导致一些潜在的有价值的关联规则被删去,置信度有时也不能正确反 映前件和后件之间的关联。提升度： 反映规则前后件的相关性, 若提升度小于 1 表示前后件存在负相关关系, 否则正相关。主观评价： 可视化：需要友好的环境,保持用户参与,允许领域专家解释和检验被发现的模式,与数据挖 掘系统交互。基于模板的方法：允许用户限

62、制挖掘算法提取的模式类型,只把满足用户指定的模板的规则提供给用户，而不是报告提取所有模式。主观兴趣度度量：通过主观度量如概念分层，商品利润等，使用这些度量来过滤那些没有价值的模式。第六章 异常挖掘1 异常挖掘的定义及应用异常数据的定义：异常是在数据集中偏离大部分数据的数据，使人怀疑这些数据的偏离并非由 随机因素产生，而是产生于完全不同的机制。异常挖掘就是发现数据集中的异常数据。大多数数据挖掘方法发现适用于大部分数据的常规模式，这种情况下，试图降低或消除异常数 据的影响，异常数据通常作为噪音而忽略。而在有些应用领域识别异常数据是许多工作的基础和前 提，异常数据可能对应于稀有事件或异常行为而具有特殊的意义和很高的实用价值。异常检侧目前 已成为数据挖掘的一个重要方面， 在许多应用领域 （如风险控制领域 ），特别是在“广义安全问题” 中 异常数据正逐步成为一种有用的工具，被用来发