第3章-数据挖掘技术

第3章数据挖掘技术3.1分类（Classification）3.2关联（Association）3.3聚类（Clustering）3.4预测（Prediction）3.5数据挖掘的可视化3.6数据挖掘的实施数据仓库与数据挖掘3.1分类3.1.1概述3.1.2常见的分类算法

3.1.2.1决策树算法

3.1.2.2CLS算法

3.1.2.3ID3算法

3.1.2.4C4.5算法

3.1.2.5Autoclass算法3.1.3算法实现数据仓库与数据挖掘3.1.1分类概述分类是数据挖掘中的一个重要课题。分类的目的是获得一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到某一个给定类别。分类可用于提取描述重要数据类的模型或预测未来的数据趋势。

数据仓库与数据挖掘分类的实现构建模型：预设分类类别对每个样本进行类别标记训练集构成分类模型分类模型可表示为：分类规则、决策树或数学公式使用模型：识别未知对象的所属类别模型正确性的评价已标记分类的测试样本与模型的实际分类结果进行比较模型的正确率是指测试集中被正确分类的样本数与样本总数的百分比。测试集与训练集相分离，否则将出现过拟合（over-fitting）现象。数据仓库与数据挖掘分类的实现—模型构建TrainingDataClassificationAlgorithmsIFrank=‘professor’ORyears>6THENtenured=‘yes’Classifier(Model)数据仓库与数据挖掘分类的实现—利用模型预测ClassifierTestingDataUnseenData(Jeff,Professor,4)Tenured?数据仓库与数据挖掘分类方法的评价标准预测的正确性时间构建模型的时间使用模型所需的时间健壮性处理噪声及缺失值的能力可扩展性可操作性规则的优化决策树的大小分类规则的简洁性数据仓库与数据挖掘3.1.1分类概述常见的分类方法决策树分类决策树归纳是一种经典的分类算法。它采用自顶向下、递归的、各个击破的方式构造决策树。树的每一个结点上使用信息增益度量选择属性，可以从所生成的决策树中提取出分类规则。

数据仓库与数据挖掘3.1.1概述KNN分类即K最近邻法，最初由Cover和Hart于1968年提出的，是一个理论上比较成熟的方法。该方法的思路非常简单直观：如果一个样本在特征空间中的k个最相似（即特征空间中最邻近）样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在分类决策上只依据最邻近的一个或者几个样本的类别来决定待分类样本所属的类别。该算法较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

数据仓库与数据挖掘3.1.1概述SVM分类方法即支持向量机（SupportVectorMachine）法，由Vapnik等人于1995年提出，具有相对优良的性能指标。该方法是建立在统计学习理论基础上的机器学习方法。通过学习，SVM可以自动寻找出那些对分类有较好区分能力的支持向量，由此构造出的分类器可以最大化类与类的间隔，因而有较好的适应能力和较高的分准率。该方法只需要由各类域的边界样本的类别来决定最后的分类结果。SVM法对小样本情况下的自动分类有着较好的分类结果。数据仓库与数据挖掘3.1.1分类概述VSM分类方法即向量空间模型（VectorSpaceModel）法，由Salton等人于60年代末提出。这是最早也是最著名的信息检索方面的数学模型。其基本思想是将文档表示为加权的特征向量：D=D(T1，W1；T2，W2；…；Tn，Wn)，然后通过计算文本相似度的方法来确定待分类样本的类别。当文本被表示为空间向量模型的时候，文本的相似度就可以借助特征向量之间的内积来表示。VSM法相对其他分类方法而言，更适合于专业文献的分类。数据仓库与数据挖掘3.1.2.1决策树算法决策树分类是用属性值对样本集逐级划分，直到一个节点仅含有同一类的样本为止。决策树首先起源于Hunt等人提出的概念学习系统（ConceptLearningSystem,CLS），然后发展到Quinlan的ID3算法，最后演化为能处理连续属性值的C4.5算法。

数据仓库与数据挖掘决策树表示与例子决策树（DecisionTree）的每个内部结点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶结点代表类或类分布。树的最顶层结点是根结点。

buys_computer的决策树示意数据仓库与数据挖掘决策树表示与例子公司职员年龄收入信誉度买保险否≤40高良c2否≤40高优c2否41~50高良c1否>50中良c1是>50低良c1是>50低优c2是41~50低优c1否≤40中良c2是≤40低良c1是>50中良c1是≤40中优c1否41~50中优c1是41~50高良c1否>50中优c2描述属性类别属性数据仓库与数据挖掘决策树表示与例子年龄公司职员信誉度c1c2c1c2c1≤4041~50>50是否良优数据仓库与数据挖掘决策树分类的特点决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分枝，在决策树的叶结点得到结论。所以从决策树的根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。基于决策树的分类算法的一个最大的优点就是它在学习过程中不需要使用者了解很多背景知识（这同时也是它的最大的缺点），只要训练例子能够用属性-结论式表示出来，就能使用该算法来学习。决策树分类模型的建立通常分为两个步骤：决策树生成决策树修剪。数据仓库与数据挖掘决策树生成算法描述构造好的决策树的关键在于如何选择好的属性进行树的拓展。研究结果表明，一般情况下,树越小则树的预测能力越强。由于构造最小的树是NP-难问题，因此只能采取用启发式策略来进行。属性选择依赖于各种对例子子集的不纯度（Impurity）度量方法，包括信息增益（InformatinGain）、信息增益比（GainRatio）、Gini-index、距离度量（DistanceMeasure）、J-measure、G统计、χ2统计、证据权重（WeightofEvidence）、最小描述长度（MLP）、正交法（OrtogonalityMeasure）、相关度（Relevance）和Relief等。算法

Generate_decision_tree(samples,attribute_list)/*决策树生成算法*/输入：训练样本samples，由离散值属性表示；候选属性的集合attribute_list。输出：一棵决策树。1)创建结点N；2)IFsamples

都在同一个类CTHEN返回N

作为叶结点，以类C标记；3)IFattribute_list为空THEN返回N作为叶结点，标记为samples中最普通的类；//多数表决4)选择attribute_list中具有最高信息增益的属性test_attribute；5)标记结点N为test_attribute；6)FOReachtest_attribute中的已知值ai

由结点N长出一个条件为test_attribute=ai的分枝；7)设si是samples中test_attribute=ai的样本的集合；//一个划分8)IFsi

为空THEN加上一个树叶，标记为samples中最普通的类；9)ELSE加上一个由Generate_decision_tree(si，attribute_list-test_attribute)返回的结点；数据仓库与数据挖掘3.1.2.1决策树算法决策树的输入一组带有类别标记的样本决策树的输出一棵二叉或多叉树。二叉树的内部节点（非叶子节点）一般表示为一个逻辑判断，如形式为(ai=vi)的逻辑判断，其中ai是属性，vi是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（ID3）的内部节点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶子节点则是类别标记。数据仓库与数据挖掘3.1.2.1决策树算法决策树的构造采用自上而下的递归构造。以多叉树为例，其构造思路是：如果训练样本集中所有样本是同类的，则将它作为叶子节点，节点内容即是该类别标记；否则，根据某种策略选择一个属性，按照属性的不同取值，将样本集划分为若干子集，使得每个子集上的所有样本在该属性上具有同样的属性值。然后再依次处理各个子集。实际上就是“分而治之”（divide-and-conquer）的策略。二叉树同理，差别仅在于要选择一个好的逻辑判断。数据仓库与数据挖掘3.1.2.1决策树算法决策树构造的条件构造好的决策树的关键是：如何选择好的逻辑判断或属性。对于同样一组样本，可以有很多决策树能符合这组样本。研究表明，一般情况下，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。由于构造最小的树是NP问题，因此只能采用启发式策略选择好的逻辑判断或属性。

数据仓库与数据挖掘3.1.2.1决策树算法实际中，用于模型学习的训练数据往往不是完美的，原因是：①某些属性字段上缺值（missingvalues）；②缺少必需的数据而造成数据不完整；③数据不准确含有噪声甚至是错误的。此时，需要克服噪声和决策树剪枝。数据仓库与数据挖掘3.1.2.1决策树算法基本的决策树构造算法没有考虑噪声，生成的决策树完全与训练样本拟合。在有噪声的情况下，完全拟合将导致过分拟合（overfitting），即对训练数据的完全拟合反而不具有很好的预测性能。数据仓库与数据挖掘3.1.2.1决策树算法剪枝技术是一种克服噪声的技术，同时它也能使树得到简化而变得更容易理解。剪枝的类型向前剪枝（forwardpruning）在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。

向后剪枝（backwardpruning）是一种两阶段法：拟合－化简（fitting-and-simplifying），首先生成与训练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。数据仓库与数据挖掘3.1.2.1决策树算法剪枝的局限性剪枝并不是对所有的数据集都好，就象最小树并不是最好（具有最大的预测率）的树。当数据稀疏时，要防止过分剪枝（over-pruning）。从某种意义上而言，剪枝也是一种偏向（bias），对有些数据效果好而有些数据则效果差。

数据仓库与数据挖掘Attributes={Outlook,Temperature,Humidity,Wind}OutlookHumidityWindsunnyrainovercastyesnoyeshighnormalnostrongweakyesPlayTennis={yes,no}打高尔夫球的决策树实例（自顶向下）数据仓库与数据挖掘根据加薪百分比、工作时长、法定节假日、及医疗保险三个属性来判断一个企业的福利状况(good或bad)。数据仓库与数据挖掘3.1.2.1决策树算法CLS(ConceptLearningSystem)系统以一棵空决策树开始，并通过增加结点逐步求精，直到产生一棵能正确分类训练样本的决策树为止，是一个循环递归过程。设PN为已知训练子集，则：（1）如果PN中的所有样本均为正例，则生成一个YES结点并终止；如果PN中的所有样本均为反例，则生成一个NO结点并终止；否则，根据某种启发策略选择一个属性A，设A取值为υ1，υ2…υr，并生成新结点。（2）将PN中的样本根据其属性A的取值加以划分，生成r个子集记为PN1,PN2…PNr。（3）递归地应用该算法到每个子集PNi。数据仓库与数据挖掘3.1.2.2CLS算法CLS算法的局限性分类属性的选择决定了算法的效率与所生成的决策树的繁简程度、预测效果。选择属性是决策树归纳算法的关键。CLS算法可以产生所有可能的决策树，正确分类训练样本，并能选择最简单的决策树。但是属性选择的不确定性，在实际应用中往往受问题大小的限制。

数据仓库与数据挖掘3.1.2.3ID3算法Quinlan提出的ID3算法，对CLS算法做出了改进。它的基本算法仍然来自于CLS，但使用熵来选择属性，效果非常理想。ID3只能处理离散型描述属性；在选择根节点和各个内部节点上的分枝属性时，采用信息增益作为度量标准，选择具有最高信息增益的描述属性作为分枝属性假设nj是数据集X中属于类别cj的样本数量，则各类别的先验概率为P(cj)=nj/total，j=1,2,…,m。数据仓库与数据挖掘3.1.2.3ID3算法对于数据集X，计算期望信息计算描述属性Af划分数据集X所得的熵假设Af有q个不同取值，将X划分为q个子集{X1,X2,…,Xs,…Xq}假设ns表示Xs中的样本数量，njs表示Xs中属于类别cj的样本数量数据仓库与数据挖掘3.1.2.3ID3算法由描述属性Af划分数据集X所得的熵为其中计算Af划分数据集时的信息增益Gain(Af)=I(n1,n2,…,nm)-E(Af)数据仓库与数据挖掘3.1.2.3ID3算法举例：根据天气状况决定某天早上是否合适打高尔夫球，合适的属于正例记为P，不合适的属于反例记为N。天气由四个属性描述，即

outlook(天气形势)取值分别为sunny,overcast和rain；

temperature(温度)取值分别为cool,mild和hot；

humidity（湿度）取值为normal和high；

windy(风)取值为false和true数据仓库与数据挖掘

outlooktemperaturehumiditywindyclass

1sunnyhothighfalseN2sunnyhothightrueN3overcasthothighfalseP4rainhothighfalseP5raincoolnormalfalseP6raincoolnormaltrueN7overcastcoolnormaltrueP8sunnymildhighfalseN9sunnycoolnormalfalseP10rainmildnormalfalseP11sunnymildnormaltrueP12overcastmildhightrueP13overcasthotnormalfalseP14rainmildhightrueN

表打高尔夫球天气情况的样本集（14个）

数据仓库与数据挖掘ID3算法举例其中p=9，n=5。

gain(outlook)=I(p,n)-E(outlook)=0.940-0.694=0.246

数据仓库与数据挖掘ID3算法举例类似地，可得：

gain(temperature)=0.029gain(humidity)=0.151gain(windy)=0.048因此，outlook具有最大的信息增益，因此outlook被选为根结点并向下扩展，通过类似的方法，得到相应的ID3决策树。

数据仓库与数据挖掘数据仓库与数据挖掘3.1.2.3ID3算法优势算法理论清晰方法简单学习能力较强不足之处对较小的数据集有效对噪声比较敏感当数据集增大时，决策树可能会改变。数据仓库与数据挖掘3.1.2.4C4.5算法C4.5算法ID3有很多改进算法，其中Quinlan在1994年开发出的C4.5算法流行最广。

C4.5的改进主要体现在两方面：（1）解决了连续数据值的学习问题；（2）提供了将学习结果决策树到等价规则集的转换功能。

数据仓库与数据挖掘3.1.2.4C4.5算法C4.5算法C4.5属于一种归纳学习算法。归纳学习（InductiveLearning）旨在从大量经验数据中归纳抽取一般的判定规则和模式，它是机器学习（MachineLearning）中最核心、最成熟的一个分支。根据有无导师指导，归纳学习又分为有导师学习（SupervisedLearning，又称为示例学习）和无导师学习(UnsupervisedLearning)。C4.5属于有导师的学习算法。数据仓库与数据挖掘3.1.2.4C4.5算法示例学习算法分为两大类：覆盖算法（coveringalgorithms）分治算法（divide-and-conqueralgorithms）

前者归纳生成规则，后者归纳生成决策树。

数据仓库与数据挖掘3.1.2.5Autoclass算法Autoclass算法

是一个基于Bayesian网络的无监督的分类算法，该算法可以处理连续和离散的属性。对于连续属性值，用户应先验说明属性的概率分布类别（比如正态分布）；而对于离散属性，用户可以说明属性可能的所有取值。Autoclass算法可以把属性单独考虑，也可以先验说明某些属性的联合分布。该算法根据先验的概率分布类别，探索性地将数据集多次分成不同个数的类，然后比较这些分类，给出较优的几个结果。

数据仓库与数据挖掘3.1.2.6神经网络算法人工神经网（ArtificialNeuralNetwork，ANN）是20世纪80年代后期迅速发展起来的人工智能技术，它对噪声数据具有很高的承受能力，对未经训练的数据具有分类模拟的能力，因此在网站信息、生物信息和基因以及文本的数据挖掘等领域得到了越来越广泛的应用。在多种ANN模型中，反向传播（BackPropagation，BP）网络是应用最广的一种。

数据仓库与数据挖掘神经元通过非线性函数n维的输入向量

x

被映射为变量

ymk-fweightedsumInputvectorxoutputyActivationfunctionweightvectorwåw0w1wnx0x1xn数据仓库与数据挖掘神经网络的组成输出节点输入节点隐层节点输入矢量输入矢量:xiwij基本的BP网络由输入层、输出层和隐层组成。数据仓库与数据挖掘数据仓库与数据挖掘神经网络的拓扑结构神经网络训练之前，需要设计网络拓扑结构。设计网络拓扑的关键是，确定隐层的神经元个数及各神经元初始权值和阈值（偏差）。理论上讲，隐层的神经元数越多，逼近越精确。但实际上，隐层神经元数不宜过多；否则会极大加长训练时间，并造成网络容错能力下降。经训练后的神经网络若其准确性不能被接受，则必须重新进行拓扑设计或改用不同的初始权值和阈值（偏差）。

数据仓库与数据挖掘神经网络的训练训练的终止条件获得一组权重值，使得训练集中几乎所有样本都分类正确训练步骤利用随机值对权值进行初始化

将训练样本逐一地输入给神经网络，进行训练对于每个神经元将其所有的输入值进行线性求和计算得到总的输入利用激励函数计算其输出值计算误差修正网络权值和阈值（偏差）数据仓库与数据挖掘BP神经网络BP神经网络通过迭代处理一组训练样本，将各样本的网络预测与实际已知类标号进行比较实现学习训练，反向修改网络的权值，使得网络预测与实际类之间的误差平方最小。BP神经网络按照最优训练准则反复迭代，确定并不断调整神经网络结构，通过迭代修改，当误差收敛时学习过程终止。因此，具有分类准确、收敛性好、动态性好和鲁棒性强等优点。数据仓库与数据挖掘BP神经网络存在的问题收敛速度问题

BP分类器最大的弱点是其训练速度非常缓慢，难以收敛。尤其是当网络的训练达到一定程度后，收敛更为缓慢。局部极小点问题

BP算法采用的是梯度下降法，对一个复杂的网络而言，其误差曲面是一个高维空间中的曲面，其中分布着许多局部极小点，一旦陷入了局部极小点则算法很难逃离出来。

数据仓库与数据挖掘BP神经网络存在的问题网络瘫痪问题

在训练过程中，权值可能变得很大，这会使神经元的网络输入变得更大，从而使得其激励函数的一阶导函数在此点上的取值很小。此时的训练步长会变得非常小，最终导致网络停止收敛，这种现象即是所谓的网络瘫痪现象。数据仓库与数据挖掘其它的分类算法基于案例推理的分类基于遗传算法的分类基于粗糙集的分类基于模糊集的分类数据仓库与数据挖掘3.1.2.7粗糙集粗糙集理论是建立在分类机制的基础上的，它将分类理解成在特定空间上的等价关系，从而构成了对该空间的划分。其关键思想是将不确定的或不精确的知识用已知的知识库中的知识来近似地刻画，是目前被使用较多的一种归纳学习方法。该理论的特点是：它不需要提供除问题所需处理的数据集合之外的任何先验信息，所以对问题的不确定性的描述和处理相对客观。数据仓库与数据挖掘粗糙集基本理论(P182)1．知识与分类积木颜色形状体积x1红圆小x2蓝方大x3红三角小x4蓝三角小x5黄圆小x6黄方小x7红三角大x8蓝三角大数据仓库与数据挖掘粗糙集基本理论(P182)2．不可分辨关系（不分明关系）3．上近似集和下近似集4．知识依赖度URX1C/2B+3A+4D/5A+6C+数据仓库与数据挖掘粗糙集概念的物理意义数据仓库与数据挖掘粗糙集理论的特点1．粗糙集理论的内涵知识是主体对论域中的客体进行分类的能力，分类能力越强，主体所具备知识的可靠性越高分类能力受主体分辨能力的影响，因此分类具有近似性影响分类能力的因素很多，不同的因素重要性不同，其中某些因素起着决定性作用具有相同属性的实体，属性取值的不同对分类能力也产生影响，属性之间存在着某种依赖关系数据仓库与数据挖掘粗糙集理论的特点2．与其它不确定理论的关系知识系统中的不确定性主要来自于3个方面：（1）认知对象间缺乏足够的区分度。（2）对象集合存在不确定性，这里集合的不确定性有两种解释。（3）不合适的知识表达粒度数据仓库与数据挖掘决策表达逻辑知识的简化（P189）简化核决策表（P190）当且仅当C→D，决策表T＝(U，A，C，D)是协调的。每个决策表T=(U,A,C,D)都可以唯一地分解成两个决策表一个是协调的T1=(U1,A,C,D)和另一个完全不协调的T2=(U2,A,C,D)Uacdeox101111x211010x310011x410010x510000x611011数据仓库与数据挖掘粗糙集的研究进展(P192)1．理论研究2．应用研究3．粒度研究具体地讲，凡是在分析问题和求解问题中,应用了分组、分类和聚类手段的一切理论与方法均属于粒度计算(GranularComputing,GrC)的范畴粒计算作为信息处理的一种新的概念和计算范式，覆盖了所有有关粒度的理论、方法、技术和工具的研究；这些理论都是从集会出发，采用不同的机制研究知识粒度的变换，它们之间并不是互相竞争的理论，而是互补的数据仓库与数据挖掘3.1.2.8

基于案例推理（P220）基于案例推理（Casw-BasedReasoning，CBR）是通过检查出案例库中过去同类的相似问题从而获得当前问题的解决方案。基本思想：基于人们在问题求解中习惯于过去处理类似问题的经验和获取的知识，再针对新旧情况的差异做相应的调整，从而得到新问题的解并形成新的案例。适用于没有很强的理论模型和领域知识不完全、难以定义、不良定义或定义不一致而经验丰富的决策环境中。数据仓库与数据挖掘CBR的逻辑学基础1．类比推理在人工智能中，如机器定理证明的归结原理，使用的是演绎推理，是从一般到特殊的推理过程，并未发现新的知识；反之，归纳推理则是从特殊到一般的推理过程，属于非标准逻辑，能根据某些已知的特殊性知识，归纳出未知的一般性知识。如果这些特殊性知识已经直接或间接包含了未知的一般性知识的所有可能情况，则归纳推理的结论完全有效，是完全归纳推理，仍然属于形式逻辑；否则结论可能有效，也可能无效，是不完全归纳推理。数据仓库与数据挖掘类比推理的基本结构就是： 物体A有属性a、b、c、d， 物体B有属性a、b、c； 所以类似地，B亦有属性d。类比有多种形式，如方法类比、概念类比、图形类比、联想类比等，都是人类思维的体现。类比推理给出的前提虽然指明了事物各种属性的共存，但是并没有确证这些属性之间有必然联系。CBR的逻辑学基础数据仓库与数据挖掘CBR的逻辑学基础2．非单调逻辑常识是人工智能研究的主要内容，因为机器智能必须处理常识和实现常识推理。然而常识并无明确的定义，而且有众多的例外。常识推理的基本特征是在知识不完全情况下进行的，要作出各种假设，具有非单调性。人类知识的增长实际上是非单调的发展过程，原因是人们推理时所依据的知识具有不完全性。假如把人们在不同认识阶段的知识用集合F表示，则是时间t的函数，F(t)表示人们再时刻t的知识总和，却不具备当t2>t1时F(t2)>F(t1)。然而，经典逻辑如形式逻辑、演绎逻辑等，对人类认知世界的处理却是单调的。数据仓库与数据挖掘1、CBR的工作过程CBR智能技术（P222）数据仓库与数据挖掘检索（Retrieve）：根据输入待解决的问题的有关信息，从案例库中检索相似的案例集；重用（Reuse）：从检索到的一组案例中获得求解方案，判别是否符合需求，若符合，则重用这些方案（或多个方案的合并解），否则需要修正；修正案例（Revise）：从相似案例中修正求解方案，使之适合于求解当前问题，得到当前问题的新求解方案；保存案例（Retain）：将新案例及其解根据一定的策略存入案例库中，此乃CBR的学习方式。CBR智能技术数据仓库与数据挖掘二、案例表示案例由诸多的属性组成，案例间相似性就是根据属性之间的相似度来定义的，目标案例和源案例的本质特征具有相似性关系使得类比有了基础。案例表示的研究，是整个CBR研究的基础和核心；案例的表示涉及到这样几个问题：选择什么信息存放在一个案例中、如何选择合适的案例内容描述结构、案例库如何组织和索引等1．案例表示的要求2．案例表示方法CBR智能技术数据仓库与数据挖掘三、CBR技术特点（P224）1．CBR的心理学模型：记忆推理2．CBR与思维模拟：直觉、逻辑、创造性思维的综合3．知识复用：结果的复用、方法的复用4．研究CBR技术的动机主要是克服在知识系统中的出现关键问题，如问题(1)克服理论不完善或信息缺失，(2)及时获取与更新知识，(3)对付计算复杂性问题，(4)辅助决策。5．增量式学习：增加知识库案例CBR智能技术数据仓库与数据挖掘1．案例相似性理论

(1)语义相似

(2)结构相似性

(3)目标特征

(4)个体相似性

2．相似性计算

(1)Tversky对比匹配函数

(2)改进的Tversky匹配法

(3)距离度量法或最近邻算法

(4)多参数的相似性计算

(5)Weber计算法相似性研究（P226）数据仓库与数据挖掘案例修正技术1．案例修正方法（P228）2．修正知识获取(1)利用领域知识来学习修正规则(2)交互式修正规则的学习，一般是从专家用户处学习修正知识(3)从案例库中学习修正规则，即利用机器学习技术从案例库中获取修正知识(4)从数据库中直接地发现修正知识(5)案例推理中基于案例库的修正学习技术(6)递归修正技术：它是根据案例之间的规律来递归求解的,根据用户需求来引导并发现出修正知识数据仓库与数据挖掘3.1.2.9遗传算法遗传算法（GeneticAlgorithms，GA）是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，大多数系统都遵循“适者生存”的仿自然法则。经过多年的发展，遗传算法取得了丰硕的应用成果和理论研究进展。数据仓库与数据挖掘3.1.2.9遗传算法求解此类问题的算法应该注意以下几点：不能简单地认为只要能产生适应环境的结构就好，还要保证求解问题的时间处于合理的范围；应该在保持穷举法的通用性的基础上提高效率；由于不了解环境，在算法中要有存储和利用实验结果，从中获取信息的手段。因而，Holland提出了模仿自然界的进化机制来解决适应性问题的优化算法——遗传算法。由于他提出的遗传算法简单实用，因而已普遍被接受采纳。数据仓库与数据挖掘遗传算法的主要特征（P230）图7-18是SGA（标准遗传算法）一种模式的工作流程图。由图可见，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。遗传算法的遗传操作（GeneticOperation）包括：选择（Selection）、交叉（Crossover）和变异（Mutation）三个主要的遗传算子，它们使得遗传算法具有了其它传统方法所没有的特性。遗传算法的核心内容是它的五个基本要素，它们是：参数编码；初始群体的设定；适应度函数的设计；遗传操作设计；控制参数设定。数据仓库与数据挖掘遗传算法求函数f(x)=x2+2的极值的计算过程数据仓库与数据挖掘遗传算法的基本原理（P234）1、模式定理(Schematatheorem)2、积木块假设3、欺骗问题4、隐并行性数据仓库与数据挖掘遗传算法的关键问题及方法一、编码（1）二进制编码（2）多字符及实数编码（3）树编码（4）自适应编码二、适应度函数1.适应度函数的设定2.适应度函数定标三、遗传操作1.选择算子2.交叉算子3.变异算子四、未成熟收敛问题数据仓库与数据挖掘挖掘关联规则的遗传算法（P241）（1）编码（2）适应度函数定义（3）选择操作（4）交叉操作（5）变异操作（6）规则评价和提取编号支持度可信度规

则

前

提规

则

结

果R10.2120.876日照量介于55到75小时降雨量介于0到30毫米R20.1540.857平均气温介于2.0到8.0摄氏度降雨量介于0到30毫米R30.1210.904日照量介于62到82小时降雨量介于0到30毫米数据仓库与数据挖掘3.1.2.10

模糊技术（P242）一、模糊知识模糊集理论用来最大限度地模拟人的思维及其推理功能，来研究描述一类信息不精确系统的知识模型。美国自动控制专业Zadeh提出模糊理论的出发点之一就是描述不确定性，如模糊性、随机性等。如果一个概念的外延边界是不清楚的，那么这个概念的外延边界是个模糊集合。如“青年”、“中年”，“老年”由于概念的外延的模糊而赞成的不确定性称为模糊型(Fuzziness)，在[0,1]上取值隶属函数就描述了这种模糊性。Zadeh认为：指明各个元素的隶属集合，就等于指定了一个集合；当属于0和1之间时值时，就是模糊集合。数据仓库与数据挖掘3.1.2.10

模糊技术二、模糊集合论（一）隶属度（P243）（二）模糊集合的表示（P244）数据仓库与数据挖掘模糊度及模糊关系一、模糊度（P247）是[0,1]空间上的隶属函数，表达模糊性的大小。取值0.5时模糊性最大。海明模糊度欧几里得模糊度明可夫斯基模糊度数据仓库与数据挖掘模糊度及模糊关系二、模糊关系（P247）模糊矩阵模糊关系三、模糊逻辑与模糊推理模糊命题模糊逻辑模糊推理数据仓库与数据挖掘3.2关联3.2.1基本概念3.2.2典型算法3.2.3算法实现

数据仓库与数据挖掘3.2.1基本概念关联自然界中某种事物发生时其他事物也会发生，则这种联系称之为关联。反映事件之间依赖或关联的知识称为关联型知识（又称依赖关系）。关联的类型分为简单关联、时序关联、因果关联。数据仓库与数据挖掘3.2.1基本概念关联规则关联是两个或多个变量取值之间存在的一类重要的可被发现的某种规律性。数据仓库与数据挖掘3.2.1基本概念关联规则的数学定义

先设I={i1,i2,...,im}是一个以m个不同项为元素的集合，T是针对I的交易的集合，每一笔交易包含若干个属于I的项。关联规则可表示为X=>Y，其中X,Y

I且X

Y=

X称为规则的前提或前项，Y称为结果或后项。每一规则有两个度量标准，即支持度(Support)和可信度(Confidence)

规则的支持度定义为:support(X=>Y)=support(XUY)

规则的可信度定义为:confidence(X=>Y)=support(XUY)/support(X)数据仓库与数据挖掘3.2.1基本概念关联规则的形式

R:X=>Y

其中，X及Y是两个不相交的集合，即X,Y

I且X

Y=

关联规则可以理解为一个命题，即如果一个交易支持项集X，则它也以一定的可能性支持项集Y，这一可能性称之为规则的可信度，记为conf(R)或C(R)数据仓库与数据挖掘3.2.1基本概念举例规则形式:Body®Head[support,confidence]buys(x,“diapers”)®buys(x,“beers”)[0.5%,60%]major(x,“CS”)^takes(x,“DB”)®grade(x,“A”)[1%,75%]数据仓库与数据挖掘3.2.1基本概念关联规则的性质

规则的非结合性规则的不可分解性规则的不可传递性规则的可扩展性数据仓库与数据挖掘关联规则挖掘实例

通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如，在同一次购物中，如果顾客购买牛奶的同时，也购买面包（和什么类型的面包）的可能性有多大？这种信息可以引导销售，可以帮助零售商有选择地经销和安排货架。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。数据仓库与数据挖掘关联规则挖掘实例购物篮关联分析实例图数据仓库与数据挖掘3.2.1基本概念CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer“啤酒与尿布”的关联规则数据仓库与数据挖掘

ForruleA

Csupport=support({A

C})=50%confidence=support({A

C})/support({A})=66.6%ForCA(50%,100%)TheAprioriprinciple:AnysubsetofafrequentitemsetmustbefrequentMin.support50%Min.confidence50%关联挖掘实例数据仓库与数据挖掘3.2.2典型算法典型算法

AIS算法（R.Agrawal等提出）

Apriori算法（及变种AprioriTid和AprioriHybrid)）

SETM算法（M.Houtsma等提出）

DHP算法（J.Park等提出）

PARTITION算法（A.Savasere等提出）

Sampling算法（H.Toivonen提出）

FP-growth算法（JiaweiHan提出）数据仓库与数据挖掘3.2.2典型算法AIS算法的主要思想其主要思想是一边扫描数据库，一边产生候选项集并累计支持度。具体地说，在对数据库进行第k次扫描时，候选项集是由第k-1次扫描所产生的边界集(frontierset)通过增加当前事务中的项得到，同时计算候选项集中元素的支持数，直到某次扫描所产生的边界集为空。缺点：生成的候选项集太大。数据仓库与数据挖掘3.2.2典型算法Apriori算法的主要思想该算法利用了频繁项集所具有的任意频繁项集的子集都是频繁项集的这一性质对数据库进行多次扫描:第一次扫描得到频繁项集的集合L0

，第k趟扫描前先利用上次扫描的结果项目集Lk-1,产生候选k项集的集合Ck

，然后再通过扫描数据库确定C中每一候选k项集的支持数，最后在该次扫描结束时求出频繁k项集的集合Lk

，算法的终止条件是Ck或Lk为空。

优点：所产生的候选项集比AIS算法少得多，效率较高。事实上，它被视为关联规则挖掘最经典的算法，其他很多算法都是其变种或改进。

数据仓库与数据挖掘3.2.2典型算法SETM算法的主要思想该算法实际也是AIS算法的变形。SETM把候选集的产生和累计分开，在一个线性存储结构里存储了所有候选集和相应的交易的标识符（TID）。每次扫描结束后，不再读取数据库，而是对TID进行排序并累计各个候选集的支持度。其思想是扫描候选集的编码（TID）来代替扫描数据库，实质上是把数据库中与支持有关的信息单独提取出来，构成一个较小但充分的TID库。这种做法大大减少了数据库访问的时间。缺点：候选项集过大。

数据仓库与数据挖掘3.2.2典型算法DHP算法的主要思想该算法利用散列表(hashtable)产生候选集，是对Apriori算法的直接改进。在遍历一次数据库得到候选k--项集的支持度，得到频繁k一项集后，DHP算法将每一个事务的可能的(k+1)--项集通过哈希规则形成散列表。散列表的每一栏包括所有通过散列规则映射到该栏中的项集的数目。根据结果的散列表，可以生成一个位向量，当散列表中对应的该栏中的数值大于或者等于最小支持时，对应的位置为1,否则为0。用该向量可以过滤掉下一次生成候选时所不必要的项集:如某候选项在向量中对应位的值为0，则舍弃。这对候选2--项集的产生尤为有效，可以在第二次就大大减小候选集的规模。数据仓库与数据挖掘DHP算法优点在某些场合，DHP算法的效率比Apriori算法明显提高。数据仓库与数据挖掘3.2.2典型算法PARTITION算法的主要思想该算法主要针对大型数据库，包括两部分：

(1)将目标数据库分为n个互不相交的子数据库D1，…，Dn，每个Di(i=1,2,⋯,n)的大小都要能容纳在内存中。然后把每个Di，读入内存并按一般算法发现频繁项集Li。再把所有的Li合并为数据库D的潜在频繁项集PL=UiLi;(2)计算潜在频繁项集PL在D中的支持度，得出频繁项集L。

数据仓库与数据挖掘3.2.2典型算法Sampling算法的主要思想对数据库D进行随机抽样得到抽样事务数据库D’，先以小于指定的支持度（minsup）挖掘D’中的频繁项集L’，再在剩余的数据集D-D’中继续计算L’中各元素的支持数，最后再以minsup求出L。这在大多数情况下就可以求得所有的频繁项集，但是有时会漏掉一些。这时可以对D进行二次扫描以发现漏掉的频繁项集。优点：多数情况下只需对数据库扫描一次，最坏情况下也只需扫描两次。

数据仓库与数据挖掘3.2.3算法实现Apriori算法的实现

（1）由候选项集(candidateitemset)产生频繁项集(frequentitemset)；（2）由频繁项集(frequentitemset)产生强关联规则(strongassociationrule)。数据仓库与数据挖掘3.2.3算法实现Apriori算法的基本流程

使用逐层搜索的迭代方法，通过对数据库的多次扫描发现所有的频繁项集。在每一趟扫描中只考虑具有同一长度k(即为项集中所含项目的个数)的所有项集。算法的第一次扫描仅仅计算每个项目的具体支持度，以确定长度为1的频繁项集。在后继的每一次扫描中，首先使用在前一次获得的频繁项集Lk-1和Apriori-gen函数产生的候选项集q，接着扫描数据库，计算Ck中候选项的支持度，最后确定候选项集中哪些真正成为频繁项集。重复上述过程直到再也发现不了新的频繁项集为止。数据仓库与数据挖掘DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanDApriori算法实例设定最小支持度阈值为2

数据仓库与数据挖掘交易号项集合T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3设定最小支持度阈值为2

数据仓库与数据挖掘扫描D，对每个候选项计数，生成C1：项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2数据仓库与数据挖掘比较候选项支持度计数与最小支持度计数，生成L1：项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2数据仓库与数据挖掘由L1产生候选集C2：

项集｛I1，I2｝｛I1，I3｝｛I1，I4｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝｛I3，I4｝｛I3，I5｝｛I4，I5｝数据仓库与数据挖掘再次扫描D，对每个候选项计数，产生L2：项集支持度计数｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2数据仓库与数据挖掘对L2进行连接&剪枝，产生C3，即最终结果。项集｛I1，I2，I3｝｛I1，I2，I5｝数据仓库与数据挖掘3.2.2典型算法Apriori算法的局限性由于依赖于候选项集产生频繁项集的理论（Apriori类算法）所开发的算法具有先天的弱点，使得在基于Apriori算法开发的应用没有实质性突破。Han等提出的一种新的算法理论，用一种压缩的数据结构(FP-tree)存储关联规则挖掘所需的全部数据信息，通过对源数据的两次扫描，将数据信息存到这种结构里，避开了产生候选项集的步骤，极大地减少了数据交换和频繁匹配的开销。这就是所谓无候选项集产生的算法(FrequentPatternsGrowth,FP-Growth)。数据仓库与数据挖掘3.2.3算法实现改进的算法——FP-growth(1)它构造了一种新颖的、紧凑的数据结构FP-tree。它是一种扩展的前缀树结构，存储了关于频繁模式数量的重要信息。(2)开发了基于FP-tree的模式片断成长算法，它从长度为1的频繁模式开始，只检查它的条件模式构建它的条件模式树，并且在这个树上递归地进行挖掘。模式的成长通过联合条件模式树新产生的后缀模式实现。(3)挖掘过程中采用的搜索技术是基于分区的，通过分割再解决的方法，而不是Apriori类算法的自下向上产生频繁模式的集合。数据仓库与数据挖掘3.2.2典型算法FP-growth算法的主要思想(P198)该算法主要是为了克服类Apriori算法的产生候选项集的缺点，通过采用一种新的数据结构FP-tree来达到目的。优点：只扫描数据库二次，并且不用产生候选项集，提高了效率。数据仓库与数据挖掘FP-growth算法实现交易编号所有购物项（排序后的）频繁项100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300b,f,h,j,of,b400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,p其中，最小支持度阈值为3数据仓库与数据挖掘FP-growth算法实现null{}b:1f:3c:1b:1p:1a:2b:1m:1f:2c:2a:3f:4c:3m:2p:23.f,b4.c,b,pf:1c:1m:1p:1a:11.f,c,a,m,p2.f,c,a,b,m5.f,c,a,m,pFP-growth算法树的构造

数据仓库与数据挖掘FP-growth算法实例生成的FP树

节点链性质对任意频繁项ai，顺着ai的节点链，从ai的头开始，可以找到包含ai的所有频繁模式。数据仓库与数据挖掘FP-growth与Apriori的比较DatasetT25I20D10K数据仓库与数据挖掘3.3聚类3.3.1定义3.3.2聚类算法

3.1.2.1聚类方法分类

3.1.2.2K均值算法

3.1.2.3K中心点算法

3.1.2.4C均值算法

数据仓库与数据挖掘3.3.1定义聚类分析从纷繁复杂的数据中，根据最大化类内相似性、最小化类间相似性的原则进行聚类或分组。即使得在一个簇内的对象具有高相似性，而不同簇间的对象具有低相似性的过程。数据仓库与数据挖掘3.3.2.1聚类方法分类基于划分的聚类方法基于层次的聚类方法基于密度的聚类方法基于网格的聚类方法基于模型的聚类方法

数据仓库与数据挖掘3.3.2.1聚类方法分类基于划分的聚类方法给定一个由n个对象组成的数据集合，对此数据集合构建k个划分，每个划分代表一个簇，即将数据集合分成多个簇的算法。要求：①每个簇至少有一个对象；②每个对象必须且仅属于一个簇。典型算法k-均值和k-中心点算法等。数据仓库与数据挖掘3.3.2.1聚类方法分类基于层次的聚类方法对给定的数据集合进行层层分解的聚类过程，具体地主要包括凝聚法和分裂法。凝聚法指起初每个对象被认为是一个簇，然后不断合并相似的簇，直到达到一个令人满意的终止条件；分裂法恰恰相反，先把所有的数据归于一个簇，然后不断分裂彼此相似度最小的数据集，使簇被分裂成更小的簇，直到达到一个令人满意的终止条件。根据簇间距离度量方法的不同，层次法可分为不同的种类。常用的距离度量方法包括：最小距离、最大距离、平均值距离和平均距离等。

典型算法：CURE、Chameleon和BIRCH等

数据仓库与数据挖掘基于层次的聚类方法这类方法不需要预先给定参数（聚类数），但需要终止条件。Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)数据仓库与数据挖掘CURE算法描述随机选取s个样本；将所有样本划分为p个簇，每个簇的样本数是s/p；

将每个簇划分为q个子集，每个子集样本数是s/pq

删除孤立点数据随机取如果一个簇变化缓慢，则删除该簇合并其中的部分子集

数据仓库与数据挖掘CURE算法－DataPartitioningandClusterings=50p=2s/p=25xxxyyyyxyxs/pq=5数据仓库与数据挖掘CURE算法－ShrinkingRepresentativePointsxyxyShrinkthemultiplerepresentativepointstowardsthegravitycenterbyafractionof

.Multiplerepresentativescapturetheshapeofthecluster数据仓库与数据挖掘CHAMELEON算法CHAMELEON算法是由G.Karypis,E.H.Han和V.Kumar在1999年提出的一种动态层次聚类方法。基于动态模型计算相似性只有当两个类之间的相似性高于类内对象的相似性时合并两个类。本质上，是一个两阶段算法1.首先，使用图分割算法将数据集合划分为多个子集；2.然后，使用层次聚类中的凝聚方法将这些子集进行反复的合并，直至获得最终的聚类结果。

数据仓库与数据挖掘CHAMELEON算法ConstructSparseGraphPartitiontheGraphMergePartitionFinalClustersDataSet数据仓库与数据挖掘3.3.2.1聚类方法分类基于密度的聚类方法这类算法的思想是，只要某簇邻近区域的密度超过设定的某一阈值，则扩大簇的范围，继续聚类。这类算法可以获得任意形状的簇。典型算法：DBSCAN、OPTICS和DENCLUE等数据仓库与数据挖掘3.3.2.1聚类方法分类基于网格的聚类方法基于网格的聚类算法首先将问题空间量化为有限数目的单元，形成一个空间网格结构，随后聚类在这些网格之间进行。这类算法速度较快。典型算法：STING、WareCluster和CLIQUE等

数据仓库与数据挖掘3.3.2.1聚类方法分类基于模型的聚类方法基于模型的聚类算法为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。所基于的假设是：数据是根据潜在的概率分布生成的。典型算法：COBWEB和神经网络算法等。数据仓库与数据挖掘3.3.2.1聚类方法分类上述方法属于传统聚类的范畴。一般地，传统聚类算法对于维度较低的数据集较有效，而当维度较高时，可能就不适合了。此外，大型数据库的聚类研究受到越来越多的重视。随着数据库技术的普及，积累了大量的数据信息，因此这一分支成为一个研究热点。

数据仓库与数据挖掘模式矩阵一般地，数据对象采用矢量表示法，即通过一个在多维空间中的矢量，来描述一个对象多方面的特征。矢量的每个维度描述对象的一个特征。多个对象的矢量构成一个模式矩阵（PatternMatrix），即（xij）mn

其中每行代表一个对象，每列描述一个特征。数据仓库与数据挖掘相似度在各种聚类算法中，通常是需要借助量化的指标以表征数据对象之间的特征差异和不同，称之为聚类统计量。聚类统计量包括：距离或相似度。数据仓库与数据挖掘标准化由于不同的特征采用不同的度量标准或尺度，这将对聚类结果产生不同的影响，为了消除这一差别，常进行标准化变换，使所有的特征能用一个共同的标准度量。数据仓库与数据挖掘距离的计算标准化处理后，计算对象间的距离最常用：欧氏距离，曼哈顿距离（又称绝对距离）、明考斯基（Minkovski）距离等方法。

数据仓库与数据挖掘相似度的计算n个对象彼此之间的相似性或近似性可通过相似（异）度矩阵（DissimilarityMatrix）表示。它是一个nm维、对角线元素为1的对称矩阵，即（rij）nm。其中，rij是i对象和j之间相似性的量化表示。通常其值是非负的。对象和关系越亲密，其绝对值越接近1；彼此关系越疏远，其值越接近于0。对象间相似度的计算方法包括：夹角余弦法、相关系数法及指数相似系数法等。

数据仓库与数据挖掘评价聚类方法的标准聚类分析是一种无监督的学习，事先对给定数据集合的结构一无所知，没有利用任何先验知识。无论采用哪种聚类算法，其聚类结果的合理性和有效性都有待评价。

聚类有效性对聚类分析具有重要意义，被认为是聚类分析的一个瓶颈。对于相同的数据集合，采用不同的聚类方法，可能得到不同的聚类结果。

即便是采用同一种聚类方法，若选择不同的初始参数（如聚类数、聚类中心等）也可能会得到不同的聚类结果。

数据仓库与数据挖掘例如，采用相同的k-均值聚类算法对同一个wine测试集进行聚类实验，当预设聚类类别数分别为1～8时，则所得到的聚类正确率是不同的，如柱状图所示。

数据仓库与数据挖掘评价聚类方法的标准可伸缩性即算法中模式数发生变化的情况。有些算法在模式数小的条件下，算法的性能很好，但是模式数增大后，算法性能下降。如PAM算法是一种k-中心点算法，它对小的数据集合非常有效，但对大的数据集合则没有良好的可伸缩性。高维性即算法中模式属性个数发生变化的情况。同样，有些算法只擅长处理低维数据。在高维空间中聚类是一个挑战，特别是数据有可能非常稀疏和偏斜。

数据仓库与数据挖掘评价聚类方法的标准发现任意形状的聚类一个簇可能是任意形状的，但一般的聚类算法是基于欧氏距离和曼哈顿距离度量实现聚类，更趋于发现球状簇。在这方面，基于密度的聚类方法较好。处理噪声数据的能力噪声数据可能是数据本身不完整，也可能是孤立点数据（Outlier）。有些算法不擅于处理孤立点数据，因此还专门出现了发现孤立点数据的算法。

数据仓库与数据挖掘评价聚类方法的标准用于决定输入参数的领域知识最小化和输入记录顺序敏感性一方面要求降低算法对输入参数的敏感程度，另一方面要求输入记录顺序对算法的结果影响小。如经典的k-均值算法，需要预先给出簇的数目。在一些知识发现应用中，这一参数非常影响聚类的质量。这常常是高效率算法的弱点。

数据仓库与数据挖掘评价聚类方法的标准可解释性和可用性知识发现过程中，聚类结果总是表现为一定的知识，这就要求聚类结果可解释、易理解。这与可视化密切相关，同时也与实际应用有关。如SOM（SelfOrganizationMapping）算法用于文本聚类可以产生知识地图，表现了良好的可视化性能。

数据仓库与数据挖掘3.3.2.2K均值算法K均值（k-means）是一种简便、实用的无监督聚类分析算法。这种算法在已知簇的个数时，可很好地实现数据的聚类分析。

基本思想（1）首先，随机选择k个数据点做为聚类中心；（2）然后，计算其它点到这些聚类中心点的距离，通过对簇中距离平均值的计算，不断改变这些聚类中心的位置，直到这些聚类中心不再变化为止。数据仓库与数据挖掘3.3.2.2K均值算法输入：n个数据的数据集合和已知的簇个数k输出：n个数据各属于k个簇中哪个簇的信息算法步骤：1）任意从n个数据中选择k个作为初始的簇中心；2）将剩余的n-k个数据按照一定的距离函数划分到最近的簇；3）repeat4）按一定的距离函数计算各个簇中数据的各属性平均值，作为新的簇中心；5）重新将n个数据按照一定的距离函数划分到最近的簇；6）until簇的中心不再变化。数据仓库与数据挖掘3.3.2.2K均值算法K均值的流程由流程图可知，k-均值算法是一种基于对数据集进行划分的方法进行聚类的算法。它是不断趋于最优解的试探过程。每一次迭代都试图使簇中心的选择更加接近于数据集的实际簇中心。输出N输入读入标准化归一化初始化簇计算簇平均值更改簇中心重新决定点归何簇Y簇中心是否变化数据仓库与数据挖掘3.3.2.2K均值算法K均值的实现过程数据仓库与数据挖掘3.3.2.2K均值算法优势（1）算法简单；（2）执行和收敛过程相对较快，是一种常见的聚类算法。局限性（1）必须事先知道聚类数；（2）算法要求簇是密集的、簇和簇之间的差异比较大；（3）数据集的平均值的计算必须有适当的定义；（4）不能用于非凸面的聚类；（5）对于某些孤立数据和“噪声”点敏感等。数据仓库与数据挖掘3.3.2.3K中心点算法k-中心点算法是对k-均值的改进主要的改进不采用簇中对象的平均值作为参照点，选用簇中位置最中心的对象，即中心点。这样的划分方法依然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。

数据仓库与数据挖掘3.3.2.3K中心点算法基本思想首先为每个簇随机的赋一个样本做中心点，将剩余的点依照距离的远近分配给最近的簇；随后用其它的非中心点数据做中心点，并查看聚类情况。如果替换的聚类总代价小于零，那么就执行替换直到中心点不再发生变化，也就是说达到代价最小值时停止算法。

数据仓库与数据挖掘3.3.2.3K中心点算法输入：簇的个数k，包含n个样本的数据集输出：各样本属于k个簇的信息算法步骤：1）随机选择k个样本作为初始中心点；2）repeat3）将非中心点的数据依照与各中心点的距离划分到最近的簇中；4）随机的在非中心点中选择一个样本；5）计算使用该点做中心点来代替原中心点的代价；6）if<0then用该点替换原中心点，形成新的簇集合7）until中心点不再发生变化数据仓库与数据挖掘3.3.2.4C均值算法1.选取聚类块数k2.从训练集中任意取定k个向量作为聚类中心3.将每个样本向量（n为输入向量维数），按下列欧氏距离归入中心为的类中。