聚类分类和关联.pdf

第 6 章 聚类﹑分类及关联算法 聚类﹑分类及关联算法是数据挖掘和知识发现的最主要算法。数据挖掘就是从大量的、 不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知 道的、但又是潜在有用的信息和知识的过程。数据挖掘所发现的知识（或模式）最常见的算 法有以下几类[7] ：概念描述、关联分析、分类、聚类分析、预测型知识和偏差型知识。 6.1 时间复杂度与空间复杂度 一般来说，解决同样的问题有多种算法，那么在不同的客观条件下如何对不同的算法进 行取舍呢？ 这就需要一种方法来对不同的算法来进行比较。 一. 算法的要求和目标： 算法设计的基本要求包括： 1)正确性(Correctness).2)可读性(Readablity).3)健壮性(Robustness) 4) 最小的代价. 正确性是指在理论上正确地反映了算法对应的原理，在实践上指出了一条可实现任务的 途径， 同时容易理解，编码和调试. 优秀的算法通常是简洁而清晰的，这样带来的直接好 处就是易于编码和理解，同时这样算法也必定是健壮的，如果一个算法晦涩难懂，则很可能 其中会隐藏较多的错误。 算法代价的最小化是指其执行时间最短且占用的存储空间最少，它们之间往往是相互矛 盾的，然而一般而言，算法的执行时间是主要的评价标准。 二. 算法的执行时间 算法的执行时间等于它所有基本操作执行时间之和，而一条基本操作的执行时间等于 它执行的次数和每一次执行的时间的积，表示为如下形式： 算法的执行时间＝操作 1＋操作2 ＋ ... + 操作 n 操作的执行时间＝操作执行次数×执行一次的时间 然而存在一个问题，不同的编程语言，不同的编译器，或不同的 CPU 等因素将导致执行一 次操作的时间各不相同，这样的结果会使算法的比较产生歧义，于是需要假定所有计算机执 行相同的一次基本操作所需时间相同，而把算法中基本操作所执行的最大次数作为量度。就 是说把算法的执行时间简单地用基本操作的执行次数来代替了。 另一方面，基本操作可以是基本运算，賦值，比较，交换等，例如在排序中，基本操 作指的是元素的比较及交换。而在线性查找中，它是数据的比较。 三. 时间复杂度表示方法 当问题规模即要处理的数据增长时，基本操作要重复执行的次数必定也会增长，那么必 须知道这个执行次数以什么样的数量级增长。所谓数量级可以理解为增长率。这个所谓的数 量级就称为算法的渐近时间复杂度(asymptotic time complexity)，简称为时间复杂度。由于基 本操作的执行次数是问题规模 n 的一个函数 T(n), 所以问题就是要确定这个函数 T(n)是什 么, 然后分析它的数量级, 拥有相同数量级的函数 f(n) 的集合表示为 O(f(n)) ，O 是数量级的 标记。如果 T(n) 的数量级和 f(n)相同，显然 T(n) ∈Of(n) 。这个函数的值表示当要处理的数据 量增长时，基本操作执行次数以什么样的比例增长。即 n 增长时，T(n)增长多少？特别地， 如果执行次数不能表示成为问题规模 n 的多项式函数，则称该问题是NP 难(NP-hard) 问题。 时间复杂度：算法中基本操作重复执行的次数是问题规模n 的某个函数 f(n)，T （n ）=O （f （n ））。它表示随问题规模n 的增大，算法执行时间的增长率和 f （n ）的增长率相同。通常 只要求出上界复杂度。 对于大规模的数据集，可以应用的计算复杂度往往是线性的或拟线性的，表示为 O(n)或 O(nlogn), 更高的计算复杂度通常是无法满足时实性的需求的。 1 四. 几个例子 例 1 冒泡排序. 假如有 10 个数，第一次循环比较 9 次，第二次循环比较 8 次，以此类推， 一共循环 9 次，那么总次数为 9 ＋8＋7 ＋6 ＋5＋4 ＋3 ＋2 ＋1 等于 45 次，则对于 N 个数来说， 总比较次数为 N(N-1)/2 次，可见得对于 N 个数来说，它的比较次数的数量级已达到 N 的 平方, 即 T=N(N-1)/2,