《2 聚类、分类、关联规则》由会员分享，可在线阅读，更多相关《2 聚类、分类、关联规则（72页珍藏版）》请在金锄头文库上搜索。
1、2012-1-12 1聚类分析的含义聚类分析的含义z 聚类（ Clustering）用于发现在数据库中未知的对象类z 聚类方法对象类划分的依据是 “物以类聚 ”，即考察个体或数据对象间的相似性z 在聚类之前，对象类划分的数量与类型均是未知的2012-1-12 2欧几里德距离欧几里德距离z 欧几里德距离（ Euclidean distance） 类似空间距离的计算。2222211i|),(xxxxxxjmimjijjid +=L,2,1;,2,1 njniLL2012-1-12 3分割聚类方法概述分割聚类方法概述z 分割聚类方法是一种基于原型（ Prototype）的聚类方法。z 其本质是首先从
2、数据集中随机地选择几个对象作为聚类的原型，然后将其它对象分别分配到由原型所代表的最相似、也就是距离最近的类中。z 分割聚类方法通过 迭代控制策略 对原型不断地进行调整，从而使得整个聚类得到优化。2012-1-12 4k-means算法的思路算法的思路z 1.首先 随机地选择 k个对象 代表 k个类，每一个对象作为一个类的原型，根据 距离原型最近 的原则将其它对象分配到各个类中。2012-1-12 5k-means算法的思路算法的思路z 2.以每一个类所有对象的 平均值（ mean）作为该类新的原型， 迭代 进行对象的再分配，直到没有变化为止，从而得到最终的个类。2012-1-12 6k-mea
3、ns算法步骤算法步骤1.首先随机地选择 k个对象，每一个对象作为一个类的 “中心 ”，分别代表将分成的 k个类。2.根据距离 “中心 ”最近的原则，寻找与各对象最为相似的类，将其它对象分配到各个相应的类中。2012-1-12 7k-means算法例算法例3283485664xi23217878675xi1x10x9x8x7x6x5x4x3x2x1xi1xi2x8x5x3x2x4x6x7x1x10x9聚类个数 k=2随机选择 x3,x6作为中心根据中心最近原则，将其他对象分配到相应类中2012-1-12 8k-means算法步骤算法步骤3. 在完成对象的分配之后，针对每一个类，计算其所有对象的平
4、均值，作为该类的新的 “中心 ”。4. 根据距离 “中心 ”最近的原则，重新进行所有对象到各个相应类的分配。5. 返回步骤（ 3），直到没有变化为止。2012-1-12 9k-means算法例算法例xi2x8x5x3x2x4x6x7x1x10x9xi1计算两个类的平均值分别为f1(1)、 f2(1)。f1(1)f2(1)根据距离 “中心 ”最近的原则，重新分配所有对象。2012-1-12 10k-means算法例算法例xi2x8x5x3x2x4x6x7x1x10x9xi1如此迭代计算，直至对象的分配不再发生变化，即可得到最终的聚类。f2(1)f2(2)2012-1-12 11层次聚类方法概述层
5、次聚类方法概述z 层次聚类方法（ Hierarchical Clustering Method）是采用 “自顶向下 （ Top-Down） ”或 “自底向上 （ Bottom-Up） ”的方法 在不同的层次上 对对象进行分组，形成一种树形的聚类结构。z 其包括分解型层次聚类法（自顶向下）和聚结型层次聚类法（自底向上）。2012-1-12 12层次聚类方法思想层次聚类方法思想z 层次聚类方法按照 一定的相似性判断标准 ，合并最相似的部分，或者分割最不相似的两个部分。z 如果合并最相似的部分，从每一个对象作为一个类开始， 逐层向上聚结 ，直到形成唯一的一个类 。z 如果分割最不相似的两个部分，从所
6、有的对象归属在唯一的一个类中开始， 逐层向下分解 ，直到每一个对象形成一个类。2012-1-12 13聚结层次聚类算法例聚结层次聚类算法例3283485664xi23217878675xi1x10x9x8x7x6x5x4x3x2x12012-1-12 14x1x2x3x4x6x7x5x10x9x8第一层x2x3x4x6第二层x7x5x10x9x8x1x1x1x2x3x4x6x7x5 x10x9x8x8x8第三层x2x3x4x6x7x5 x10x9第四层x1x2x3x4x6x7x5x10x9第五层第六层x8x1x2x3x4x6x7x5x10x9选择最相似、也就是 dmin最小的两个或多个类进行聚
7、结聚结层次聚类算法例聚结层次聚类算法例2012-1-12 15分类的目标分类的目标z 分类的目标是通过分析训练集中的数据，对类进行准确的描述或者建立模型，然后用它对数据库中的其它数据分类或者上升为分类规则。2012-1-12 16分类发现的处理过程分类发现的处理过程z 1. 分类模型的建立z 监督学习 (Supervised Learning)z 分类模型的建立是通过分析训练样本数据总结出一般性的分类规则，建立分类模型。z 分类模型以分类规则、决策树或数学公式的形式给出。z2012-1-12 17分类发现的处理过程训练集训练集分析分析分类器分类器建立的模型建立的模型矩形是黄矩形是黄圆形是红圆形
8、是红三角是绿三角是绿2012-1-12 18分类发现的处理过程z 2. 分类模型的应用z 在对建立的分类模型进行应用前，需要对建立的分类模型进行评估，在确保分类模型的准确性及精确度的情况下，才能运用该分类模型对未知其类别的数据样本进行分类处理。2012-1-12 19分类发现的含义数据库数据库分类器分类器红形红形黄形黄形绿形绿形已建立的模型已建立的模型没有分辨颜的形没有分辨颜的形2012-1-12 20分类发现的主要方法分类发现的主要方法z 1. 基于决策树模型的数据分类z ID3算法z 2. 基于统计模型的数据分类z 贝叶斯分类z 3. 基于神经网络的数据分类2012-1-12 21决策树生
9、成过程决策树生成过程z 1. 用户根据实际需求以及所处理数据的特性，选择 类别标识属性 和决策树的 决策属性集 。2012-1-12 22决策树生成过程例决策树生成过程例320高直销电力薄板华中2000年80中直销电力薄板华中2000年600低分销电力线材华东2000年50低直销电力线材华南2000年300中分销机电圆钢华中2000年510高直销冶金管材华东2000年200高直销冶金薄板华中2000年行数利润销售渠道客户行业销售产品销售地区销售时间选择类别标示属性选择类别标示属性选择决策属性集选择决策属性集2012-1-12 23决策树生成过程决策树生成过程z 2. 在决策属性集中选择 最有分
10、类标识能力的属性 作为决策树的当前决策节点。z 3. 根据当前决策节点属性取值的不同，将训练样本数据集划分为若干子集。How？2012-1-12 24决策树生成过程例决策树生成过程例320高直销电力薄板华中2000年80中直销电力薄板华中2000年600低分销电力线材华东2000年50低直销电力线材华南2000年300中分销机电圆钢华中2000年510高直销冶金管材华东2000年200高直销冶金薄板华中2000年行数利润销售渠道客户行业销售产品销售地区销售时间选择根节点（选择根节点（最有分类标识能力的属性）将训练样本数据集划分为若干子集根据销售渠道的取值，将训练集分为两个子集直销 和 分销20
11、12-1-12 25决策树生成过程例决策树生成过程例销售渠道销售渠道直销直销分销分销可得：可得：2012-1-12 26决策树生成过程决策树生成过程z 4. 针对上一步中得到的每一个子集，重复进行上述的 2、 3两个步骤，直到最后的子集符合结束的 三个条件之一 。2012-1-12 27三个条件三个条件z 1. 子集中的所有元组都属于同一类；z 2. 该子集是遍历了所有决策属性得到的；z 3. 子集中的所有剩余决策属性取值完全相同，已不能根据这些决策属性进一步进行子集划分。2012-1-12 28决策树生成过程决策树生成过程z 5. 根据符合条件的不同，生成叶子节点。z 对满足 “条件一 ”所
12、产生的叶子节点，直接根据该子集的元组所属类别进行类别标识。z 满足步骤 “条件二 ”或 “条件三 ”所产生的叶子节点，选取子集所含元组的代表性类别特征进行类别标识。2012-1-12 29决策树生成过程例决策树生成过程例在在“销售渠道销售渠道”为为“分销分销”的分枝中进行的分枝中进行同样的属性选择处理同样的属性选择处理600低分销电力线材华东2000年300中分销机电圆钢华中2000年行数利润销售渠道客户行业销售产品销售地区销售时间2012-1-12 30决策树生成过程例决策树生成过程例在在“销售渠道销售渠道”为为“直销直销”的分枝中进行的分枝中进行同样的属性选择处理同样的属性选择处理320高
13、直销电力薄板华中2000年80中直销电力薄板华中2000年50低直销电力线材华南2000年510高直销冶金管材华东2000年200高直销冶金薄板华中2000年行数利润销售渠道客户行业销售产品销售地区销售时间对于对于“客户行业客户行业”为为“冶金冶金”的数据集来说，的数据集来说，均属于均属于“利润利润”为为“高高”的类，故该分枝终的类，故该分枝终止进一步划分。（第一个条件）止进一步划分。（第一个条件）“客户行业客户行业”为为“电力电力”，“销售地区销售地区”为为“华中华中”这一分枝中，类别标识属性有两个不同的取这一分枝中，类别标识属性有两个不同的取值。值。但已经没有可以继续分解的决策属性了但已经
14、没有可以继续分解的决策属性了。（第三种情况）。（第三种情况）选择具有最大可能的类别标识属性值选择具有最大可能的类别标识属性值“高高”作为其类别标识属性作为其类别标识属性2012-1-12 31决策树生成过程例决策树生成过程例直销直销 分销分销华中华中 华东华东电力电力冶金冶金由此可得：由此可得：销售地区销售地区华中华中华南华南低低中中低低高高高高销售地区销售地区客户行业客户行业销售渠道销售渠道2012-1-12 32决策树剪枝决策树剪枝z 有决策树得到的初步规则中，有一些预测规则准确性较低，因此需要对上述得到的决策树进一步处理，这个进一步处理的过程由 “剪枝 ” 过程完成。2012-1-12
15、33决策树剪枝决策树剪枝z 主要是采用新的样本数据集（称为 测试数据集 ）中的数据检验决策树生成过程中产生的初步规则，将那些影响预测准确性的分枝剪除。2012-1-12 34测试数据集测试数据集略320高直销电力华中略300中分销机电华中150中直销电力华南50低直销电力华南这些元组符合： “销售渠道 ”为 “直销 ”， “行业 ”为 “电力 ”， “地区 ”为 “华南 ”的分枝 （第二组）20高直销电力华南390高直销冶金华东20低直销冶金华中50中直销冶金华中这些元组符合： “销售渠道 ”为 “直销 ”， “客户行业 ”为 “冶金 ”的分枝（第一组）320高直销冶金华中说明行数利润销售渠道客户行业销售地区2012-1-12 35第一组测试数据第一组测试数据390高直销冶金华东20低直销冶金华中50中直销冶金华中320高直销冶金华中行数利润销售渠道客户行业销售地区直销直销 分销分销华中华中 华东华东冶金冶金 电力电力销售地区销售地区华中华中华南华南低低中中低低高高高高销售地区销售地区客户行业客户行业销售渠道销售渠道其准确率为其准确率为(320+390)/(320+50+2
