下面先对数据进行[0,1]规格化，下表是规格化后的数据
•
接着用k-means算法进行 聚类。设k=3，即将这15 支球队分成三个集团。现 抽取日本、巴林和泰国的 值作为三个簇的种子，即 初始化三个簇的中心为A： {0.3, 0, 0.19}，B：{0.7, 0.76, 0.5}和C：{1, 1, 0.5} 下面，计算所有球队分别 对三个中心点的相异度， 这里以欧氏距离度量。下 面是用程序求取的结果：
log2 ( p) log 2 (n)
C4.5定义
C4.5定义
实例
• 假设有一个信息系 统，关于的是几种 天气的不同变化对 是否进行比赛的影 响．根据这些信息， 给定一个决策表如 右图：
NO. 1 Outlook sunny Temperature hot Windy false Humidity high Play? No
C4.5总结
• C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算 法进行了改进： • 1) 用信息增益率来选择属性，克服了用信息增益选择属性 时偏向选择取值多的属性的不足； • 2) 在树构造过程中进行剪枝； • 3) 能够完成对连续属性的离散化处理； • 4) 能够对不完整数据进行处理。 • C4.5算法有如下优点：产生的分类规则易于理解，准确率 较高。其缺点是：在构造树的过程中，需要对数据集进行 多次的顺序扫描和排序，因而导致算法的低效。此外， C4.5只适合于能够驻留于内存的数据集，当训练集大得无 法在内存容纳时程序无法运行。
2
3 4 5 6 7 8 9 10 11 12 13 14
sunny
overcast rain rain rain overcast sunny sunny rain sunny overcast overcast rain
hot
hot Mild（温暖） cool cool cool mild cool mild mild mild hot mild
聚类图形化表示如图：
K次平均算法
• K-means算法的基本思想是：给定一个包含n个数据对象 的数据库，以及要生成簇的数目k，随机选取k个对象作为 初始的k个聚类中心；然后计算剩余各个样本到每一个聚 类中心的距离，把该样本归到离它最近的那个聚类中心所 在的类，对调整后的新类使用平均值的方法计算新的聚类 中心；如果相邻两次的聚类中心没有任何变化，说明样本 调整结束且聚类平均误差准则函数已经收敛。本算法在每 次迭代中都要考察每个样本的分类是否正确，若不正确， 就要调整。在全部样本调整完成后修改聚类中心，进入下 一次迭代。如果在一次迭代算法中，所有的样本被正确分 类，则不会有调整，聚类中心不会有变化。在算法迭代中 值在不断减小，最终收敛至一个固定的值。该准则也是衡 量算法是否正确的依据之一。
true
false false false true true false false false true true false true
high
high high normal normal normal high normal normal normal high normal high
No
Yes Yes Yes No Yes No Yes Yes Yes Ye是给定一个元素集合D，其中 每个元素具有n个可观察属性，使用某种算法将D 划分成k个子集，要求每个子集内部的元素之间相 异度尽可能低，而不同子集的元素相异度尽可能 高。其中每个子集叫做一个簇 。
• 与分类不同，分类是示例式学习，要求分类前明 确各个类别，并断言每个元素映射到一个类别。 而聚类是观察式学习，在聚类前可以不知道类别 甚至不给定类别数量，是无监督学习的一种。
K-Means步骤
• 假设要把样本集分为c个类别，算法描述如下： • （1）适当选择c个类的初始中心； • （2）在第k次迭代中，对任意一个样本，求其到c 个中心的距离，将该样本归到距离最短的中心所 在的类； • （3）利用均值等方法更新该类的中心值； • （4）对于所有的c个聚类中心，如果利用（2） （3）的迭代法更新后，值保持不变，则迭代结束， 否则继续迭代。 • 该算法的最大优势在于简洁和快速。算法的关键 在于初始中心的选择和距离公式。
实例：中国男足
• 下面，我们来看看k-means算法一个有趣的应用 示例：中国男足近几年到底在亚洲处于几流水平？ 下页的图是亚洲15只球队在2005年-2010年间大 型杯赛的战绩 • 其中包括两次世界杯和一次亚洲杯。我提前对数 据做了如下预处理：对于世界杯，进入决赛圈则 取其最终排名，没有进入决赛圈的，打入预选赛 十强赛赋予40，预选赛小组未出线的赋予50。对 于亚洲杯，前四名取其排名，八强赋予5，十六强 赋予9，预选赛没出现的赋予17。这样做是为了 使得所有数据变为标量，便于后续聚类。
• 熵的概念源自热物理学.假定有两种气体a、b，当 两种气体完全混合时，可以达到热物理学中的稳 定状态，此时熵最高。如果要实现反向过程，即 将a、b完全分离，在封闭的系统中是没有可能的。 只有外部干预（信息），也即系统外部加入某种 有序化的东西（能量），使得a、b分离。这时， 系统进入另一种稳定状态，此时，信息熵最低。 热物理学证明，在一个封闭的系统中，熵总是增 大，直至最大。若使系统的熵减少（使系统更加 有序化），必须有外部能量的干预。
• 下面根据第一次聚类结果，调整各个簇的中心点。 • A簇的新中心点为：{(0.3+0+0.24+0.3)/4=0.21, (0+0.15+0.76+0.76)/4=0.4175, (0.19+0.13+0.25+0.06)/4=0.1575} = {0.21, 0.4175, 0.1575}（取簇中所有元素各自维度的算术平均数。） • 用同样的方法计算得到B和C簇的新中心点分别为 {0.7, 0.7333, 0.4167}，{1, 0.94, 0.40625}。
树的修剪
• 树一旦生成后，便进入第二阶段——修剪阶段。决策树为什么要剪枝？ 原因就是避免决策树“过拟合”样本。前面的算法生成的决策树非常 的详细而庞大，每个属性都被详细地加以考虑，决策树的树叶节点所 覆盖的训练样本都是“纯”的。因此用这个决策树来对训练样本进行 分类的话，你会发现对于训练样本而言，这个树表现堪称完美，它可 以100%完美正确得对训练样本集中的样本进行分类（因为决策树本 身就是100%完美拟合训练样本的产物）。但是，这会带来一个问题， 如果训练样本中包含了一些错误，按照前面的算法，这些错误也会 100%一点不留得被决策树学习了，这就是“过拟合”。C4.5的缔造 者昆兰教授很早就发现了这个问题，他做过一个试验，在某一个数据 集中，过拟合的决策树的错误率比一个经过简化了的决策树的错误率 要高。 • 目前决策树的修剪的策略有三种：基于代价复杂度的修剪（CostComplexity Pruning）、悲观修剪（Pessimistic Pruning）和MDL （Minimum Description Length）修剪。对于树的修剪，相对树的生 成要简单一些 ，时间关系， 具体就不讲了，有兴趣下来讨论。
树的终止
• 树的建立实际上是一个递归过程，那么这 个递归什么时候到达终止条件退出递归呢？ 有两种方式，第一种方式是如果某一节点 的分支所覆盖的样本都属于同一类的时候， 那么递归就可以终止，该分支就会产生一 个叶子节点。还有一种方式就是，如果某 一分支覆盖的样本的个数如果小于一个阈 值，那么也可产生叶子节点，从而终止建 立树。我们只考虑二叉分割的情况，因为 这样生成的树的准确度更高。
算法二：K-Means
• 挖掘主题：聚类 • k-means算法是一个聚类算法，把n个对象 根据他们的属性分为k个分割(k < n)。它与 处理混合正态分布的最大期望算法很相似， 因为他们都试图找到数据中自然聚类的中 心。它假设对象属性来自于空间向量，并 且目标是使各个群组内部的均方误差总和 最小。
• 用调整后的中心点再 次进行聚类，得到： • 第二次迭代后的结果 为： • 中国C，日本A，韩国 A，伊朗A，沙特A， 伊拉克C，卡塔尔C， 阿联酋C，乌兹别克斯 坦B，泰国C，越南C， 阿曼C，巴林B，朝鲜 B，印尼C。
• 结果无变化，说明结果已收敛，于是给出最终聚类结果： 亚洲一流：日本，韩国，伊朗，沙特 亚洲二流：乌兹别克斯坦，巴林，朝鲜 亚洲三流：中国，伊拉克，卡塔尔，阿联酋，泰国，越南， 阿曼，印尼 • 看来数据告诉我们，说国足近几年处在亚洲三流水平真的 是没有冤枉他们，至少从国际杯赛战绩是这样的。 • 其实上面的分析数据不仅告诉了我们聚类信息，还提供了 一些其它有趣的信息，例如从中可以定量分析出各个球队 之间的差距，例如，在亚洲一流队伍中，日本与沙特水平 最接近，而伊朗则相距他们较远，这也和近几年伊朗没落 的实际相符。
• 也就是说，熵是描述系统混乱的量，熵越 大说明系统越混乱，携带的信息就越少， 熵越小说明系统越有序，携带的信息越多。
C4.5具体算法步骤
1、创建节点N 2、如果训练集为空，在返回节点N标记为Failure 3、如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N 4、如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类； 5、for each 候选属性 attribute_list 6、if 候选属性是连续的then 7、对该属性进行离散化 8、选择候选属性attribute_list中具有最高信息增益的属性D 9、标记节点N为属性D 10、for each 属性D的一致值d 11、由节点N长出一个条件为D=d的分支 12、设s是训练集中D=d的训练样本的集合 13、if s为空 14、加上一个树叶，标记为训练集中最普通的类 15、else加上一个有C4.5（R - {D},C，s）返回的点
Humidity high high high normal
Play? No No No Yes
11