数据挖掘课程复习提纲(4+0)

数据挖掘课程复习提纲（4+0）有关考试题型：一、选择题（每题2分，共16分）二、判断题（每题1分，共10分)三、填空题（每空1分，共19分）四、简答题（每题5分，共15分）五、计算题（每题10分，共40分）基本要求：掌握数据预处理、分类、聚类、关联分析、离群点检测的基本方法，及每类方法的应用场景（每类方法理解、熟悉一个例子）。算法重点掌握k-means、一趟聚类、Appriori及基于密度的离群点检测方法；掌握决策树分类(C4.5、CART)、KNN分类的基本思想，基于聚类的离群点检测方法的思想。第一章绪论1数据挖掘的定义技术层面：数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中、人们事先不知道的、但又潜在有用的信息和知识的过程。商业层面：数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。2数据挖掘的任务预测任务：根据其它属性的值预测特定（目标）属性的值，如回归、分类、异常检测。描述任务：寻找概括数据中潜在联系的模式，如关联分析、聚类分析、序列模式挖掘。聚类(Clustering)分析“物以类聚，人以群分”。聚类分析技术试图找出数据集中数据的共性和差异，并将具有共性的对象聚合在相应的簇中。聚类分析可以帮助判断哪些组合更有意义，聚类分析已广泛应用于客户细分、定向营销、信息检索等领域。分类(Classification)分析分类分析就是通过分析示例数据库中的数据，为每个类别做出准确的描述，或建立分析模型，或挖掘出分类规则，然后用这个分类模型或规则对数据库中的其它记录进行分类。分类分析已广泛应用于用户行为分析(受众分析)、风险分析、生物科学等领域。聚类与分类的区别聚类问题是无指导的：没有预先定义的类。分类问题是有指导的：预先定义有类。关联(Association)分析关联分析是发现特征之间的相互依赖关系，通常是在给定的数据集中发现频繁出现的模式知识(又称为关联规则)。关联分析广泛用于市场营销、事务分析等领域。离群点(Outlier)检测离群点检测就是发现与众不同的数据。离群点检测已广泛应用于(商业、金融、保险等领域)欺诈行为的检测，网络入侵检测，反洗钱，犯罪嫌疑人调查，海关、税务稽查等领域。回归(Regression)分析回归分析是确定一个变量与一个或多个变量间相互依赖的定量关系的分析方法，常应用于风险分析、销售预测、作文自动评分等领域。序列模式(SequentialPattern)挖掘序列模式挖掘是指分析数据间的前后序列关系，包括相似模式发现、周期模式发现等，应用于客户购买行为模式预测、Web访问模式预测、疾病诊断、网络入侵检测等领域。6数据挖掘使用的软件SPSSClementine、SASEnterpriseMiner、IBMIntelligentMiner、SQLServer2005，OracleDM等商用软件能够提供常规的挖掘过程和挖掘模式。Matlab，Excel(DatamininginExcel:XLMiner)等提供了数据挖掘模块。Weka，RapidMiner(YALE)，ARMiner等为开源数据挖掘工具。7数据挖掘在商业领域中的应用(1)市场营销；(2)交叉销售与交叉营销；(3)客户关系管理；(4)个性化推荐与个性化服务；(5)风险分析与控制；(6)欺诈行为检测和异常模式的发现；(7)供应链库存管理中的需求预测；(8)人力资源管理第三章数据挖掘建模方法1．Clementine的数据挖掘方法论CRISP-DMCRISP-DM（CRoss-IndustryStandardProcessforDataMining）即为”跨行业数据挖掘过程标准”，为一个KDD工程提供了一个完整的过程描述，该模型将一个KDD工程分为6个不同的，但顺序并非完全不变的阶段。业务理解（BusinessUnderstanding）其任务包括：确定商业目标、评析环境、确定数据挖掘目标、制定项目计划。数据理解（DataUnderstanding）其任务包括：收集原始数据、描述数据、探索数据、检验数据质量。数据准备（DataPreparation）其任务包括：选择数据、清洗数据、构造数据、整合数据、规范化数据等。建模（Modeling）其任务包括：选择建模技术、生成测试计划、构建模型、评估模型（参数设置等技术角度）。评估（Evaluation）其任务包括：评价结果、重审过程、确定下一步。部署（Deployment）其任务包括：规划部署、规划监控与维护、产生最终报告、回顾项目。2成功建立预测模型的注意要点要成功建立预测模型，需要注意以下三点：(1)预测模型的时间范围(2)模型的使用有效期(3)建立预测模型的假设假设1：历史是未来的写照假设2：数据是可以获得的假设3：数据中包含我们的预期目标3有效模型的建立需要考虑以下因素：(1)预测建模的第一项任务就是搜集足够预先分类好的数据，将模型集分为三部分：训练集、测试集、评估集，并理解模型在各个子集上的效果。(2)对于类别不平衡的数据，通过抽样来控制模型集的密度，即不同分布的类别比例。(3)注意观察所用数据的输入和输出时间范围，所有输入都必须出现在输出之前，保留一个执行期间是明智的选择。(4)在模型集中使用多重时间窗口有助于确保模型稳定、并在时间上易于转换。(5)大多数建模过程需要建立多个模型，并对多个模型的效果进行比较，以选用效果最好的模型进行预测，或者对多个模型进行组合，以得到性能更优的集成分类模型。(6)对不同的模型集、模型参数以及时间范围进行试验，有助于建立更好更稳定的模型。4建立有效预测模型的基本步骤：(1)用训练集进行训练建立模型(2)利用测试集，对模型进行修正(3)对模型的效果进行评价第3章聚类分析1聚类的定义聚类(Clustering)是将数据集划分为若干相似对象组成的多个组(group)或簇(cluster)的过程，使得同一组中对象间的相似度最大化，不同组中对象间的相似度最小化。或者说一个簇(cluster)就是由彼此相似的一组对象所构成的集合，不同簇中的对象通常不相似或相似度很低。聚类分析中“簇”的特征：聚类所说的簇不是事先给定的，而是根据数据的相似性和距离来划分，另外聚类的数目和结构都没有事先假定。聚类方法的目的是寻找数据中：潜在的自然分组结构和感兴趣的关系。聚类有着广泛的应用，既可作为一种独立的数据挖掘方法使用，也可作为预处理工具，为其它数据挖掘任务作数据准备。如在电信业务数据挖掘中，作为一种独立的方法用于客户细分，也可以作为异常挖掘的预处理步骤。2数据挖掘中使用的数据(1)不同的属性类型：分为分类属性和数值属性，分类属性又分标称型和序数型，而数值属性又分区间型和比率型。如性别为标称型，好坏等级为序数型，日期时间为区间型，分数为比率型。(2)数据集的特性:维度(Dimensionality)，稀疏性(Sparsity)，分辨率(Resolution)。3距离与相似性属性之间的相似性度量(1)Cosine相似度定义两个向量的夹角余弦为相似度，即：miimiimiiiqpqpqpqpqpqps1212122||||||||),cos(),(取值范围在区间[-1,1]内。(2)相关系数(Correlationcoefficient)miiimiiimiiiiiqqppqqppqps12121)()()()(),(相关系数是标准化后的对象之间的夹角余弦，取值范围在区间[-1,1]内，它表示两个向量的线性相关程度。具有平移不变性。(3)广义Jaccard系数广义Jaccard系数又称为Tanimoto系数，用EJ表示，取值范围在区间[0,1]内。广泛用于信息检索和生物学分类中，在二元属性情况下简化为Jaccard系数。iiiiiiiiiiqpqpqpqpJ22),(E常用距离函数:(1)间隔数值属性设m为样本空间的维数，对于任意样本对象],,,[21mpppp与],,,[21mqqqq。欧式(Euclidean)距离：miiiqpqpd122||),(曼哈顿(Manhattan)距离：miiiqpqpd11||),(Canberra距离：miiiiiCanbqpqpqpd1||||||),((2)二值属性二值属性变量(binaryvariable)只有两种状态:0或1,表示属性的存在与否。一种差异计算方法就是根据二值数据计算。假设二值属性对象p和q的取值情况如表2-1所示。其中11n表示对象p和q中均取1的二值属性个数，10n表示对象p取1而对象q取0的二值属性个数，01n表示对象p取0而对象q取1的二值属性个数，00n表示对象p和q均取0的二值属性个数。表2-1二值属性对象p和q的取值情况对象p对象q10合计111n10n1011nn001n00n0001nn合计0111nn0010nnJaccard系数定义如下：1110011001),(nnnnnqpd4K-means算法k-means算法用n,Mean表示一个簇，其中n表示簇中包含的对象个数，Mean表示簇中对象的平均值（质心）。k-means是基于质心的方法典型算法，算法描述如下：(1)从数据集D中任意选择k个对象作为初始簇中心；(2)Repeat；(3)根据簇中对象的均值，将每个对象(再)指派到最相似的簇；(4)更新簇均值，即计算每个簇中对象的均值；(5)until簇不再发生变化。k-means算法的优缺点：优点为算法描述容易、实现简单、快速，缺点如下：(1)簇的个数k难以确定；(2)聚类结果对初始簇中心的选择较敏感；(3)对噪音和异常数据敏感；(4)不能用于发现非凸形状的簇，或具有各种不同大小的簇；(5)只能用于处理数值属性的数据集，不能处理包含分类属性的数据集。5一趟聚类算法具体过程如下：(1)初始时，簇集合为空，读入一个新的对象；(2)以这个对象构造一个新的簇；(3)若已到数据库末尾，则转(6)，否则读入新对象，利用给定的距离定义，计算它与每个已有簇间的距离，并选择最小的距离；(4)若最小距离超过给定的半径阈值r，转(2)；(5)否则将该对象并入具有最小距离的簇中并更新该簇的各分类属性值的统计频度及数值属性的质心，转(3)；(6)结束。聚类阈值r采用抽样技术确定范围，具体描述如下：(1)在数据集D中随机选择0N对对象；(2)计算每对对象间的距离；(3)计算(2)中距离的平均值EX和标准差DX；(4)取r在EX+0.5DX到EX-0.5DX之间(不同的问题可能要求的范围不同！！)一趟聚类算法的优点在于只需扫描数据集一遍即得到聚类结果，具有近似线性时间复杂度、效率高、参数选择较简单有效、以及对离群点和噪声不敏感。与k-means算法不同，一趟聚类算法对数据样本的顺序比较敏感，通过聚类阈值的改变来影响聚类得到的簇个数。与k-means算法类似，一趟聚类算法也不能用于发现非凸形状的簇，或具有各种不同大小的簇。对于具有任意形状簇的数据集，算法可能将一个大的自然簇划分成几个小的簇，而难以得到理想的聚类结果。6.新的距离定义假设数据集D有m个属性，其中有Cm个分类属性和Nm个数值属性，NCmmm，不妨设分类属性位于数值属性之前，用iD表示第i个属性取值的集合。定义3-1给定簇C，iDa，a在C中关于iD的频度)(|aFreqiDC定义为C在iD上的投影中包含a的次数。定义3-2给定簇C，C的摘要信息CSI(ClusterSummaryInformation)定义为：},{SummarynCSI，其中||Cn为C中包含对象的个数，Summary由分类属性中不同取值的频度信息和数值型属性的均值两部分构成，即：)},,,(,1},))(,{(,{21|NCCCimmmmCiDCiicccCenmiDaaFreqaStatCenStatSummary