数据挖掘课程复习提纲.doc

《数据挖掘课程复习提纲.doc》由会员分享，可在线阅读，更多相关《数据挖掘课程复习提纲.doc（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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、KNN、Apriori及基于距离、密度、聚类的异常检测方法。第一章 绪论1 数据挖掘的

2、定义技术层面：数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中、人们事先不知道的、但又潜在有用的信息和知识的过程。商业层面：数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。2 数据挖掘的任务预测任务：根据其它属性的值预测特定（目标）属性的值，如回归、分类、异常检测。描述任务：寻找概括数据中潜在联系的模式，如关联分析、演化分析、聚类分析、序列模式挖掘。(1) 关联(Association)分析关联分析，发现特征之间的相互依赖关系，通常是从给定的数据集中发现频繁

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

4、化的数据对象的变化规律和趋势进行建模描述。 如：商品销售的周期(季节)性。 (5) 异常(Outlier)分析异常分析就是对异常数据的挖掘、分析。比如商业欺诈行为的自动检测，网络入侵检测，金融欺诈检测，反洗钱，犯罪嫌疑人的调查等。(6) 序列模式(Sequential Pattern)挖掘 分析数据间的前后序列关系 3 数据挖掘的对象包括空间数据库、时间序列数据库、流数据、多媒体数据库、文本数据和万维网4.知识发现的主要步骤： (1) 数据清洗(data clearing)。其作用是清除数据噪声和与挖掘主题明显无关的数据。(2) 数据集成(data integration)。其作用是将来自多数

5、据源中的相关数据组合到一起。(3) 数据转换(data transformation)。其作用是将数据转换为易于进行数据挖掘的数据存储形式。(4) 数据挖掘(data mining)。其作用是利用智能方法挖掘数据模式或规律知识。(5) 模式评估(pattern evaluation)。其作用是根据一定评估标准从挖掘结果筛选出有意义的相关知识。(6) 知识表示(knowledge presentation)。其作用是利用可视化和知识表达技术，向用户展示所挖掘的相关知识。数据挖掘只是知识发现过程的一个步骤。5 数据挖掘产生背景及应用领域产生背景：“数据过剩”、“信息爆炸”与“知识贫乏” 使得人们淹

6、没在数据中， 难以制定合适的决策!应用领域：在许多行业都有广泛应用，有大量数据的领域就有应用。(1)数据挖掘在商业领域中的应用市场分析和管理，公司分析和风险管理，欺诈行为检测和异常模式的发现，自动趋势预测,(2)数据挖掘在计算机领域中的应用信息安全：入侵检测，垃圾邮件的过滤，互联网信息/使用挖掘，智能回答系统(3)其它领域中的应用数据挖掘在工业制造方面的应用，生物信息或基因的数据挖掘，体育竞赛，天文学，军事情报分析(反恐)，电视观众预测，多媒体、空间数据分析，6 数据挖掘使用的软件SPSS Clementine、SAS Enterprise Miner 、IBM Intelligent Min

7、er 、SQL Server 2005，Oracle DM等商用软件能够提供常规的挖掘过程和挖掘模式。Matlab， Excel(Data mining in Excel: XLMiner)等提供了数据挖掘模块。Weka，RapidMiner(YALE)，ARMiner等为开源数据挖掘工具。7 数据挖掘领域10大挑战性问题：(1) 数据挖掘理论的构建(2) 高维、数据流数据挖掘(高效、可扩展) (3) (时间)序列数据挖掘(4) 从复杂数据中挖掘复杂知识(5) 网络环境下的数据挖掘技术 (6) 分布式、多代理的数据挖掘(7) 生物及环境问题数据挖掘(8) 相关问题的数据挖掘处理(9) 安全、隐

8、私及数据整合(10) 非静态、不平衡及代价敏感的数据挖掘第二章 数据预处理1 数据挖掘中使用的数据(1) 数据挖掘中使用的数据是数据对象及其属性的集合。其中：属性是指对象的性质或特性，对象也称为数据对象、点、样本、观测或是实体等。数据集是数据对象的集合(同分布、同特征)。(2) 不同的属性类型：分为分类属性和数值属性，分类属性又分标称型和序数型，而数值属性又分区间型和比率型。如性别为标称型，好坏等级为序数型，日期时间为区间型，分数为比率型。因此，根据属性具有的不同性质，属性可分为四种：标称、序数、区间、比例 。(3) 数据集的类别：记录数据、基于图形的数据、有序的数据、序列数据。(4) 数据集

9、的特性:：维度(Dimensionality)，稀疏性(Sparsity)，分辨率(Resolution)。2 数据的质量问题现实世界中的原始数据往往存在一定的质量问题，如：噪声、离群点、缺失值、重复数据等，需要对其进行“清洗”才能更高效地进行挖掘。中位数的定义：设给定的N个不同值的数据集按数值升序排序，如果N是奇数，则中位数是有序集的中间值，否则中位数是中间两个值的平均值。众数的定义：数据集中出现次数最多的值。3 数据预处理(1) 为什么要预处理数据o 现实世界的数据是“不干净的” 不完整的：有感兴趣的属性缺少属性值 含噪声的：包含错误或“孤立点” 不一致的：在命名或编码上存在差异o 没有高

10、质量的数据，就没有高质量的挖掘效果 高质量的决策必须依赖高质量的数据 数据仓库需要对高质量的数据进行一致性地集成o 意义 使挖掘过程更有效、更容易 目的：提供干净、简洁、准确的数据，提高挖掘效率和准确性(2) 数据预处理工作一般包括：数据清理、数据集成、数据变换、数据归约、离散化及特征选择等。数据清理包括填写空缺数据，平滑噪声数据，识别、删除孤立点，数据集成，抽样等。数据集成是集成多个数据库，数据立方体或文件。数据变换是对原始数据进行规范化和特征构造。数据归约是对数据集进行压缩表示及特征选择。数据离散化是通过概念分层和数据离散化来归约数据。(3) 抽样：用数据较小的随机样本表示大的数据集o 抽

11、样是一种选择数据对象子集进行分析的常用方法o 数据挖掘使用抽样是因处理所有数据的费用太高、太费时间 o 有效抽样原理：如果样本是有代表性的，则使用样本与使用整个数据集的效果几乎一样抽样方法：o 简单随机抽样：无放回抽样 ，有放回的抽样 o 分层抽样 特点：总体由不同类别的对象组成，每种类型的对象数量差别很大 先对数据集进行分组：数据集D被划分为互不一相交的“层”，则可通过对每一层按一定比例简单随机选样得到D的分层选样 利用聚类实现分层抽样：将数据集D划分成m个不相交的簇，再在聚类结果的簇上进行简单随机抽样抽样方法可以压缩数据量。如果数据的类别不均衡，通常采用的抽样方法是分层抽样。(4) 噪声的

12、处理方法包括：分箱（将数据落入箱中来平滑数据）、聚类（通过聚类监测并且去除孤立点）、计算机与人工结合（计算机检测可疑数据然后对可疑数据进行人工判断）、回归（通过让数据适应回归函数来平滑数据）。 规范化通过将属性数据按比例缩放，通过一个函数将给定属性的整个值域映射到一个新的值域中，即每个旧的值都被一个新的值替代。有3种规范化策略。规范化方法一 最小最大(min-max)规范化通过线性变换将值转换到区间0,1，这里分别为f的n个观测值的最小值和最大值。最小最大规范化保持原有数据之间的联系。如果今后的输入落在A的原始数据值域之外，该方法将面临“越界错误”。规范化方法二z-score规范化，其中为属性

13、标准差，为属性平均值。当属性f的实际最大和最小值未知，或异常点左右了最小最大规范化时，该方法是有用的。规范化方法三小数定标规范化小数定标规范化通过移动属性A 的小数点位置进行规范化。A 的值v 被规范化为v，由下式计算：，其中，j是使 的最小整数。(5) 数据归约策略数据归约：数据归约用来得到数据集的简约表示，它小得多，但可以产生相同的（或几乎相同的）分析结果o 数据归约策略 数据立方体聚集 维归约：通过删除不相干的属性或维减少数据量 数据压缩：用数据编码或者变换得到原始数据的压缩表示。典型的有小波变换和主成分分析 数值归约 离散化和概念分层o 归约标准 用于数据归约的时间不应当超过或“抵消”

14、在归约后的数据上挖掘节省的时间 归约得到的数据比原数据小得多，但可产生相同或几乎相同的分析结果(6) 特征提取(Feature Extraction)：由原始数据创建新的特征集o 映射数据到新的空间 从不同视角提示重要和有趣的特征 傅里叶变换(Fourier Transform) 小波变换(Wavelet Transform)o 特征构造 由一个或多个原始特征共同构造新的特征(7) 特征选择从一组已知特征集合中选择最具代表性的特征子集，使其保留原有数据的大部分信息，即所选特征子集可以像原来的特征全集一样用来正确区分数据集的每个数据对象。通过特征选择，一些和任务无关或是冗余的特征被删除，从而提高

15、数据处理的效率。特征选择可以用于解决维数灾难的问题。 特征选择目的：去除不相关和冗余的特征，降低时间空间复杂度，提高数据质量及数据泛化能力。 理想的特征子集：每个有价值的非目标特征与目标特征强相关，而非目标特征之间不相关或是弱相关 基本步骤：去掉与目标特征不相关的特征,删除冗余特征(8) 离散化与概念分层离散化：通过将属性域划分为区间，减少给定连续属性值的个数。包括等宽离散化，等频离散化等方法。概念分层：通过使用高层的概念（比如：老年，中年，青年）来替代底层的属性值（比如：实际的年龄数据值）来规约数据，概念分层可以用树来表示，树的每一个节点代表一个概念（比如：按地区划分世界）。4 距离与相似性

16、属性之间的相似性度量 (1) Cosine相似度定义两个向量的夹角余弦为相似度，即： 对文档进行聚类时通常采用余弦相似度计算相似性。(2) 相关系数(Correlation coefficient)相关系数是标准化后的对象之间的夹角余弦，它表示两个向量的线性相关程度。具有平移不变性。(3) Pearson相关系数对象之间的相似性度量常用距离函数:(1) 间隔数值属性设m为样本空间的维数，对于任意样本对象与。欧式(Euclidean)距离：曼哈顿(Manhattan)距离：Canberra距离：(2) 二值属性二值属性变量(binary variable)只有两种状态:0或1,表示属性的存在与否

17、。一种差异计算方法就是根据二值数据计算。假设二值属性对象p和q的取值情况如表2-1所示。其中表示对象p和q中均取1的二值属性个数，表示对象p取1而对象q取0的二值属性个数，表示对象p取0而对象q取1的二值属性个数，表示对象p和q均取0的二值属性个数。表2-1 二值属性对象p和q的取值情况对象p对象q10合计10合计Jaccard系数定义如下：第三章 分类1 分类的定义分类是对数据集进行学习并构造一个拥有预测功能的分类模型，用于预测未知样本的类标号，如：根据电子邮件的标题和内容预测该邮件是否为垃圾邮件。分类和回归都有预测的功能，但是：分类预测的输出为离散或标称的属性；回归预测的输出为连续属性值，

18、例如：预测未来某银行客户会流失或不流失，这是分类任务，预测某商场未来一年的总营业额，这是回归任务。2 分类的应用领域 目前分类与回归方法已被广泛应用于各行各业，如：在金融领域中，分类器被用于预测股票未来的走向。在医疗诊断中，使用分类模型预测放射学实验室医疗癌症的诊断、精神病的诊断、医疗影像的诊断等。在市场营销中，利用历史的销售数据，预测某些商品是否可以销售、预测广告应该投放到哪个区域、预测某客户是否会成为商场客户从而实施定点传单投放等。3 分类的步骤(1) 将数据集划分为训练集和测试集；(2) 对训练集进行学习，构建分类模型；（这个模型可以是决策树或分类规则等形式）(3) 用建好的分类模型对测

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

20、C4.5、CART、SLIQ、SPRINT、PUBLIC等。5.1 ID3决策树分类算法介绍ID3分类算法由Quinlan于1986年提出，使用信息增益(information gain)作为属性的选择标准。其基本思想如下：首先检测所有属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一个类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。ID3分类算法的伪代码如下：函数：DT(S,F)输入：训练集数据S，训练集数据属性集合F输出：ID3决策树(1)if 样本S全部属于同一个类别C th

21、en(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) 为该分支添加一个叶结点，并标记类标号为C；(11) else(12) 递归调用DT(SV, F-A)，为该分支创建子树；(13) end if(11) end for(12)end ifID3算法使用信息增益来获取最好的属性

22、作为决策结点，以使得训练记录被划分为较纯的子集。信息增益是度量一个给定属性划分训练集到目标类的好坏程度。信息增益值最高的属性被选择作为决策结点。ID3建决策树例子见书本。熵(entropy)的定义：熵用来度量一个属性信息的数量。假设训练集S的类标号属性C具有m个可能的值，即C=C1,C2,Cm，并且Ci在所有样本中出现的频率为Pi (i=1,2,3,m)，则该训练集S所包含的信息熵Entropy(S)为：如果所有记录都属于同一个类，则训练集S的熵值为0，表示很纯。例如假定数据集S中有14个样本，目标属性Play Ball有2个值：Play Ball=Yes, No。14个样本的分布为：9个样本

23、的类标号取值为YES，5个样本的类标号取值为NO，因此： C1=Yes在所有样本S中出现的概率为：9/14，C2=NO在所有样本S中出现的概率为：5/14，因此数据集S的熵为：信息增益的定义：ID3中信息增益（information gain）的定义是：划分前样本的不纯程度(熵)和划分后样本的不纯程度(熵）的差值。假设划分前样本数据集为S, 现在假定用属性A来划分样本S，则按属性A划分S的信息增益Gain(S,A)为：样本S的熵减去按属性A划分S后的样本子集的熵。其中：按属性A划分S后的样本子集的熵定义如下：假定属性A有k个不同的取值，从而将S划分为k个样本子集S1,S2,Sk，则按属性A划分

24、S后的样本子集的信息熵为:其中|Si|(i,=1,2,k)为划分后各样本子集中样本的个数，|S|是S中样本的个数。ID3算法总结：ID3算法是所有可能的决策树空间中一种自顶向下、贪婪的搜索方法。ID3搜索的假设空间是可能的决策树的集合，搜索目的是构造与训练数据一致的一棵决策树，搜索策略是爬山法，在构造决策树时从简单到复杂，用信息熵作为爬山法的评价函数。ID3算法的核心是在决策树各级结点上选择属性，用信息增益作为属性选择的标准，使得在每个非叶节点进行测试时能获得关于被测数据最大的类别信息，使得该属性将数据集分成子集后，系统的熵值最小。5.2 C4.5算法基于ID3算法中存在的不足，Quinlan

25、于1993年对其做出改进，提出了改进的决策树分类算法C4.5，该算法继承了ID3算法的优点，并在以下几个方面对ID3算法进行了改进：(1)能够处理连续型属性数据和离散型属性数据；(2)能够处理具有缺失值的数据；(3)使用信息增益率作为决策树的属性选择标准；(4)对生成的树进行剪枝处理，以获取简略的决策树；(5)从决策树到规则的自动产生。C4.5算法的基本描述：1)对数据集进行预处理，将连续型属性数据离散化；2)计算每个属性的信息增益和信息增益率；3)根结点属性每一个可能的取值对应一个子集，对样本子集递归地执行(2)过程，直到划分的每个子集中的观测数据都属于同一个类标号，生成决策树。4)根据构造

26、的决策树提取分类规则，对新的数据集进行分类。C4.5算法的概念描述：假定S为训练集，目标属性C具有m个可能的取值，C=C1,C2,Cm，即训练集S的目标属性具有m个类标号值C1,C2,Cm，C4.5算法所涉及的概念描述如下：(1)假定训练集S中，Ci在所有样本中出现的频率为pi(i=1,2,3,m)，则该集合S所包含的信息熵为：(2)设用属性A来划分S中的样本,计算属性A对集合S的划分熵值EntropyA(S)定义如下:若属性A为离散型数据，并具有k个不同的取值，则属性A依据这k个不同取值将S划分为k个子集S1,S2,Sk，属性A划分S的信息熵为：其中|Si|和|S|分别是Si和S中包含的样本

27、个数。如果属性A为连续型数据，则按属性A的取值递增排序，将每对相邻值的中点看作可能的分裂点，对每个可能的分裂点，计算：其中SL和SR分别对应于该分裂点划分的左右两部分子集，选择EntropyA(S)值最小的分裂点作为属性A的最佳分裂点，并以该最佳分裂点按属性A对集合S的划分熵值作为属性A划分S的熵值。(3) C4.5以信息增益率作为选择标准，不仅考虑信息增益的大小程度，还兼顾为获得信息增益所付出的“代价”：C4.5通过引入属性的分裂信息来调节信息增益，分裂信息定义为：信息增益率定义为：这样如果某个属性有较多的分类取值，则它的信息熵会偏大，但信息增益率由于考虑了分裂信息而降低，进而消除了属性取值

28、数目所带来的影响。C4.5算法例子见书本。C4.5算法对数值型属性数据的处理：C4.5可以处理数值型属性数据的分类，它的处理思想是，针对数值型属性，先对其进行递增排序，将没对相邻值的中点看做可能的分裂点，对每个可能的分裂点，计算分裂熵值，选取分裂熵值最小的分裂点作为该数值属性的最佳分裂点。具体例子请参考书本。5.3 决策树分类算法的优缺点：总的来讲，基于决策树的分类算法的具有以下优点：(1)构造的代价低；(2)在分类未知记录时非常快；(3)对于一些比较小的树非常容易解释；(4)在许多简单数据集上测试发现，决策树分类技术其准确率和其它分类技术相当。 6 贝叶斯分类算法贝叶斯分类方法是一种利用概率

29、统计知识进行学习分类的方法，属于基于统计的学习方法，即：预测一个数据对象属于某个类别的概率。例如：计算邮件是垃圾邮件或合法邮件的概率，取概率大的为预测结果。主要算法有：朴素贝叶斯分类算法，贝叶斯信念网络分类算法等。朴素贝叶斯分类算法和贝叶斯信念网络分类算法都是建立在贝叶斯定理基础上的算法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

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

31、si/s来估计，其中si是数据集D中属于类Ci的样本个数，s是数据集D的样本总数朴素贝叶斯假定一个属性值对给定类的影响独立于其他属性值，属性之间不存在依赖关系,这样： 从数据集中求概率这里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中，当且仅当: 这样X被指派到最大的类别

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

33、最近邻数目，其中每个样本可以表示为(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最近邻集合DZ4. 采用投票机制返回DZ中样本的多数类的类标号5. end for K-最近邻分类算法的优缺点：优点：算法思想简单，易于实现。缺点：最近邻分类对每个属性指定相同的权重，而数据集中不同属性可能需要赋予

34、不同的权值；由于K-NN存放所有的训练样本，直到有新的样本需要分类时才建立分类，因此当训练样本数量很大时，该学习算法的时间复杂度为n2。K-NN的扩展：对K-NN的改进主要从提高分类的速度和准确度两个方面进行。如先对训练样本中的每一类样本集进行聚类，然后用聚类后形成的子类代替属于该子类的所有样本集，从而大大减少了训练样本的数量，提高了计算速度。也可以先对未知样本集进行预分类，划分出训练集和测试集，然后采用K-NN分类器进行分类，从而提高分类进度并降低时间复杂度。8 分类模型的评价8.1 分类模型性能评价标准：(1) 分类准确率，即模型正确地预测新的或先前未见过的数据的类标号的能力。一个分类模型

35、在测试集上的准确率越高说明这个模型越好。(2) 计算复杂度，由于在数据挖掘中的操作对象是海量的数据库，因而空间和时间的复杂度将是非常重要的问题。(3) 可解释性，分类结果只有可解释性好，容易理解，才能更好地用于决策支持。(4) 可伸缩性，一个模型是可伸缩的，是指在给定内存和磁盘空间等可用的系统资源的前提下，算法的运行时间应当随数据库大小线性增加。(5) 稳定性，模型不随数据的变化而过于剧烈变化。(6) 强壮性，模型在数据集中含有噪声和空缺值的情况下，仍具有较好的正确分类数据的能力。(7) 成本，这涉及预测错误代价所产生的计算花费 8.2 分类准确度的定义分类模型的性能常根据模型正确预测和错误预

36、测的检验记录的百分比来进行评估。方法是建立一个混合矩阵，根据混合矩阵来计算分类模型的分类准确率和分类差错率。一个描述二元分类问题的混淆矩阵如表：预测类别+-实际类别+正确的正例(TP)错误的负例(FN)-错误的正例(FP)正确的负例(TN)分类准确度(accuracy)为：分类差错率(Errorate)为：查准率(Precision)定义为正确分类的正例个数占分类为正例的样本个数的比例：查全率(Recall)定义为正确分类的正例个数占实际正例个数的比例 ：8.3 分类准确度度量的不足通常分类算法寻找的是分类准确率高的分类模型。分类准确度在一般情况下可以满足分类器模型的比较。但是，分类准确度：默

37、认所有数据集都是平衡数据集，但很多数据集是不平衡的，即不同类的样本分布不平均。默认所有的错误代价都是相同的，许多实际领域中往往代价不同。可以采用ROC曲线分析方法来度量分类器的性能，与分类准确度评估方法相比，ROC曲线分析方法具有以下优点：(1)充分利用了预测得到的概率值。(2)给出不同类的不同分布情况差别，即当是不平衡数据时，不同的数据分布，将得到不同的分类结果，而准确率评估则默认所有的数据集都是平衡数据集。(3)考虑了不同种类错误分类代价的不同。(4)二类分类的Roc曲线通过斜率反映了正例和反例之间的重要关系，同时也反映出类的分布和代价之间的关系。(5)可以使分类器的评估结果用曲线的形式更

38、直观地展示在二维空间中。8.4 分类模型评估方法我们已经知道如何度量分类模型的准确率或误差率。那么，如何使用以上度量得到分类器的准确率的可靠估计？通常评估准确率的常用技术包括：保持方法、随机子抽样、交叉验证等。他们都是基于给定数据的随机抽样划分来评估准确率的技术。保持方法在这种方法中，给定数据随机地划分为两个独立的集合，作为训练集和检验集，其中训练集用于构造分类器，而测试集用于测试分类器的性能。其执行步骤如下：(1)以不放回抽样方式把数据集分为两个相互独立的子集：训练集和测试集。通常情况下，指定三分之二的数据分配到训练集，其余三分之一分配到测试集。(2)使用训练集来训练构建分类模型，用测试集来

39、评估分类模型的分类准确率。随机子抽样随机子抽样(Random Subsampling)方法可以看成是保持方法的多次迭代，并且每次都要把数据集分开，随机抽样形成测试集和训练集。其执行步骤如下：(1)以不放回抽样方式从数据集D中随即抽取样本；这些样本形成新的训练集D1，D中其余的样本形成测试集D2。通常D中的2/3作为D1，而剩下的1/3作为D2；(2)用D1来训练分类器，用D2来评估分类准确率。(3)步骤(1)(2)循环K次。K越大越好，总准确率估计取每次迭代准确率的平均值。K-折交叉验证k-折交叉验证(k-fold cross-validation)方法中确保每个样本用于训练的次数相同，并且用

40、于检验恰好一次。其思想是，将初始数据集随机划分成k个互不相交的子集D1,D2,Dk，每个子集的大小大致相等，然后进行k次训练和检验的过程。与保持和随机子抽样方法不同，这里每个样本用于训练的次数相同，并且用于检验一次。对于分类，准确率估计是k次迭代正确分类的总数除以初始数据中的样本总数。对于回归预测，误差估计可以用k次迭代的总损失除以初始总样本来计算。第四章 聚类1 聚类的定义聚类(Clustering)是将数据集划分为若干相似对象组成的多个组(group)或簇(cluster)的过程，使得同一组中对象间的相似度最大化，不同组中对象间的相似度最小化。或者说一个簇(cluster)就是由彼此相似的

41、一组对象所构成的集合，不同簇中的对象通常不相似或相似度很低。聚类分析中“簇”的特征：聚类所说的簇不是事先给定的，而是根据数据的相似性和距离来划分，另外聚类的数目和结构都没有事先假定。聚类与分类的区别：聚类问题是无指导的：没有预先定义的类。分类问题是有指导的：预先定义有类。聚类方法的目的是寻找数据中：潜在的自然分组结构和感兴趣的关系。聚类分析应用领域：统计学与模式分析，金融分析，市场营销，决策支持，信息检索，WEB挖掘，网络安全，图象处理，地质勘探、城市规划，土地使用、空间数据分析，生物学，天文学，心理学，考古学等。聚类有着广泛的应用，既可作为一种独立的数据挖掘方法使用，也可作为预处理工具，为其

42、它数据挖掘任务作数据准备。如在电信业务数据挖掘中，作为一种独立的方法用于客户细分，也可以作为异常挖掘的预处理步骤。2 主要聚类方法分类聚类方法主要有：基于划分的方法，如K-means算法，一趟聚类算法；基于层次的方法如单链算法、BIRCH算法；基于密度的方法，如DBSCAN算法；基于图的方法，如Chameleon和SNN算法；基于网格的方法，如STING算法；基于模型的方法，如EM算法；基于神经网络的聚类算法、谱聚类算法、蚁群聚类算法等。3 基于划分的方法给定 n 个对象或元组组成的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚类，并且k=n。划分方法满足如下要求：(1)每个组至少

43、包含一个对象；(2)每个对象必须属于且只属于一个组。划分式聚类算法需要预先指定簇数目或簇中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果。这类方法分为基于质心的(Centroid-based)划分方法和基于中心的(Medoid-based)划分方法。k-means算法用表示一个簇，其中n表示簇中包含的对象个数，Mean表示簇中对象的平均值（质心）。k-means是基于质心的方法典型算法，算法描述如下 ：(1) 从数据集D中任意选择k个对象作为初始簇中心；(2) Repeat；(3) 根据簇中对象的均值，将每个对象(再)指派到最相似的簇；(4) 更新簇均值，

44、即计算每个簇中对象的均值；(5) until 簇不再发生变化。k-means算法的优缺点：优点为算法描述容易、实现简单、快速，缺点如下：(1)簇的个数k难以确定；(2)聚类结果对初始簇中心的选择较敏感；(3)对噪音和异常数据敏感；(4)不能用于发现非凸形状的簇，或具有各种不同大小的簇。4 层次聚类算法层次聚类算法分为凝聚层次聚类和分裂层次聚类。凝聚层次聚类的思想：最初将每个对象(自身)作为一个簇，然后将这些簇进行聚合以构造越来越大的簇，直到所有对象均聚合为一个簇，或满足一定终止条件为止。绝大多数层次聚类方法属于这一类，只是簇间相似度的定义有所不同。分裂层次聚类的思想：首先将所有对象看成一个簇的

45、内容，将其不断分解以使其变成越来越小但个数越来越多的小簇，直到所有对象均独自构成一个簇，或满足一定终止条件为止。典型层次聚类方法有：BIRCH、ROCK和CURE算法。BIRCH算法简介如下：BIRCH方法通过集成层次聚类和其它聚类算法来对大量数据进行聚类，其中层次聚类用于初始的微聚类阶段，而其它方法如迭代划分用于在后面的宏聚类阶段。BIRCH引入了两个概念：聚类特征CF(Clustering Feature)和聚类特征树(CF tree)，它们用于概括簇描述。这些结构帮助聚类方法在大型数据库中取得好的速度和伸缩性，使得BIRCH方法对对象的增量和动态聚类也非常有效。聚类特征CF是一个三维向量

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