第 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 冒泡排序. 假如有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, 则说它的比较操作的时间复杂度为 O(n 2) (n 的平方)。
例2 数组的线性查找 很显然，在最坏的情况下，10个数要比较10次，那么对于N 个数来
说，要比较N 次，平均 N/2次，即T = N/2, 它的数量级是一次的，所以说这个线性查找的
时间复杂度是线性的，即 O(n).
例3. 交换i 和j 的内容。
temp=i ; i=j ; j =temp;
以上三条语句的频度均为1，该程序的执行时间是与问题规模n 无关的常数，因此算法的时
间复杂度为常数阶，记作T （n ）=O （1）。
例4 求两个n 阶方阵的乘积C=A×B ，其算法如下：
#define n 100
void MatrixMultiply(int A[n][n],int B[n][n],int C[n][n]){ int i,j,k
for (i=1;i<=n;++i) /* 次数 n+1 */
for (j=1;j<=n;++j) /* 次数 n*(n+1)*/
{ C[i][j]=0; /* 次数 n 2 */
for (k =1;k<=n,k++) /* 次数 n 2(n+1) */ C[i][j]=C[i][j]+A[i][k]*B[k][j];/* 次数 n 3 */}}
所以， T(n)=2n 3+3n 2+2n+1 和T(n)=O(n 3)。
常见的时间复杂度，按数量级递增排列依次为：常数阶O(1),对数阶0(Log 2n),线性阶
O(n)，线性对数阶0(nLog 2n)，平方阶O(n 2)，立方阶0(n 3)，指数阶O(2n )。通常认为，具有
指数阶量级的算法是实际不可计算的，而量级低于平方阶的算法.
总之，算法分析不是要求出一个算法的真实执行时间,而是比较算法执行的相对运算时
间，是对算法对内存,带宽等等基本资源消耗情况的分析。怎样比较算法的相对执行时间. 设
想提出一个理想的统一的计算机模型，算法运行在这种理想计算机上。 算法的计算时间通
常是我们关注的重点,也就是算法的时间复杂度分析. 算法分析的目的是在多个算法中选择
一个满足要求的算法.算法分析目的就是分析和比较算法的优劣.
表格 6.1 算法的相对执行时间
五. 算法存储空间的度量 程序所需要的空间主要由以下部分构成：
? 指令空间（instruction space ）指令空间是指用来存储经过编译之后的程序指令所需的空间。
? 数据空间（data space ） 数据空间是指用来存储所有常量和所有变量值所需的空间。数据
空间由两个部分构成：
1) 存储常量和简单变量所需要的空间。
2) 存储复合变量所需要的空间。这一类空间包括数据结构所需的空间及动态分配的空间。
? 环境栈空间（environment stack space ） 环境栈用来保存函数调用返回时恢复运行所需要
的信息。例如，如果函数fun1调用了函数fun2，那么至少必须保存fun2结束时fun1将要
继续执行的指令的地址。
一个程序所需要的空间可以分成两部分：
? 固定部分，它独立于实例的特征。一般来说，这一部分包含指令空间（即代码空间）、简
单变量及定长复合变量所占用空间、常量所占用空间等等。
? 可变部分，它由以下部分构成：复合变量所需的空间（这些变量的大小依赖于所解决的
具体问题），动态分配的空间（这种空间一般都依赖于实例的特征），以及递归栈所需的空间
（该空间也依赖于实例的特征）。
算法存储空间度量的基本做法 用程序执行中需要的辅助空间的消耗作为存储空间度量
的依据，是问题规模n 的函数。而程序执行中本身需要的工作单元不能算。 因此，算法空
间复杂度 S(n)=O (f(n)) 称为算法的空间复杂度。
对一个程序的空间复杂性感兴趣的主要原因如下：
? 如果程序将要运行在一个多用户计算机系统中，可能需要指明分配给该程序的内存大小。
? 对任何一个计算机系统，想提前知道是否有足够可用的内存来运行该程序。
? 一个问题可能有若干个内存需求各不相同的解决方案。比如，对于你的计算机来说，某个
C ++ 编译器仅需要1MB 的空间，而另一个C ++ 编译器可能需要4MB 的空间。如果你的计
算机中内存少于4MB ，你只能选择1MB 的编译器。如果较小编译器的性能比得上较大的
编译器，即使用户的计算机中有额外的内存，也宁愿使用较小的编译器。
? 可以利用空间复杂性来估算一个程序所能解决的问题的最大规模。
例7，有一个电路模拟程序，用它模拟一个有c 个元件、w 个连线的电路需要2 8 0 K + 1 0 *
（c+w ）字节的内存。如果可利用的内存总量为6 4 0 K 字节，那么最大可以模拟c+w ≤3 6 K
的电路。
6.2. 距离函数
距离测度函数和各种类型相似性查询的定义.
定义3 所谓量度空间的距离函数)0)(,(≥y x d 是如下定义的:
1) ),(),(x y d y x d =(对称性);
2) ),(y x d (相似性)
3) ),(),(),(z y d z x d y x d +≤(三角不等式)
为计算任意两个对象距离的相似性，选择相似性(不相似性测度)测度度量成为必要前提；
1）向量间距离函数：
距离的度量方法可采用欧几里德距离和Mahalanobis 距离度量方法分别被定义为：
2/1))()((),(y x C y x y x d T ??=
(1)C 是一个正定矩阵，当C=I 时，2/1))
)(((),(y x y x y x d ??=。距离是一种统计特征度量)它与特征向量的概率分布状态有关；上述距离的更加一般形式是加权p l 距离， ∑=??=k i p p t y x C y x y x d 1/1)|)()((|),(
(2)
Hamming 距离
2）度量字符串之间的Tanimoto 测度，即 Y X Y X Y X Y X Y
X n n n n n n y x d U I U I ?+==),( (3)
Hausdorff 距离是描述两组点集之间相似程度的一种量度，它是两个点集之间距离的一种定
义形式：假设有两组集合1A {,}p a a =K ，1{,}q B b b =K 则这两个点集合之上的Hausdorff
距离定义为：
(,)max((,),(,))H A B h A B h B A =
(4)其中, (,maxmin b B a A h A B a b ∈∈=?），(,maxmin a A b B h B A b a ∈∈=?），* 是点集A 和点集B 间的距离范式(如:2L 或Euclidean 距离). 这里，式(1)称为双向Hausdorff 距离，是Hausdorff 距离
的最基本形式；而h(A,B) 和h(B,A)分别称为从A 集合到B 集合和从B 集合到A 集合的单
向Hausdorff 距离。即：h(A,B)实际上首先对点集A 中的每个点i a 到距离此点i a 距离最近
的B 集中的点j b 之间的距离j i a b ? 进行排序，取这样的距离中的最大值作为h (A,B)
的值。h (B,A)同理可得。
由式(1)知，双向Hausdorff 距离H(A,B)是单向距离h(A,B)和h(B,A)两者中的较大者，它
度量了两个点集间的最大不匹配程度。考虑到由式(1)定义的基本形式的Hausdorff 距离易受
突发噪声的影响，或待识别物体本身只是部分可见，此时若使用基本形式的Hausdorff 距离
必将使计算结果产生较大的偏差，进而影响整体匹配识别结果，故有partial distance 的定义:
)),(),,(max(),(A B h B A h B A H k L LK =
(5)其中，||||min ),(||,||min ),(a b L B A h b a K A B h B b th A a L A a th B b k ?=?=∈∈∈∈，这里，th B b K ∈
表示从B 集合到A 集合的排序后的距离值集合中的第K 个值， th
A a L ∈ 表示从A 集合到B
集合的排序后的距离值集合中的第L 个值。
例6 使用Hausdroff 距离做手势识别 这篇文章所建系统采用修正的Hausdorff 距离(MHD ，
Modified Hausdorff Distance)来进行模板匹配，其定义如下：
1(,)min A b B
a A h A B a
b N ∈∈=?∑ 其中，A N 是点集A 中的点个数。
修正的Hausdorff 距离(MHD)对噪声不太敏感，可避免由于部分噪声像素点的干扰带
来的偏差。该系统在系统实施中，分别利用基本形式的Hausdorff 距离与修正的Hausdorff
距离这两种思想来进行匹配识别，以证明修正的Hausdorff 距离思想的优越性。
Hausdorff 距离技术对于像素点位置的波动性较二值化相关技术( binary correlation
techniques )有更好的鲁棒性，因为前者是测量一种相似程度，而不要求测试样本与模板像素
点之间具有一一对应关系，即不需在匹配前进行规整。而且，同大多数形状比较方法(shape
comparison methods)不同，而且，Hausdorff 距离的计算并不基于相应数据集合上的明确的
点对(explicit pairing of points)之间的距离计算。另外，Hausdorff 距离模板匹配的方法不需要
进行复杂的光流计算或图象分割匹配。正是由于上述优良特性，它多被用来实现对一般目标
物体的识别，对运动物体的跟踪检测等。
3）概率测度的度量与模糊测度：见数据融合一章数据关联部分。
4）基于熵的两个随机变量的概率数之间的度量，对于两个离散随机变量X 和Y ，如果要对
它们之间的相似程度进行度量，可以使用Shannon 信息论中的互信息函数，定义如下 )),(),,(max(),(X Y h Y X h Y X H k L LK =
(6)
分别是X 和Y 的边缘概率分布；),(y x p XY 是X 和Y 的联合概率分布，),(log ),(),(,y x p y x p Y X H XY y x XY 2∑?=表示随机变量的Shannon 熵。互信息给出了两个
随机变量X 和Y 相互包含对方的信息量，即两个随机变量中所包含的共有信息。如果X ，Y 相
互独立，则互信息值为零；反之其值越大，表明两个变量之间的相似性程度越高。在图像处
理宗，常常用互信息所表示两幅图像所包含的共同信息，当互信息最大时，表示两幅图像实
现了配准。
5）基于内积构造的函数之间的距离函数 在内积空间中，><=b a x ,||，因此，可以得到一个广泛的定义内积空间的距离的方
法. 例如我们定义内积空间p p b a
g f g f /1))((,∫?>=<，则相应的距离函数位 p p b a g f g f /1))((,∫?>=< (7)
6）不一致数据的度量
很多情况下，由于种种原因如测量条件的改变，操作的失误等，数据的维度往往是不一
致和不完整的，为此需要采用特殊的度量方式，如下面所示的部分距离。让 “?” 表示数据
中遗失的特征值，则两个点之间的部分距离如下：
})84()51{()35(5||)98765(?)4??1(||||||222222?+??=?=?=T T i j ij v x D (8)
一般的，对于一条保留j I 个非遗失的特征的数据j x r
和一条保留i I 个非遗失的特征的数据i x r 之间的部分距离定义为 ∑=?=c I m im jm c ij x x I d
D 122|||| (9)
这里d I I j i ≤≤, c I m ,...,2,1= 向量j x r 和i x r 之间公共的未遗失的特征向量.
6.3. 数据压缩-矢量量化的基本原理
学习矢量量化（LVQ —Learning Vector Quantization ）是70年代后期发展起来的一种数
据压缩技术基本思想：将若干个标量数据组构成一个矢量，然后在矢量空间给以整体量化，
从而压缩了数据而不损失多少信息矢量量化编码也是在图像、语音信号编码技术中研究得较
多的新型量化编码方法，它的出现并不仅仅是作为量化器设计而提出的，更多的是将它作为
压缩编码方法来研究的。在传统的预测和变换编码中，首先将信号经某种映射变换变成一个
数的序列，然后对其一个一个地进行标量量化编码。而在矢量量化编码中，则是把输入数据
几个一组地分成许多组，成组地量化编码，即将这些数看成一个k 维矢量，然后以矢量为单
位逐个矢量进行量化。矢量量化是一种限失真编码，其原理仍可用信息论中的率失真函数理
论来分析。而率失真理论指出，即使对无记忆信源，矢量量化编码也总是优于标量量化。
在矢量量化编码中，关键是码本的建立和码字搜索算法。 相关的概念如下。
定义: 矢量量化是把一个k 维输入矢量K R X X ?∈~映射为另一个K 维量化矢量N Y Y ~∈，
即)(X Q Y =，这里X ~表示输入矢量构成的信源空间；Y 是量化矢量即码字；Y ~
是码字的
空间即码书；)(?Q 表示量化器。
码本的生成算法有两种类型，一种是已知信源分布特性的设计算法；另一种是未知信源
分布，但已知信源的一列具有代表性且足够长的样点集合（即训练序列）的设计算法。可以
证明，当信源是矢量平衡且遍历时，若训练序列充分长则两种算法是等价的。
码字搜索是矢量量化中的一个最基本问题，矢量量化过程本身实际上就是一个搜索过
程，即搜索出与输入最为匹配的码矢。矢量量化中最常用的搜索方法是全搜索算法和树搜索
算法。全搜索算法与码本生成算法是基本相同的，在给定速率下其复杂度随矢量维数K 以
指数形式增长，全搜索矢量量化器性能好但设备较复杂。树搜索算法又有二叉树和多叉树之
分，它们的原理是相同的，但后者的计算量和存储量都比前者大，性能比前者好。树搜索的
过程是逐步求近似的过程，中间的码字是起指引路线的作用，其复杂度比全搜索算法显著减
少，搜索速度较快。由于树搜索并不是从整个码本中寻找最小失真的码字，因此它的量化器
并不是最佳的，其量化信噪比低于全搜索。
矢量量化经典算法－LBG 算法基本步骤:
将N·Ｋ个信号取样值组成的信源序列｛x i ｝中每K 个为一组分为N 个K 维随机矢量，
构成信源空间T ＝｛X 1，X 2，…，X N ｝（X 在K 维欧几里德空间R K 中），其中第j 个矢量可
记为X j =｛x j,1，x j,2，…，x j,k ｝，j=1,2,…N 。再把R K 无遗漏地划分成J ＝2n 个互不相交的子空
间R １，R ２，…，R j 。在每一个子空间R i 中找一个代表矢量c i ，令恢复矢量集C ＝｛c １，c ２，…c
Ｊ｝,C 称为码本或码书（Codebook ）
，c i 称为码矢(Code Vector)或码字(Code Ｗord)，C 内矢量的数目J ，称为码本长度。矢量量化过程就是把一个K 维模拟矢量X 映射为另一个K 维
量化矢量，其数学表示式为：c i ＝Q （X j ），式中Q 为量化函数。
在VQ 中，码本的生成是一个关键，它要根据失真最小的原则，分别决定如何对R K 进
行划分以得到合适的J 个分块，以及如何从每个分块（Ｒi ）中选出它们各自合适的代表矢
量c i 。LBG 算法是一种递归算法，可根据给定的训练序列，经过多次递归运算，求出满足
要求的码本。训练序列是从具体的应用场合中选取典型图像，从这些图像中取出的图像子块
序列。在用LBG 算法进行VQ 设计时，初始码本的确定很重要，本程序中采用分裂法来确
定初始码本Ｃ(0)。分裂法的思想是：先用一个初始码字(等于全部训练序列T 的平均值)来初
始化初始码本，然后把这个初始码字分裂为2个码字，根据失真最小的原则，进行迭代比较，
当满足条件时退出迭代过程，更新码字；接着把2个码字分裂为4个码字，同样根据失真最
小原则，进行迭代比较，当满足条件时退出迭代过程，更新码字。如此不断分裂、迭代比较，
直到码字个数达到要求为此。算法的设计步骤如下：
(１) 给出训练序列Ｔ＝｛X 1，X 2，…，X N ｝以及失真控制门限ε（0＜ε＜1);
(2) 置M=1, 求初始码字N X C n
m m /1*1∑==，计算初始平均失真； 3）分裂：for i=1,2,…,M, 置M=2M, 找出训练序列T 的最小失真分割，即
*)0(*)1(;)1(i i M i o i c c c c εε?=+=+
4) 迭代。①找出训练序列T 的最小失真分割；②for n=1～M ，求出各分割的算术平均值或
几何中心；③取i=i+1; ④计算平均失真: ⑤重复第3和第4步，直到码字个数达到要求为止。
6.4. 多维数据可视化技术
数据挖掘可视化是将数据信息以某种图形图像可视化的形式呈现出来，给观察者提供
一种量化的方式，来理解嵌入在数据中的隐藏信息。这些隐藏信息通常是异常信息和模式信
息。异常信息是指用户观察到了意想不到的图形图像分布信息，通常由异常的数据现象或者
数据特征引起。模式信息是由反映数据现象和数据特征规律的规则的图形图像信息。而多维
数据可视化是数据挖掘可视化的一个重要方向。对它进行研究，主要分为三类问题：几何问
题（数据信息的表示方法），认知问题（人们对数据表示方法的认知能力），评价问题（可视
化系统表示数据信息的有效性）。认知问题和评价问题涉及到医学和神经学等主观方面的知
识，本文暂且不讨论。对于几何问题，重要的不是计算机技术，而是如何将数据中隐藏的复
杂的数据关系信息映射到人们能够理解的图形图像的能力。
人类的认知系统可以识别空间三维物体，对于抽象的物体或者像素的识别很困难。空间
的可视性最多能够达到四维（例如第四维为时间维）。目前对于构成可视化的方法中的主要
方法，有以下几个方面。
1）空间三维图形：不同的图形元素的组合的变换映射为不同的数据维解释。把一个可
视化空间结构和一条数据信息对应起来。通过图形的密度和颜色的分布，大致能够了解数据
的分布、数据之间的相似性和数据之间的关系。
2）颜色图：分为彩色图和灰度图。彩色图的每一种颜色，对应着不同的属性维，灰度
图可以利用颜色的深浅来标记数据量的属性值的大小，颜色越深，数值越大或者用它来强调
某种特别的信息，它通常预先需要很好的映射定义。
3）亮度：对于特定的区域，用不同的亮度来辅助人眼对视点的观察。
4）数学的方法：利用数学中统计的方法，先对数据关系进行分析，得到数据的大体分
布信息，然后再结合其它的可视化方法来进行细节数据分析。或者利用数学中统计的方法对
数据中的关系进行映射，映射成为图形图像关系来帮助分析。
下面列举几个目前主要的多维数据可视化技术
图3 展开图
6.4.1几何图技术
1）星型图[6]：是一种简单的几何多维数据可视化技术。每个星型标记的构造方法如下：任选空间的某一点作为一个星型标记的中心点，由中心点作出n条线段来代表n个数据维，这n个线段把平面平均分成n份。一般地，每一个线段长度代表一个数据维的值的大小（或者名词性属性，由用户自己定义各自的长度）。把一个星型标记线段的终点全部用直线连接起来，就构成了一个星型图(图4)。每一个星型图都代表数据库中一条记录，这样一组数据就用一组星型来代表。
图4 星型图
2）平行坐标图平行坐标图是一个最早出现但是迄今仍然使用的可视化方法。它的基本思想是将n维数据空间用n条等距离的平行轴映射到二维平面上，每条轴线都对应于一个属性维。把每条记录对应的点用一条折线连接起来。如图是一个三维数据集的平行坐标图。原则上平行坐标图可以适用于任意维度数据集的可视化。
维度1 维度2 维度3
图2. 多维数据集的平行坐标可视化
3）图标技术[4]：用户可以自己定义的一些图标，来代表多维数据。利用图标类型的不同特征来映射原来数据的性质。它的主要思想是把多维数据集合中的每一条记录转化为一个图标，可视化的特征元素在对应映射的数据的操控之下，可以看到数据的大概分布特征。设计一种特别的可视化几何结构来对应于一种特殊的数据结构，可以辅助分析特殊的数据，再综合颜色和亮度，就可以能够反映出对应的多维结构的内部特征（图5）。
图5 对应于数据集中数据记录的图标
像缝衣针图标技术。Chernoff Faces[9]技术也是一种著名的可视化多维数据的图标方法。人的每一个面部特征都代表一个特别的数据维，n个数据维中的第一个数据维可以和人脸上的嘴的大小相关联，n个数据维中第二个数据维和鼻子的大小相关联，n个数据维中的第三个数据维和眼睛的大小相关，等等。这种技术高度浓缩了数据，而且用一种有趣的方式反映了大量数据表的特征。缺点是cheroff face的面部特征与数据集中的数据维对应顺序依赖关系很强，如果数据维和面部特征对应顺序改变，那么反映的数据关系也改变了。
4）catterplot Matrix[5]
Scatter plot是显示多个数据维中任意两个数据维之间的依赖关系的矩阵图，分别把多维数据中的每一个维数对称地标注在横轴和纵轴上，把它们在数据集中每一对出现的频度作为关系依赖的评价，这样每两维的关系被显示在这个平面网格图中(图3)。在Scatter plot的matrix n 维矩阵中，scatterplots会产生n*(n-1)/2对维之间的关系。这些维的名字被写在矩阵的主对角线上，它的主要优点是很容易解释所有的维之间的关系而不受数据集大小和维数多少的影响；缺点是当维数增加的时候，矩阵要受到屏幕大小的限制，而且只能够发现两个维之间的关系，不能发现多个数据维之间的关系。
6.4.2 Harrarchy 技术
1）Stacked 技术[1]：堆显示技术可以把数据分层显示。核心思想是把一个坐标系统嵌入到另外一个坐标系统中。首先选出一个多维数据集属性中的两个属性来构建一个平面坐标系，在这个坐标系中，利用不同的坐标值把空间分成不同的矩形表格，在这些表格中，再选择剩余属性中的两个属性来构建第二层坐标系，依照此方法做下去。对于多维数据的情况，数据维数被用来分割数据和建立分层，层次的选择是值得考虑的。它的典型应用有World- within –worlds 系统。这种技术适合比较密集的数据集，在稀松的数据集上用的较少。这主要是因为对于每一个可能的数据点都对应于屏幕上的空间，而且随着数据维数的增加，屏幕空间也随着增大。对于分层技术主要的问题是很难判断空间关系，对于非临近数据维，两个数据点本来关系很近，但是在屏幕上的位置却十分远。如果能够提供用户减少嵌套的特性和离散化维数的方法，可视化效果可以提高。
6.4.3 降维技术
对于大量的数据，有时发现它的内部特征是很难的，只有通过降维技术来获得数据的总体结构特征，进而再利用其它的可视化技术来分析数据。
1) 自组织特征映射网络SOM算法[11]
该算法的核心思想是把多维向量通过竞争学习网络，将多维数据点映射到低维网格平面上的一个点。该部分详细内容在神经网络一章介绍。
2)volume rendering[15] 体素化的可视化方法，主要用等值面，多用于医学方面。利用数据预处理的手段，把数据进行分层分组，利用每一组的权值，来作为颜色灰度的决定值，再利用其它的可视化手段来进行显示。一般来说，三维空间数据场是连续的，而数值计算结果或测量所得数据则是离散的，是对连续的三维场进行采样的结果。体绘制技术就是要将这一种三维空间样本直接转换为屏幕上的二维图象，尽可能准确地重现原始的三维数据场。屏幕上的
二维图象决定于桢缓存中对应与每一个象素点的光亮度值，这也是一个二维的离散数据场。因此，体绘制技术的实质是将离散的三维空间数据场转化为离散的二维数据。
总之，一个多维数据可视化过程包括翻译数据阶段（在完全改变某个事物之前），数据显示阶段。数据翻译阶段就是将数据库集中的数据对应于可视化的元素，每一个可视化的元素都是一种可视化特征。这些可视化的物体，可能是线、点、抛物线、图、2D或者3D表面、3D固体、图像文本。对于每一个可视化的物体，我们可以选择颜色、位置、形状、风格、文本、大小、宽度、长短、深度、方向取向、相关位置等可视化特征，还有一些动态特征，采用数学方法来对数据来进行分析。我们经常需要利用不同方法来组合产生一种新的可视化多维数据的方法。
6.4.4 OPTICS：排序对象识别聚类结构
尽管DBSCAN（8.6.1节中描述的基于密度的聚类算法）能根据给定输入参数ε和MinPts 对对象进行聚类，它仍然将选择能产生可接受的聚类结果的参数值的责任留给了用户。事实上，这也是许多其他聚类算法存在的问题。对于真实的，高维的数据集合而言，参数的设置通常是依靠经验，难以确定。绝大多数算法对参数值是非常敏感的：设置的细微不同可能导致差别很大的聚类结果。而且，真实的高维数据集合经常分布不均，全局密度参数不能刻画其内在的聚类结构。
为了解决这个难题，提出了OPTICS聚类分析方法（Ordering Points to Identify the Clustering Structure）。OPTICS没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个簇次序（cluster ordering ）。这个次序代表了数据的基于密度的聚类结构。它包含了信息，等同于从一个广域的参数设置所获得的基于密度的聚类。
考察DBSCAN，我们可以看到，对一个恒定的MinPts值，关于高密度的（即较小的ε值）的聚类结果被完全包含在根据较低密度所获得的密度相连的集合中。记住参数ε是距离，它是邻域的半径。因此，为了生成基于密度聚类的集合或次序，我们可以扩展DBSCAN算法来同时处理一组距离参数值。为了同时构建不同的聚类，对象应当以特定的顺序来处理。这个次序选择根据最小的ε值密度可达的对象，以便高密度的聚类能被首先完成。基于这个想法，每个对象需要存储两个值——核心距离（core-distance）和可达距离（reachability-distance）：
一个对象p的核心距离是使得p成为核心对象的最小ε。如果p不是核心对象，p的核心距离没有定义。
一个对象q关于另一个对象p的可达距离是p的核心距离和p与q的欧几里得距离之间的较大值。如果p不是一个核心对象，p和q之间的可达距离没有定义。
例8.3图8a描述了核心距离和可达距离的概念。假设ε=6，MinPts=5。p的核心距离是p 与第四个最近的数据对象之间的距离ε’。q1关于p的可达距离是p的核心距离（即ε’=3mm），因为它比从p到q1的欧几里得距离要大。q2关于p的可达距离是从p到q2的欧几里得距离，它大于p的核心距离。图8b显示了一个含有五个类的数据集它的排序图，每一个凹陷对应一个类。
(a) (b)
图6. OPTICS的定义和可视化应用
OPTICS 算法创建了数据库中对象的一个次序，额外存储了每个对象的核心距离和一个
适当的可达距离。一种算法被提出基于OPTICS 产生的次序信息来抽取聚类。这样的信息对
于关于小于在生成该次序中采用的距离ε的任何距离ε’的基于密度的聚类都是足够的。
一个数据集合的聚类次序可以被图形化地描述，以有助于它的理解。例如，图6a 是一
个简单的二维数据集合的可达性图表，它给出了数据如何被聚类的概述。也有在多个层次上
观察高维数据的聚类结构的方法被研究。由于OPTICS 算法与DBSCAN 在结构上的等价性，
OPTICS 算法具有和DBSCAN 相同的时间复杂度，即当空间索引被采用，复杂度为O （nlongn ）
6.5. 聚类算法
6.5.1 概述
传统的聚类算法按照不同的标准可以作不同的划分，如表格2所示。
表格2 传统的聚类算法的分类 按照目标函数
按照聚类过程 按照模式归属关系 按照构成类的单元 有目标函数
划分式 硬聚类算法 基于密度划分 无目标函数 分级(层)式 软(模糊)聚类算法 基于网格划分
带有目标的聚类算法往往把聚类转化为一个经典的目标函数的优化问题，从而有许多成熟的
优化技术可以作为其优化工具。另一方面，必然也受到目前优化技术局限性的限制，如局部
最小问题，初始化问题等。
以下着重介绍这些算法中最典型的四类：划分算法、层次算法、基于密度的算法、基于
网格的算法和基于模型的算法。
(1)划分聚类算法是将数据集分成若干子集。即给定一个例子的集合X,其中包括n个数据对
象，并要生成数目为k的簇，需要同时满足如下的要求:
① 每个组至少包括一个对象;
② 每个对象必须属于且只属于一个组，但是在模糊划分技术中第二个要求可以放宽。如果
给定要构建的划分数目k，划分方法是由一个初始划分开始，通过优化一个评价函数把数据
划分成若干子类，因此事实上已经把聚类问题转化成了优化问题，划分聚类方法输出的是多
个互不相交的聚类集。常用的基于划分的聚类方法有k一均值(k-means)法和k一中心法
(k-medoids), CLARA法和CLARANS法等。
(2)层次聚类方法是把对给定的数据集按层次进行分解，结果是形成一棵以数据子集为节点
的类别树。根据层次分解的方式不同，其又可以分为凝聚的层次方法和分裂的层次方法，凝
聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后相继地合并
相近的对象或组，直到所有的组合并为一个层次的最上层，或者达到一个终止条件;分裂的
方法，也称为自顶向下的方法，一开始将所有的对象置于一个类中，在迭代的每一步中，一
个类被分裂为更小的类，直到最终每个对象在单独的一个类中，或者达到一个终止条件。层
次的方法的缺陷在于:一旦一个步骤(合并或者分裂)完成，它就不能被撤消，这个严格规定
是有用的，由于不用担心组合数日的不同选择，计算代价会较小，但是该技术的一个主要问
题是它不能更正错误的决定。现在比较常用的层次聚类方法有BIRCH法，CURE法等。层次聚
类算法产生一个嵌套聚类的层次。更具体的说，这些算法包含N步，与数据向量的数量一样
多。在第t步，要在前t-1步的聚类基础上生成新的聚类。在合并算法中，初始的聚类0Ψ由
N个聚类组成，每个聚类仅包含X中的一个元素，第一步生成聚类1ψ，它包含N-1个集合，如
果10ψψ?。重复此过程直到产生最有一个聚类1?N ψ
，它只包含一个单个的聚类集合，即
数据集0X ，因而得到聚类的层次为
110...????N ψψψ
分裂算法与合并算法的思路恰恰相反。在这种算法中，初始聚类0ψ仅包含一个集合X 。第
一步产生聚类1ψ，它由2ψ集合组成，如果01ψψ?。重复此过程直到产生最后一个聚类
1?N ψ，它包含N个集合，每个集合仅包含X中一个元素，在这种情况下可得
110...????N ψψψ
通用的合并算法
1. 初始化：
1.1 选择},...,2,1},{{0N i x C i i ===ψ；
1.2 令0=t ；
2. 重复执行下列步骤：
2.1 1+=t t ；
2.2 在1?t ψ的所有可能聚类对)},{(s r C C 中找一组),(s r C C ，满足
),(min ),(,s r s r s r C C g C C g =
2.3 定义j i q C C C ∪=，并产生新聚类}},{{
1q j i t t C C C ∪?=?ψψ。 3. 直到所有向量全被加入到单一聚类。
基本地，数据挖掘对聚类的典型要求如下：
可伸缩性：许多聚类算法在小于200个数据对象的小数据集合上工作得很好；但是，一
个大规模数据库可能包含几百万个对象，在这样的大数据集合样本上进行聚类可能会导
致有偏的结果。我们需要具有高度可伸缩性的聚类算法。
处理不同类型属性的能力：许多算法被设计用来聚类数值类型的数据。但是，应用可能
要求聚类其他类型的数据，如二元类型(binary)，分类/标称类型（categorical/nominal ），
序数型（ordinal ）数据，或者这些数据类型的混合。
发现任意形状的聚类：许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基
于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是，一个簇可能
是任意形状的。提出能发现任意形状簇的算法是很重要的。
用于决定输入参数的领域知识最小化：许多聚类算法在聚类分析中要求用户输入一定的
参数，例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定，
特别是对于包含高维对象的数据集来说。这样使得聚类的质量难以控制。
处理“噪声”数据的能力：绝大多数现实中的数据库都包含了孤立点，缺失，或者错误的
数据。一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。
对于输入记录的顺序不敏感：一些聚类算法对于输入数据的顺序是敏感的。例如，同一
个数据集合，当以不同的顺序交给同一个算法时，可能生成差别很大的聚类结果。开发
对数据输入顺序不敏感的算法具有重要的意义。
高维度（high dimensionality ）：一个数据库或者数据仓库可能包含若干维或者属性。许
多聚类算法擅长处理低维的数据，可能只涉及两到三维。人类的眼睛在最多三维的情况
下能够很好地判断聚类的质量。在高维空间中聚类数据对象是非常有挑战性的，特别是
考虑到这样的数据可能分布非常稀疏，而且高度偏斜。
基于约束的聚类：现实世界的应用可能需要在各种约束条件下进行聚类。假设你的工作
是在一个城市中为给定数目的自动提款机选择安放位置，为了作出决定，你可以对住宅
区进行聚类，同时考虑如城市的河流和公路网，每个地区的客户要求等情况。要找到既
满足特定的约束，又具有良好聚类特性的数据分组是一项具有挑战性的任务。
可解释性和可用性：用户希望聚类结果是可解释的，可理解的，和可用的。也就是说，
聚类可能需要和特定的语义解释和应用相联系。应用目标如何影响聚类方法的选择也是
一个重要的研究课题。
随着数据仓库和数据挖掘技术的日益发展，数据挖掘技术目前数据挖掘领域研究方向主
要集中在以下几点：
1) 处理不同类型数据
绝大多数数据库是关系型的，因此在关系数据库上有效地执行数据挖掘是至关重要的。但是在不同应用领域中存在着各种数据和数据库，而且经常包含复杂的数据类型，例如结构数据、复杂对象、事务数据、历史数据等。由于数据类型的多样性和不同的数据挖掘目标，一个数据挖掘系统不可能处理各种数据。因此针对特定的数据类型，需要建立特定的数据挖掘系统。
2) 数据快照和时间戳
现实数据库通常是庞大、动态、不完全、不准确、冗余和稀疏的，这给知识发现系统提出了许多难题。数据库中数据的不断变化造成先前发现的知识很快过时，利用数据快照和时间戳方法可解决这一问题。前者特别适用于阶段性搜索集的数据，但需要额外空间存储快照。数据的不准确性使知识挖掘过程需要更强的领域知识和更多的抽样数据，同时导致发现结果的不正确；不完全数据包括缺少单个记录的属性值或缺少关系的字段；重复出现的信息称为冗余信息，为避免将对用户毫无意义的函数发现作为知识发现的结果，系统必须了解数据库的固有依赖。另外数据的稀疏性和不断增加的数据量增加了知识发现的难度。
3) 数据挖掘算法的有效性和可测性
海量数据库通常有上百个属性和表及数百万个元组。GB量级数据库已不鲜见，TB量级数据库已经出现，高维大型数据库不仅增大了搜索空间，也增加了发现错误模式的可能性。因此必须利用领域知识降低维数，除去无关数据，从而提高算法效率。从一个大型数据库中抽取知识的算法必须高效、可测量，即数据挖掘算法的运行时间必须可预测，且可接受，指数和多项式复杂性的算法不具有实用价值。但当算法用有限数据为特定模型寻找适当参数时，有时会导致物超所值，降低效率[19]。
4) 交互性用户界面
数据挖掘的结果应准确地描述数据挖掘的要求，并易于表达。从不同的角度考察发现的知识，并以不同形式表示，用高层次语言和图形界面表示数据挖掘要求和结果。目前许多知识发现系统和工具都缺乏与用户的交互，难以有效利用领域知识，对此可以利用贝叶斯方法和数据库本身的演绎能力发现知识。
5) 在多抽象层上交互式挖掘知识
很难预测从数据库中会挖掘出什么样的知识，因此一个高层次的数据挖掘查询应作为进一步探查的线索。交互式挖掘时用户能交互地定义一个数据挖掘要求，深化数据挖掘过程，从不同角度灵活看待多抽象层上的数据挖掘结果。
6) 从不同数据源挖掘信息
局域网、广域网及Internet网将多个数据源联成一个大型分布、异构的数据库，从包含不同语义的格式化和非格式化数据中挖掘知识是对数据挖掘的一个挑战。数据挖掘可以揭示大型异构数据库中存在的普通查询不能发现的知识。数据库的巨大规模、广泛分布及数据挖掘方法的计算复杂性，要求建立并行分布的数据挖掘[20]。
7) 私有性和安全性
数据挖掘能从不同角度、不同抽象层上看待数据，将影响到数据挖掘的私有性和安全性。通过研究数据挖掘导致的数据非法侵入，可改进数据库安全方法，以避免信息泄漏。
8) 和其他系统的集成
方法功能单一的发现系统的适用范围必然受到一定的限制。要在更广泛的领域发现知识，系统就应该是数据库、知识库、专家系统、决策支持系统、可视化工具、网络等技术的集成。
9) Internet上的知识发现
从WWW信息的海洋中可以发现大量的新知识，已有资源发现工具发现含有关键值的文本。Han 等人提出利用多层次结构化方法，通过对原始数据的一般化，构造多层次的数据库
6.5.2 带有目标函数的聚类算法
为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多数应用采用了以下两个比较流行的启发式方法：（1）k-means算法，在该算法中，每个簇用该
簇中对象的平均值来表示。（2）k-medoids算法，在该算法中，每个簇用接近聚类中心的一个对象来表示。这些启发式聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。
给定一个包含n个数据对象的数据库，以及要生成的簇的数目k，一个划分类的算法将数据对象组织为k个划分（k≤n），其中每个划分代表一个簇。通常会采用一个划分准则（经常称为相似度函数，similarity function），例如距离，以便在同一个簇中的对象是“相似的”，而不同簇中的对象是“相异的”。
算法：k-means。
输入：簇的数目k和包含n个对象的数据库。
输出：k个簇，使平方误差最小。
方法：
（1）任意选择k个对象作为初始的簇中心；
（2）repeat
（3）根据与每个中心的距离，将每个对象赋给“最近”的簇；
（4）重新计算每个簇的平均值；
（5）until 不再发生变化
k-means方法有很多变种。它们可能在初始k个平均值的选择，相异度的计算，计算聚类平均值的策略上有所不同。经常会产生较好的聚类结果的一个有趣策略是首先采用层次的自底向上算法决定结果簇的数目，及找到初始的簇，然后用迭代的重定位来改进聚类结果。
k-means方法的一个变体是k-medoids 方法 . k-medoids聚类算法的基本策略是：首先为每个簇随意选择选择一个代表对象；剩余的对象根据其与代表对象的距离分配给最近的一个簇。然后反复地用非代表对象来替代代表对象，以改进聚类的质量。聚类结果的质量用一个代价函数来估算，该函数评估了对象与其参照对象之间的平均相异度。为了判定一个非代表对象O random 是否是当前一个代表对象O j的好的替代，对于每一个非代表对象p，下面的四种情况被考虑：
第一种情况：p当前隶属于代表对象O j。如果O j被O random所代替，且p离O I最近，i≠j，那么p被重新分配给O I。
第二种情况：p当前隶属于代表对象O j。如果O j 被O random代替，且p离O random最近，那么p被重新分配给O random。
第三种情况：p当前隶属于O I ，i≠j。如果O j被O random代替，而p仍然离O I最近，那么对象的隶属不发生变化。
第四种情况：p当前隶属于O I，i≠j。如果O j被O random代替，且p离O random最近，那么p被重新分配给O random。
当存在“噪音”和孤立点数据时，k-medoids方法比k-means方法更健壮，这是因为medoid 不象平均值那么容易被极端数据影响。但是，k-medoids方法的执行代价比k-means算法高。此外这两种方法都要求用户指定结果簇的数目k。
算法：k-medoids，
输入：结果簇的数目k，包含n个对象的数据库
输出：k个簇，使得所有对象与其最近代表对象的相异度总和最小。
履行方法：
（1）随机选择k个对象作为初始的代表对象；
（2）repeat
（3）指派每个剩余的对象给离它最近的代表对象所代表的簇；
（4）随意地选择一个非代表对象O random；
（5）计算用O random代替O j的总代价S；
（6）如果S<0，则用O random替换O j，形成新的k个代表对象的集合；
（7）until 不发生变化
---------------------------------------------------------------------
典型的k-medoids算法，如PAM，对小的数据集合非常有效，但对大的数据集合没有良好的可伸缩性。
6.5.2 基于密度的方法DBSCAN
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个基于密度的聚类算法。该算法将具有足够高密度的区域划分为簇，并可以在带有“噪音”的空间数据库中发现任意形状的聚类。它定义簇为密度相连的点的最大集合。
基于密度的聚类的基本想法涉及一些新的定义。我们先给出这些定义，然后用一个例子加以说明。
一个给定对象周围半径ε内的区域称为该对象的ε –邻域。
如果一个对象的ε–邻域至少包含最小数目MinPts的对象，那么该对象称为核心对象。 给定一个对象集合D，如果p是在q的ε–邻域内，而q是一个核心对象，我们说对象p 从对象q出发是直接密度可达的，。
如果存在一个对象链p1,p2,…,p n，p1=q，p n=p，对p i D
∈，1≤i≤n，p i+1是从p i关于ε和 MinPts 直接密度可达的，则对象p是从对象q关于ε和MinPts密度可达的(density-reachable)。 如果对象集合D中存在一个对象o，使得对象p和q是从o关于ε和MinPts密度可达的，那么对象p和q是关于ε和MinPts密度相连的（density-connected）。
密度可达性是直接密度可达性的传递闭包，这种关系是非对称的。只有核心对象之间是相互密度可达的。不过，密度相连性是一个对称的关系。
“DBSCAN如何进行聚类？”DBSCAN通过检查数据库中每个点的ε-邻域来寻找聚类。如果一个点p的ε-邻域包含多于MinPts个点，则创建一个以p作为核心对象的新簇。DBSCAN 然后反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及几个密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。
如果采用空间索引，DBSCAN的计算复杂度是O（nlogn），这里n是数据库中对象的数目。否则，计算复杂度是O（n2）。该算法对用户定义的参数是敏感的，DBSCAN在下面的章节中会进一步的讨论，同时将与另一个基于密度的聚类算法OPTICS进行比较。
6.5.2 基于网格的方法
基于网格的聚类方法采用一个多分辨率的网格数据结构。它将空间量化为有限数目的单元，这些单元形成了网格结构，所有的聚类操作都在网格上进行。这种方法的主要优点是处理速度快，其处理时间独立于数据对象的数目，仅依赖于量化空间中每一维上的单元数目。
基于网格方法的有代表性的例子包括STING，它利用了存储在网格单元中的统计信息；WaveCluster，它用一种小波转换方法来聚类对象；CLIQUE，它是在高维数据空间中基于网格和密度的聚类方法。
8.7.3 CLIQUE：聚类高维空间
CLIQUE（Clustering In QUEst）聚类算法综合了基于密度和基于网格的聚类方法。它对于大型数据库中的高维数据的聚类非常有效。CLIQUE的核心想法：
给定一个多维数据点的大集合，数据点在数据空间中通常不是均衡分布的。CLIQUE区分空间中稀疏的和拥挤的区域，以发现数据集合的全局分布模式。
如果一个单元中的包含的数据点超过了某个输入参数，则该单元是密集的。在CLIQUE
中，相连的密集单元的最大集合定义为簇。
“CLIQUE 如何工作？”CLIQUE 分两步进行多维聚类：
第一步，CLIQUE 将n 维数据空间划分为互不相交的长方形单元，识别其中的密集单元。该
工作对每一维进行。例如，图8.17显示了关于age 和salary ，vocation 维的密集的长方形单
元。代表这些密集单元的相交子空间形成了一个候选搜索空间，其中可能存在更高维度的密
集单元。 “为什么CLIQUE 将更高维密集单元的搜索限制在子空间密集单元的交集中？”
这种候选搜索空间的确定采用基于关联规则挖掘中的先验特性（apriori property ）。一般来说，
该特性在搜索空间中利用数据项的先验知识以裁减空间。CLIQUE 所采用的特性如下：如果
一个k 维单元是密集的，那么它在k-1维空间上的投影也是密集的。也就是说，给定一个k
维的候选密集单元，如果我们检查它的k-1维投影单元，发现任何一个不是密集的，那么我
们知道第k 维的单元也不可能是密集的。因此，我们可以从（k-1）维空间中发现的密集单
元来推断k 维空间中潜在的或候选的密集单元。通常，最终的结果空间比初始空间要小很多。
然后对检查密集单元决定聚类。
在第二步，CLIQUE 为每个簇生成最小化的描述。对每个簇，它确定覆盖相连的密集单
元的最大区域，然后确定最小的覆盖。
“CLIQUE 的有效性如何？” 因为高密度的聚类存在于那些子空间中，CLIQUE 自动地
发现最高维的子空间，对元组的输入顺序不敏感，无需假设任何规范的数据分布。它随输入
数据的大小线性地扩展，当数据的维数增加时具有良好的可扩展性。但是，由于方法大大简
化，聚类结果的精确性可能会降低。
6.6. 聚类有效性
对聚类算法的结果进行定时量评价，这个任务一般称为聚类有效性（cluster validity ）。
然而，需要强调的是，这些算法所得到结果仅仅是专家用来对聚类结果进行评价的工具。聚
类有效性通常需要一个有效性指标(函数)来度量。现有的有效性指标大致分为三大类：
1) 外部指标：外部指标用与结构无关的方法对C 进行评估，也就是在X 上施加一个先验值，
它反映使用者对X 聚类结构的直觉。另外，外部准则也可构的直觉，外部准同则也可以用
于测量有效数据与预定义结构之间的符合程度，这种测量不需要在X 上应用任何聚类算法。
2) 内部指标：内部指标用所包含的X 的向量来定量地对C 进行评价，例如近邻矩阵。
3) 相对指标：相对指标通过把当前的聚类结果与使用相同聚类算法但是参数不同或者使用
不同的聚类算法所得的结果进行比较，根据比较结果进行评价。
令C 表示聚类算法作用于X 而得的聚类结构，这可能是层次算法得出的，也可能是
带有目标函数的其他算法生成的。上述三类有效性指标进一步说明如下:
6.6.1 外部准则
外部准则常常使用在下面两种情况，一是将聚类算法生成的聚类结构和独立于C 的X
划分Π相比较， 二是为了测试预定义的划分Π和X 的近邻矩阵P 之间的一致程度。
首先说明Π与聚类C 的比较。在这种情况下，C 常常是某个特定聚类算法获得的结
构。根据独立于X 的划分P ，考虑由一个特定的聚类算法得到的聚类C 有效性验证工作。
令C=｛C 1，…，C m ｝，P =｛P 1，…，P s ｝，注意C 中的聚类数与Π中的组数不一定相同。
令n ij 表示属于C i 同时也属于P j 的向量个数。令∑
==s j ij
c i n n 1；也就是说，c i n 是属于C i 的向量个数。类似地，定义属于P j 的向进个数为∑==m i ij p j n n 1。 考虑一对向量),(u v x x ，分别使用下面几个记号表示这对向量的比对结果：(a)SS ，表
示这两个向量属于C 中的同一聚类，同时也属于Π中的同一组； (b)DD ，如果这两个向量
属于C 中的不同的聚类，而且属于Π中的不同组; (C)SD ，如果这两个两个向量属C 中的同
一个聚类，同时属于Π中的不同组；(D)DS ，如果这两个两个向量属于C 中的不同的聚类，
同时属于Π中的同一组。设a 、b 、c 、d 分别为X 中的SS ，SD ，DS 和DD 向量对的个数，
则有a+b+c+d=M ，其中M 为X 中可能的向量对个数。也就是说，M=N(N-1)/2。
例6.6 设X={X i ，i =l ，…，6}，C={{ X 1，X 2，X 3}，{X 4，X 5，X 6}}，并且Π={{X 1，X 2，
X 3}，{X 4，X 5，X 6}}。下表显示了X 中所有向量对的类型。
表格2. 比较不同划分
X 1X 2X 3X 4 X 5
X 6 x 1 SS SS DD DD
DD X 2 SS DD DD
DD X 3 DD DD
DD X 4 SS
DS X 5
DS X 6
观察表格2可以得到a=4，b=0，c=2，d =9。设m 1=a+b 是属于C 中同一个聚类的向量对的
个数，m 2=a+c 是属于P 中同一组的向量对的个数，使用上述定义，可以定义测量C 与Π的
匹配程度的统计指标。目前常用的有：
R=（a+b ）/ M (Rand 统计); (6.3.3)
J=a /（a+b+c ）(Jaccard 系数) (6.3.4)
))((/221c a b a a m m a FM ++==(Fowlkes 和Mallows 指标) (6.3.5)
a+d 项是SS 向量对与DD 向量对的个数的和，因此Rand 统计量为SS 或DD 向量对占向量
对总数的百分数。Jaccard 系数与Rand 统计的原理类似，只是它不包括d 。这两个统计量的
值0和1之间。然而取得最大值的前提是m=s 。但是通常不是这种情况。对于上述定义的指
标，很显然它们的值越大，C 和Π的一致性越高。另外一个与外部准则相关的流行统计是
Hubert 的Г统计，该参数测量两个相互独立的N×N 矩阵X 和Y 之间的相关性。对于对称
矩阵，Hubert 的Г统计可以表示为
),(),((1/M)11-n 1j j i Y j i X n
i j ∑∑+===Γ (6.3.6)
其中),(j i X 和),(j i Y 分别是矩阵X 和Y 的元素),(j i 。Г值越高，意味着X 和Y 之间越一
致。Г统计的归一化形式Γ
?如下。 Y x N i j y X N i j i Y j i X M σσμμΓ∑∑+=?=??=111)
),()(),(()/1(? (6.3.7)
其中22,,Y X Y X σσμμ和分别为均值和方差，即∑∑?=+==111),()
/1(N i N i j X j i X M μ，∑∑?=+=?=112122),()/1(N i X N i j X j i X M μσ（与此类似，可以定义Y μ和2Y σ）。Γ
?在-1到1之间取值。如果j i x x ,属于C 中的同一个聚类，则设X ),(j i 等于1；否则X ),(j i 设为0。如果
j i x x ,属于Π中的同一个组，则设),(j i X 等于1；否则),(j i Y 为0。Г)?(Γ
的绝对值大意味着C 和P 相互一致。
6.6.2 内部准则
内部准则用数据本身所固有的信息来验证聚类算法产生的聚类结构是否适合数据。接
下来，除非特别指出，都认为近邻矩阵可以代表数据。分两种情况考虑；(a)聚类结构是聚
类的层次结构；（b ）聚类结构由单一聚类组成。
聚类层次的有效性
回忆一下层次聚类算法产生的树图可以由各自的同现矩阵P c 表达。我们定义一个测量
层次聚类算法产生的同现矩阵P c 与X 的近邻矩阵P 的一致性程度的统计指标。因为两个矩
阵都是对称的，并且其对角线元素都为0①，所以只需要考虑P c 和P 的上对角线元素，一共
有M=N （N-1）/2个元素。设d ij 和C ij 分别为P 和P c 的（i, j ）元素。
第一个指标被称为同现相关系数（CoPhenetic Correlation Coefficient,CPCC ）,当矩阵是
区间或比例缩放数据时，用来测量P C 和P 之间的相关性。定义为
)
/1)()/1(()/1(11111111
12222∑∑∑∑∑∑?=+=?=?+=?=+=??=N i N i j N i N c i j N i N i j p ij d c ij c p dijcij M M M CPCC μμμμ (6.3.7) 其中相应的均值由式（16.9）定义。可以看出CPCC 的值在-1和1之间（见习题16.4），CPCC
指标越接近于1，同现矩阵和近邻阵的一致性越好。很多学者都研究过CPCC 统计量（如
[Rolp68，Rolp70,Frr69]），它的主要难点是它依赖于很多参数，例如X 的大小、使用的聚类
算法以及使用的近邻测度等。因此，在H 0下精确地计算它的概率密度函数是非常困难的，在
H 0下必须使用Monte Carlo 技术来估计该分布。根据随机位置假设，生成了r 个集合X i ，每
个集合的向量都服从均匀分布，在每个X i 上应用相同的层次算法产生P c 。然后计算Xi 的近
邻矩阵P i 和得到的同现矩阵P ci 的CPCC ，并且构造对应的直方图。
在趣的是，[Rolp 70]中论述了这样一种情况：当用不加权成对分组平均（UPGMA ）算
法（见第13章）时，即使CPCC 的值很高（接近0.9），也要谨慎处理，因为即使CPCC 很
高也不能保证同现矩阵和近邻矩阵的一致程度高。
另一个统计指标r 将会在后面讨论，它适用于PCP 都是有序缩放的情况。设v p 和v c 是
两个N （N-1）/2维向量，其中每个向量分别包含有P 和Pc 的上对角元素（按行序排列）。
设v ci ，v cj 的两对元素，一些定义如下。
r 统计与问题的所有因素有关，所以随机假设H0下的概率密度函数的估计是很难求的。因
此，再一次使用Monte Carlo 技术估计H0下的概率密度函数。在这种情况下，使用的是随
机图假设。特别地，我们生成r 个随机秩序近邻矩阵Pi （不含结），然后在每个Pi 运行算 法
产生Pc 。计算每个Pi 的r 值和相应同现矩阵Pci 的r 值，并且建立r 值的直方图。
● 如果
（（v pi ＜v pj ）&（v pi ＜v cj ））或（（v pi ＞v ci ）&(v pj ＞v cj )）
{(v pi ,v pj ),(v ci ,v cj )}对的集合被称为协调的。
● 如果
（（v pi ＜v pj ）&（v pi ＞v cj ））或（（v pi ＞v ci ）&(v pj ＜v cj )）
{(v pi ,v pj ),(v ci ,v cj )}对的集合被称为不协调的。
最后，如果v pi =v ci 或者v pi =v ci ,则对集合既不是协调的，也不是不协调的。设S +和S -分别为
协调对和不协调对的个数。则Y 定义为
?
+?++?=
s s s s Y （6.14） Y 的统计值在-1和1之间。
6.6.3 相关准则
到目前为止，聚类有效性验证是基于统计检验进行处理的，这样技术的主要缺点就是它
们需要大量的数据计算，这是由于它们需要使用Monte Carlo 技术。在这一节里，讨论了
一种不同的方法，该方法并不涉及统证检验，在本节的末尾，考虑了一个聚类集合，目的是
根据预定义的准则选择出一个最好的。令A 是与特定聚类算法相关的参数向量的初始估计
值。问题可以陈述如下：
“在某个聚类算法所产生的聚类集合A 中，从不同参数值中，选出一个与数据集X 最符
合的参数值。”考虑下面几种情况：
●A 不包含聚类数m 作为参数（例如。基于图论的算法、形态学聚类算法以及边界检测
算法）。对这类算法，最好的参数值的选择其于如一假设：如果X 具有一个聚类结构。则该
结构在较大的范围内适于A 中的参数（如[Post 93]）。基于这种假设，处理过程如下。在大
的参数值范围内运行算法，选择最大范围，参数m 仍是常数（典型地m ＜＜N ＝。然后，在
这个范围中，选择A 中的合适参 数值，注意该算法也隐含地识别出X 所具有的聚类数。
6.7. 分类算法
数据分类是一个两步过程（图7.1）。第一步，建立一个模型，描述预定的数据类或概念集。通过分析由属性描述的数据库元组来构造模型。假定每个元组属于一个预定义的类，由一个称作类标号属性的属性确定。对于分类，数据元组也称作样本、实例或对象。为建立模型而被分析的数据元组形成训练数据集。训练数据集中的单个元组称作训练样本，并随机地由样本群选取。由于提供了每个训练样本的类标号，该步也称作有指导的学习（即，模型的学习在被告知每个训练样本属于哪个类的“指导”下进行）。它不同于无指导的学习（或聚类），那里每个训练样本的类标号是未知的，要学习的类集合或数量也可能事先不知道。
通常，学习模型用分类规则、判定树或数学公式的形式提供。例如，给定一个顾客信用信息的数据库，可以学习分类规则，根据他们的信誉度优或相当好来识别顾客（图7.1(a)）。该规则可以用来为以后的数据样本分类，也能对数据库的内容提供更好的理解。
第二步（图7.1(b)），使用模型进行分类。首先评估模型（分类法）的预测准确率。本章的7.9节介绍评估分类准确率的多种方法。保持（holdout）方法是一种使用类标号样本测试集的简单方法。这些样本随机选取，并独立于训练样本。模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比。对于每个测试样本，将已知的类标号与该样本的学习模型类预测比较。注意，如果模型的准确率根据训练数据集评估，评估可能是乐观的，因为学习模型倾向于过分适合数据（即，它可能并入训练数据中某些异常，这些异常不出现在总体样本群中）。因此，使用测试集。
如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。（这种数据在机器学习也称为“未知的”或“先前未见到的”数据）。例如，在图7.1(a)通过分析现有顾客数据学习得到的分类规则可以用来预测新的或未来顾客的信誉度。
“预测和分类有何不同？”预测是构造和使用模型评估无标号样本，或评估给定样本可能具有的属性值或值区间。在这种观点下，分类和回归是两类主要预测问题；其中，分类是预测离散或标称值，而回归用于预测连续或有序值。然而，我们的观点是：预测类标号为分类，预测连续值（例如，使用回归方法）为预测。这种观点在数据挖掘界广泛接受。
例6.7.1假定我们有一个AllElectronics的邮寄清单数据库。邮寄清单用于分发介绍新产品和降价信息材料。数据库描述顾客的属性，如他们的姓名、年龄、收入、职业和信誉度。顾客可以按他们是否在AllElectronics购买计算机分类。假定新的顾客添加到数据库中，你想将新计算机的销售信息通知顾客。将促销材料分发给数据库中的每个新顾客的费用可能很高。一个更有效的方法是只给那些可能买新计算机的顾客寄材料。为此，可以构造和使用分类模型。
另外，假定你想预测在一个财政年度，一个顾客将在AllElectronics进行的主要购买数量。由于预测的值是有序的，为此可以构造一个预测模型。
6.7.2 关于分类和预测的问题
1) 准备分类和预测数据
可以对数据使用下面的预处理，以便提高分类和预测过程的准确性、有效性和可规模性。
数据清理：是旨在消除或减少数据噪音（例如，使用平滑技术）和处理遗漏值（例如，用该属性最常出现的值，或根据统计，用最可能的值替换遗漏值）的数据预处理。尽管大部分分类算法都有处理噪音和遗漏值的机制，但该步骤有助于减少学习时的混乱。
相关性分析：数据中许多属性可能与分类和预测任务不相关。例如，记录银行贷款星期几签署的数据可能与应用的成功不相关。此外，其它属性可能是冗余的。因此，可以进行相关分析，删除学习过程中不相关或冗余属性。在机器学习，这一过程称为特征选择。
包含这些属性将减慢和误导学习步骤。 理想地，用在相关分析上的时间，加上从“压缩的”结果子集上学习的时间，应当少于由原来的数据集合上学习所花的时间。因此，这种分析可以帮助提高分类的有效性和可规模性。 数据变换：数据可以泛化到较高层概念。概念分层可以用于此目的。对于连续值属性，
这一步非常有用。例如，属性income 的数值值可以泛化为离散的区间，如low, medium
和high 。类似地，标称值，如street ，可以泛化到高层概念，如city 。由于泛化压缩了
原来的训练数据，学习时的输入/输出操作将减少。
数据也可以规范化，特别是在学习阶段使用神经网络或涉及距离度量的方法时。规
范化涉及将属性的所有值按比例缩放，使得它们落入较小的指定区间，如-1.0到1.0，
或0.0到1.0。例如，在使用距离度量的方法中，这可以防止具有较大初始域的属性（如
income ）相对于具有较小初始域的属性（如二进位属性）权重过大。
数据清理、相关分析和数据变换已在本书的第3章详细介绍。相关分析还在第5章介绍过。
2) 比较分类方法。
分类和预测方法可以根据下列标准进行比较和评估：
预测的准确率：这涉及模型正确地预测新的或先前未见过的数据的类标号的能力。
速度：这涉及产生和使用模型的计算花费。
强壮性：这涉及给定噪音数据或具有遗漏值的数据，模型正确预测的能力。
可规模性：这涉及给定大量数据，有效地构造模型的能力。
可解释性：这涉及学习模型提供的理解和洞察的层次。
6.7.2 贝叶斯分类
“什么是贝叶斯分类？”贝叶斯分类是统计学分类方法。它们可以预测类成员关系的可能
性，如给定样本属于一个特定类的概率。
贝叶斯分类基于贝叶斯定理，在下面介绍。分类算法的比较研究发现，一种称作朴素贝
叶斯分类的简单贝叶斯分类算法可以与判定树和神经网络分类算法相媲美。用于大型数据
库，贝叶斯分类也已表现出高准确率与高速度。
朴素贝叶斯分类假定一个属性值对给定类的影响独立于其它属性的值。该假定称作类条件独
立。做此假定是为了简化所需计算，并在此意义下称为“朴素的”。 贝叶斯信念网络是图形
模型。不象贝叶斯朴素分类，它能表示属性子集间的依赖。贝叶斯信念网络也可以用于分类。
设X 是类标号未知的数据样本。设H 为某种假定，如，数据样本X 属于某特定的类C 。
对于分类问题，我们希望确定)|(X H P ——给定观测数据样本X ，假定H 成立的概率。
)|(X H P 是后验概率，或条件X 下，H 的后验概率。例如，假定数据样本世界由水果
组成，用它们的颜色和形状描述。假定X 表示红色和圆的，H 表示假定X 是苹果，则)
|(X H P 反映当我们看到X 是红色并是圆的时，我们对X 是苹果的确信程度。P(H)是先验概率，或
H 的先验概率。对于我们的例子，它是任意给定的数据样本为苹果的概率，而不管数据样本
看上去如何。后验概率)|(X H P 比先验概率P(H)基于更多的信息（如，背景知识）。P(H)
是独立于X 的。
类似地，)|(H X P 是条件H 下，X 的后验概率。即，它是已知X 是苹果，X 是红色并且
是圆的的概率。P(X)是X 的先验概率。使用我们的例子，它是由我们的水果集取出一个数据
样本是红的和圆的的概率。
“如何计算这些概率？”正如我们下面将看到的，P(X)，P(H)和)|(H X P 可以由给定的数
据计算。贝叶斯定理是有用的，它提供了一种由P(X)，P(H)和)|(H X P 计算后验概率
)|(X H P 的方法。贝叶斯定理是：
)
()()|()|(X P H P H X P X H P = （7.5） 朴素贝叶斯分类，或简单贝叶斯分类的工作过程如下：
1. 每个数据样本用一个n 维特征向量},...,,{21n x x x X =表示，描述由属性n A A A ,...,,21对
样本的n 个度量。
2. 假定有m 个类m C C C ,...,,21。给定一个未知的数据样本X （即，没有类标号），分类法
将预测X 属于具有最高后验概率（条件X 下）的类。即，朴素贝叶斯分类将未知的样本
分配给类C i ，当且仅当：
.1)|()|(i j m j X C P X C P j i ≠≤≤>
这样，我们最大化)|(X C P i 。其)|(X C P i 最大的类C i 称为最大后验假定。根据贝叶斯
定理((7.5)式),
)
()()|()|(X P i C P i C X P X C P i = (7.6) 3． 由于P(X) 对于所有类为常数，只需要)()|(i i C P C X P 最大即可。如果类的先验概率未知，
则通常假定这些类是等概率的；即，)(...)()(21m C P C P C P ===。并据此对只)|(X C P i 最
大化。否则，我们最大化)()|(i i C P C X P 。注意，类的先验概率可以用s s C P i i =)(计算；
其中，s i 是类C 中的训练样本数，而s 是训练样本总数。
4． 给定具有许多属性的数据集，计算)|(i C X P 的开销可能非常大。为降低计算)|(i C X P 的
开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属性值条件地相互独立。
即，在属性间，不存在依赖关系。这样，
∏==n k i k i C x
p C X P 1)|()|( （7.7）
概率)|(1i C x P ,)|(2i C x P ,...,)|(i n C x P 可以由训练样本估值，其中，
(a)
如果A k 是分类属性，则i ik i k s s C x P =)|(；其中s ik 是在属性A k 上具有值x k 的类C i 的训练样本数，而s i 是C i 中的训练样本数。 (b) 如果是连续值属性，则通常假定该属性服从高斯分布。因而，
)}/()(exp{),,()|(22221c C C C k i k x x g C x P i i i σμσπσμ??== （7.8）
其中，给定类C i 的训练样本属性A k 的值，),,(i i C C k x g σμ是属性A k 的高斯密度函
数，而i i C C σμ,分别为平均值和标准差。
5． 为对未知样本X 分类，对每个类C i ，计算)()|(i i C P C X P 。样本X 被指派到类C i ，当且
仅当：
.
1)()|()()|(i j m j C P C X P C P C X P j j i i ≠≤≤> 换言之，X 被指派到其)()|(i i C P C X P 最大的类C i 。
“贝叶斯分类的效率如何？”理论上讲，与其它所有分类算法相比，贝叶斯分类具有最小
的出错率。然而，实践中并非总是如此。这是由于对其应用的假定（如，类条件独立性）的
不正确性，以及缺乏可用的概率数据造成的。然而，种种实验研究表明，与判定树和神经网
络分类算法相比，在某些领域，该分类算法可以与之媲美。
贝叶斯分类还可以用来为不直接使用贝叶斯定理的其它分类算法提供理论判定。例如，
在某种假定下，可以证明正如朴素贝叶斯分类一样，许多神经网络和曲线拟合算法输出最大
的后验假定。
聚类 一、聚类的定义 聚类，属于一种非监督学习方法，它试图在无标签的数据集中发现其分布状况或模式。通常，我们认为同一聚类中的数据点比不同聚类的数据点具有更大的相似性。 二、传统的聚类算法的分类 1、基于划分的聚类算法 主要思想：基于划分的聚类算法通过构造一个迭代过程来优化目标函数，当优化到目标函数的最小值或极小值时，可以得到数据集的一些不相交的子集，通常认为此时得到的每个子集就是一个聚类。 典型方法： k-means算法 FCM算法。 2、层次聚类算法 主要思想：层次聚类方法使用一个距离矩阵作为输入，经过聚类后得到一个反映该数据集分布状况的聚类层次结构图。 层次聚类算法通常分为两种： 凝聚的层次聚类算法：它首先把每个数据点看作是一个聚类，然后以一种自底向上的方式通过不断地选择最近邻居聚类对的合并操作，最终可以构造出一棵代表着该数据集聚类结构的层次树。 分类的层次聚类算法：它首先把所有的数据点看作是一个聚类，然后以一种以自顶向下的方式通过不断地选择最松散簇进行分裂操作，最终可以构造出一棵代表着该数据集聚类结构的层次树。 典型方法： AGNES (AGglomerative NESting) BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) CURE (Clustering Using REpresentative) 3、基于密度的聚类算法 主要思想：基于密度的聚类算法试图通过稀疏区域来划分高密度区域以发现明显的聚类和孤立点，主要用于空间型数据的聚类。 典型方法： DBSCAN (Density-based Spatial Clustering of Application with Noise) OPTICS (Ordering Points to Identify the Clustering Structure) 4、基于网格的聚类算法 主要思想：基于网格的聚类算法是一种基于网格的具有多分辨率的聚类方法。它首先将数据集的分布空间划分为若干个规则网格(如超矩形单元)或灵活的网格(如任意形状的多
文本分类与聚类(text categorization and clustering) 1.概述 广义的分类（classification或者categorization）有两种含义：一种含义是有领导的学习（supervised learning）过程，另一种是无领导的学习（unsupervised learning）过程。通常前者称为分类，后者称为聚类（clustering），后文中提到的分类都是指有指点的学习过程。 给定分类系统，将文本集中的每个文本分到某个或者某几个类别中，这个过程称为文本分类（text categorization）。将文本聚集分组成多个类或簇，使得在同一个簇中的文本内容具有较高的相似度，而不同簇中的文本内容差异较大，这个过程称为文本聚类（text clustering）。 2. 文本分类 2.1 文本分类的步骤 典范的文本分类进程可以分为三个步骤： 1. 文本表现（Text Representation） 这一过程的目标是把文本表示成分类器能够处理的情形。最常用的方法是向量空间模型，即把文本集表示成词－文档矩阵，矩阵中每个元素代表了一个词在相应文档中的权重。选取哪些词来代表一个文本，这个过程称为特点选择。常见的特征选择方法有文档频率、信息增益、互信息、期看交叉熵等等。为了减少分类过程中的计算量，经常还需要进行降维处理，比如LSI。 2. 分类器构建（Classifier Construction） 这一步骤的目标是选择或设计构建分类器的方法。没有一种通用的方法可以实用所有情形。不同的方法有各自的优缺点和实用条件，要依据问题的特色来选择一个分类器。后面专门讲述常用的方法。选定方法之后，在训练集上为每个种别构建分类器，然后把分类器利用于测试集上，得到分类结果。 3. 后果评估（Classifier Evaluation） 在分类过程完成之后，需要对分类后果进行评估。评估过程运用于测试集（而不是训练集）上的文本分类结果，常用的评估尺度由IR范畴继续而来，包括查全率、查准率、F1值等等。对于某一类别i，查全率ri=li/ni，其中ni为所有测试文档中，属于第i类的文档个数；li是经分类系统输出分类结果为第i类且结果准确的文档个数。查准率pi=li/mi，其中mi是经分类体系输出分类结果为第i类的文档个数，li是经分类系统输出分类结果为第i类且结果准确的文档个数。F1值为查全率和查准率的协调均匀数，即：。 相对于最简略的练习集－测试集评估办法而言，还有一种称为k-fold cross validation的方式，即把所有标志的数据划分成k个子集，对于每个子集，把这个子集当作训练集，把其余子集作为测试集；这样履行k 次，取各次评估成果的均匀值作为最后的评估结果。 2.2 常见的文本分类方法 1. Rocchio方法 每一类断定一个中心点（centroid），计算待分类的文档与各类代表元间的间隔，并作为判定是否属于该类的判据。Rocchio方法最早由[Hull, 1994]引进文本分类范畴，后来又有很多文章进行了改良。Rocchio方法的特点是轻易实现，效力高。缺点是受文本集分布的影响，比如计算出的中心点可能落在相应的类别之外[Sebastiani, 2002]。 2. 朴实贝叶斯（naive bayes）方式 将概率论模型利用于文档主动分类，是一种简略有效的分类方法。应用贝叶斯公式，通过先验概率和类别的条件概率来估量文档对某一类别的后验概率，以此实现对此文档所属类别的断定。[Lewis, 1998]介绍了
聚类分析 聚类(clustering)就是将数据对象分组成为多个类或簇(cluster)，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。相异度是基于描述对象的属性值来计算的。距离是经常采用的度量方式。聚类分析源于许多研究领域，包括数据挖掘，统计学，生物学，以及机器学习。 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。在许多应用中，一个簇中的数据对象可以被作为一个整体来对待 “聚类的典型应用是什么？”在商业上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。 聚类也能用于对Web 上的文档进行分类，以发现信息。作为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇作进一步的分析。此外，聚类分析可以作为其他算法（如分类等）的预处理步骤，这些算法再在生成的簇上进行处理 作为统计学的一个分支，聚类分析已经被广泛地研究了许多年，主要集中在基于距离的聚类分析。基于k-means(k-平均值)，k-medoids(k-中心)和其他一些方法的聚类分析工具已经被加入到许多统计分析软件包或系统中，例如S-Plus，SPSS，以及SAS。 在机器学习领域，聚类是无指导学习(unsupervised learning)的一个例子。与分类不同，聚类和无指导学习不依赖预先定义的类和训练样本。由于这个原因，聚类是通过观察学习，而不是通过例子学习。 在概念聚类（conceptual clustering）中，一组对象只有当它们可以被一个概念描述时才形成一个簇。这不同于基于几何距离来度量相似度的传统聚类。概念聚类由两个部分组成：（1）发现合适的簇；（2）形成对每个簇的描述。在这里，追求较高类内相似度和较低类间相似度的指导原则仍然适用。 活跃的研究主题集中在聚类方法的可伸缩性，方法对聚类复杂形状和类型的数据的有效性，高维聚类分析技术，以及针对大的数据库中混合数值和分类数据的聚类方法。 数据挖掘对聚类的典型要求如下：
聚类分析和关联规则属于数据挖掘这个大概念中的两类挖掘问题， 聚类分析是无监督的发现数据间的聚簇效应。 关联规则是从统计上发现数据间的潜在联系。 细分就是 聚类分析与关联规则是数据挖掘中的核心技术； 从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。 从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式的学习。 聚类分析是一种探索性的分析，在分类的过程中，人们不必事先给出一个分类的标准，聚类分析能够从样本数据出发，自动进行分类。聚类分析所使用方法的不同，常常会得到不同的结论。不同研究者对于同一组数据进行聚类分析，所得到的聚类数未必一致。 从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。而且聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。聚类分析还可以作为其他算法（如分类和定性归纳算法）的预处理步骤。 关联规则挖掘过程主要包含两个阶段：第一阶段必须先从资料集合中找出所有的高频项目组(FrequentItemsets)，第二阶段再由这些高频项目组中产生关联规则(AssociationRules)。 关联规则挖掘的第一阶段必须从原始资料集合中，找出所有高频项目组(LargeItemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言，必须达到某一水平。 关联规则挖掘的第二阶段是要产生关联规则(AssociationRules)。从高频项目组产生关联规则，是利用前一步骤的高频k-项目组来产生规则，在最小信赖度(MinimumConfidence)的条件门槛下，若一规则所求得的信赖度满足最小信赖度，称此规则为关联规则。
实例解析关键词聚类的方法策略 收藏到：1时间：2014-06-05 文章来源：马海祥博客访问次数：388 最近，马海祥接手了一个大型的网站，首先要做的就的对这个网站的流量来源进行分析，这其中最繁琐的莫过于对来源关键词的聚类整合了。 所谓关键词聚类就是以领域特征明显的词和短语作为聚类对象，在分类系统的大规模层级分类语料库中，利用独创的文本分类的特征提取算法进行词语的领域聚类，通过控制词语频率的影响，分别获取领域通用词和领域专类词。 所以，要想做好这类做关键词的聚类，就一定要有一些基础信息，基础数据作为背景。在此，我就借助马海祥博客的平台跟大家实例解析关键词聚类的方法策略： 1、百度商业词聚类模型
现在对于一些医疗SEO来说看行业新闻，大家经常讨论一个话题就是百度医疗行业的收入贡献比是多少？，其实，爆个大料给大家，在2005年甚至2006年之前，百度自己都不掌握这类数据。 当时百度有一个简单的客户分类，是客服提交的，然后我们看了一下消费的行业分布，结果显示超过50%属于其他分类，这个结果基本上就没法看了。 然后我就琢磨，用商业词能不能直接聚类为行业，当时我在产品部门，合作反欺诈点击的工程师是张怀亭，这是个算法高手，他当年的毕业论文就是关联规则和聚类算法，我就去请教他，他说了一堆，我大部分没听懂，但大概要点知道了一些，然后找他要了论文看了看，也没太看明白，凭借自己粗浅的理解我就动手了，然后这个还真做成了。 我的出发点就是假设客户本身具有行业属性(如果这个假设不存在，那就没辙了)，我认为每个客户提交的关键词，彼此是有关联的。某两个关键词如果同时被不同的客户提交，其关联性就会随之增加，这个是最基本的一个定义，叫做共同推举数，也是最容易算的一个值。 但是仅仅依赖于共同推举数有一个问题，就是会导致很多词都和热门词关联，这是不合理的，我记得当时好像是某网上书城的推荐购买那一栏，明显都是热门书籍，似乎也是基于共同推举数做的关联。 问题1：A和B有50个共同推举，A和C有30个共同推举，但是B这个词是热门词，共有2000个客户提交；而C是冷门词，只有50个客户提交，请问A和B的关联度高还是A和C的关联度高？ 问题2：客户1提交了10000个词(类似阿里真的是这么提交的)；客户2提交了20个词，客户1所提交的10000个词的彼此关联度和客户2之间提交的是否一致？ 考虑这两个问题，就需要做权值调整了，然后再计算词与词的关联值。那么，权值该怎么定呢？
聚类和分类的区别 2008-10-22 19:57 分类(classification)是这样的过程： 它找出描述并区分数据类或概念的模型(或函数)，以便能够使用模型预测类标记未知的对象类。分类分析在数据挖掘中是一项比较重要的任务,目前在商业上应用最多。分类的目的是学会一个分类函数或分类模型(也常常称作分类器),该模型能把数据库中的数据项映射到给定类别中的某一个类中。分类和回归都可用于预测，两者的目的都是从历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行预测。与回归不同的是，分类的输出是离散的类别值，而回归的输出是连续数值。二者常表现为决策树的形式，根据数据值从树根开始搜索，沿着数据满足的分支往上走，走到树叶就能确定类别。要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据库记录或元组构成，每个元组是一个由有关字段(又称属性或特征)值组成的特征向量，此外，训练样本还有一个类别标记。一个具体样本的形式可表示为：（v1,v2,...,vn;c)；其中vi表示字段值，c表示类别。分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。不同的分类器有不同的特点。有三种分类器评价或比较尺度：1)预测准确度；2)计算复杂度；3)模型描述的简洁度。预测准确度是用得最多的一种比较尺度，特别是对于预测型分类任务。计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据，因此空间和时间的复杂度问题将是非常重要的一个环节。对于描述型的分类任务，模型描述越简洁越受欢迎。另外要注意的是，分类的效果一般和数据的特点有关，有的数据噪声大，有的有空缺值，有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数据 聚类(clustering) 是指根据“物以类聚”的原理，将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合叫做簇，并且对每一个这样的簇进行描述的过程。它的目的是使得属于同一个簇的样本之间应该彼此相似，而不同簇的样本应该足够不相似。与分类规则不同，进行聚类前并不知道将要划分成几个组和什么样的组，也不知道根据哪些空间区分规则来定义组。其目的旨在发现空间实体的属性间的函数关系，挖掘的知识用以属性名为变量的数学方程来表示。当前，聚类技术正在蓬勃发展，涉及范围包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销等领域，聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。常见的聚类算法包括：K-均值聚类算法、K-中心点聚类算法、CLARANS、BIRCH、CLIQUE、DBSCAN等。
一、层次聚类 1、层次聚类的原理及分类 1）层次法（Hierarchical methods）先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成了一个类。其中类与类的距离的计算方法有：最短距离法，最长距离法，中间距离法，类平均法等。比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。 层次聚类算法根据层次分解的顺序分为：自下底向上和自上向下，即凝聚的层次聚类算法和分裂的层次聚类算法（agglomerative和divisive），也可以理解为自下而上法（bottom-up）和自上而下法（top-down）。自下而上法就是一开始每个个体（object）都是一个 类，然后根据linkage寻找同类，最后形成一个“类”。自上而下法就是反过来，一开始所有个体都属于一个“类”，然后根据linkage排除异己，最后每个个体都成为一个“类”。这两种路方法没有孰优孰劣之分，只是在实际应用的时候要根据数据特点以及你想要的“类”的个数，来考虑是自上而下更快还是自下而上更快。至于根据Linkage判断“类” 的方法就是最短距离法、最长距离法、中间距离法、类平均法等等（其中类平均法往往被认为是最常用也最好用的方法，一方面因为其良好的单调性，另一方面因为其空间扩张/浓缩的程度适中）。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。 2）Hierarchical methods中比较新的算法有BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies利用层次方法的平衡迭代规约和聚类）主要是在数据量很大的时候使用，而且数据类型是numerical。首先利用树的结构对对象集进行划分，然后再利用其它聚类方法对这些聚类进行优化；ROCK（A Hierarchical Clustering Algorithm for Categorical Attributes）主要用在categorical的数据类型上；Chameleon（A Hierarchical Clustering Algorithm Using Dynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此构建一个graph，Chameleon的聚类效果被认为非常强大，比BIRCH好用，但运算复杂度很高，O(n^2)。 2、层次聚类的流程 凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。这里给出采用最小距离的凝聚层次聚类算法流程： (1) 将每个对象看作一类，计算两两之间的最小距离； (2) 将距离最小的两个类合并成一个新类； (3) 重新计算新类与所有类之间的距离； (4) 重复(2)、(3)，直到所有类最后合并成一类。
聚类分析与判别分析区别1 2 聚类分析和判 3 别分析就是这样的分类方法 4 ， 5 目前它们已经成为 6 比较标准的数据分类方法。 7 我们常说 8 “物以类聚、 9 人以群分” 10 ， 11 就是聚类分 12 析和判别分析最简单、 13 14 最朴素的阐释 15 ， 16 并且这一成 17 语也道明了这两种方法的区别与联系 ， 18 19 都是分类 20 技术 ， 21 22 但它们是分别从不同的角度来对事物分类 的 23 24 ， 25 或者说 ， 26 27 是两种互逆的分类方式。聚类分析与 28 判别分析都是多元统计中研究事物分类的基本方 29 法 30 ， 31 但二者却存在着较大的差异。 32 一、 33 聚类分析与判别分析的基本概念 34 １ 35 、 36 聚类分析 37 又称群分析、 38 点群分析。 39 根据研究对象特征对 40 研究对象进行分类的一种多元分析技术 ， 41 42 把性质
相近的个体归为一类 1 2 ， 3 使得同一类中的个体都具 4 有高度的同质性 5 ， 6 不同类之间的个体具有高度的 异质性。 7 8 根据分类对象的不同分为样品聚类和变量聚类。9 ２ 、 10 11 判别分析 12 是一种进行统计判别和分组的技术手段。根 13 据一定量案例的一个分组变量和相应的其他多元14 变量的已知信息 15 ， 16 确定分组与其他多元变量之间 17 的数量关系 18 ， 19 建立判别函数 ， 20 21 然后便可以利用这一 22 数量关系对其他未知分组类型所属的案例进行判23 别分组。 24 判 25 别 26 分 27 析 28 中 29 的 30 因 变 31 32 量 33 或 34 判 35 别 36 准 则 37 38 是 39 定 类 40 41 变 42 量 ， 43 44 而自变量或预测变量基本上是定距变量。
聚类与分类
IRLAB
聚类
大纲
? 聚类分析简介 ? 层次聚类 – 单连接和全连接聚类 – 组平均聚类 – 应用：改进语言模型 – 自顶向下聚类 ? 非层次聚类 – K-均值 – EM算法
什么是聚类分析?
? 聚类: 数据对象的集合 – 在同一个类中，数据对象是相似的 – 不同类之间的对象是不相似的 ? 聚类分析 – 一个数据集合分组成几个聚类 ? 聚类是一种无监督分类:没有预定义的类 ? 典型应用 – 作为一个独立的工具 透视数据分布 – 可以作为其他算法的预处理步骤
聚类在自然语言中的应用
? 探测数据分析（exploratory data analysis）
– 例如词性标注，将相似的词作为同一种词性，对 前置词比较有效 – 对this和the 这种语法语义特征不一致的词，不总分 在一组的词不适合
? 概化（generalization）
– 等价类，可以使用相同的上下文环境，解决数据 稀疏问题 – 同时聚类是学习的一种方法（推理 Friday 的前置 词）
聚类算法类型
? 层次聚类与非层次聚类 – 层次聚类的每一个节点是其父节点的一个子类， 叶节点对应的是类别中每一个单独的对象，常用 算法自底向上与自上向下（凝聚与分裂） – 非层次聚类只是简单的包括了每类的数量，体现 不了他们之间的层次关系，常用算法K-均值 ? 软聚类与硬聚类 – 硬聚类将每一个对象分到一个且只能是一个的类 别中，例如K-均值 – 软聚类刻画的是将对象归属不同类的程度，模糊 聚类（EM算法）
气象资料孤立点分析决策树聚类分析关联规则分析气数挖气研象资料资文,据掘技资在象资料分析中资用究 【中文摘要】象资料的容量和资域资资的推移不增资和拓资气随断,形成 了资料山和资料迷资。如何有效地利用资些资料是象资域工作者面资的一气个很数大资资。资资的资算机资域中的资理方法是资资理资资大资模的据集, 因此必 资借助于据掘技资。本文首先资述了目前外据掘技资在象数挖国内数挖气 资料分析中的究和资用资研状,资述了据掘技资资用于象资料分析中取数挖气得的成果和不足。其次,资包资市资资3年逐小资的象据建立多资据集气数数, 利用据洗、据集成、据资资和据消四资主要的据资理方法资数清数数数减数气数数象资料多资据集资行据资资理,以提高据掘资象的资量数挖,最资并达到提高据掘所资模式、知资、资资等资量的。然后数挖,本文主要究了以下研四资主要的据掘技资在象资料分析中的资用数挖气:利用孤立点分析技资 分析象资料资中出资的常资资集气异,资掘了一些常象资度资和常资资集异气异; 采用策资模型建立了降雨资资模型和资染因子资度资是否超资模型决,掘出挖了资如在何资象件下气条,资染物的资度超资等资资资资会;采用聚资分析资象资气 料资行分资,以便于资资各资象特征气,提出了一资基于资资廓的资次聚资方法,并 利用基于资资廓的资次聚资方法资象据资行了聚资分析气数,资明了算法... 【英文摘要】The capacity and field of meteorological data are growing and expanding rapidly as time goes by, forming Data Mountains
利用sklearn做文本分类(特征提取、knnsvm聚类) 数据挖掘入门与实战公众号：datadw 分为以下几个过程： 加载数据集 提feature 分类 Naive Bayes KNN SVM聚类 20newsgroups官网 https://www.doczj.com/doc/e517245481.html,/~jason/20Newsgroups/ 上给出了3个数据集，这里我们用最原始的 20news-19997.tar.gz https://www.doczj.com/doc/e517245481.html,/~jason/20Newsgroups/20news-19997.ta r.gz 1.加载数据集 从20news-19997.tar.gz下载数据集，解压到 scikit_learn_data文件夹下，加载数据，详见code注释。
[python]view plaincopy #first extract the 20 news_group dataset to /scikit_learn_data fromsklearn.datasets importfetch_20newsgroups #all categories #newsgroup_train = fetch_20newsgroups(subset='train') #part categories categories = ['comp.graphics', 'comp.os.ms-windows.misc', 'comp.sys.ibm.pc.hardware', 'comp.sys.mac.hardware', 'comp.windows.x']; newsgroup_train = fetch_20newsgroups(subset = 'train',categories = categories); 可以检验是否load好了： [python]view plaincopy #print category names frompprint importpprint pprint(list(newsgroup_train.target_names))
分类(classification )： 它找出描述并区分数据类或概念的模型(或函数)，以便能够使用模型预测类标记未知的对象类。分类分析在数据挖掘中是一项比较重要的任务, 目前在商业上应用最多。分类的目的是学会一个分类函数或分类模型(也常常称作分类器),该模型能把数据库中的数据项映射到给定类别中的某一个类中。分类和回归都可用于预测，两者的目的都是从历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行预测。与回归不同的是，分类的输出是离散的类别值，而回归的输出是连续数值。二者常表现为决策树的形式，根据数据值从树根开始搜索，沿着数据满足的分支往上走，走到树叶就能确定类别。要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据库记录或元组构成，每个元组是一个由有关字段(又称属性或特征)值组成的特征向量，此外，训练样本还有一个类别标记。一个具体样本的形式可表示为：（v1,v2,...,vn; c)；其中vi表示字段值，c表示类别。分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。不同的分类器有不同的特点。有三种分类器评价或比较尺度：1)预测准确度；2)计算复杂度；3)模型描述的简洁度。预测准确度是用得最多的一种比较尺度，特别是对于预测型分类任务。计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据，因此空间和时间的复杂度问题将是非常重要的一个环节。对于描述型的分类任务，模型描述越简洁越受欢迎。另外要注意的是，分类的效果一般和数据的特点有关，有的数据噪声大，有的有空缺值，有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数据。 聚类(clustering)： 是指根据“物以类聚”的原理，将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合叫做簇，并且对每一个这样的簇进行描述的过程。它的目的是使得属于同一个簇的样本之间应该彼此相似，而不同簇的样本应该足够不相似。与分类规则不同，进行聚类前并不知道将要划分成几个组和什么样的组，也不知道根据哪些空间区分规则来定义组。其目的旨在发现空间实体的属性间的函数关系，挖掘的知识用以属性名为变量的数学方程来表示。当前，聚类技术正在蓬勃发展，涉及范围包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销等领域，聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。常见的聚类算法包括：K-均值聚类算法、K-中心点聚类算法、CLARANS、BIRCH、CLIQUE、DBSCAN等。
聚类分析与排列分析的原理和应用 植物学专业zw 引言 20世纪90年代以来，随着数据库和信息技术的发展，由于互联网技术的普及和企业、个人数据的积累，我们可以轻松的获取并存储大量的重要数据。但是如何对我们所感兴趣的数据信息进行提取和分析，这就迫切需要一种新的数据提取软件，它能够自动地、快速地、智能地把历史数据归纳成为有指导意义的信息。而数据挖掘技术具有较强的数据处理能力（刘同明等，2001）。聚类分析就是数据挖掘技术的一种。 聚类分析是统计学的一项分支，并且逐渐形成了一个系统的体系（Everitt et al,2001）。目前，聚类分析主要应用于两个领域，一个是模式识别领域，另外一个便是数据挖掘领域。近年来，聚类分析技术已经逐渐成为数据挖掘应用中的一个富有生命力的研究方向。我们面对海量数据的时候，首先必须要做的就是对它进行归类，对原始数据进行归类的一种方法就是聚类分析法，它是将抽象的或者物理的数据，根据它们之间的相近程度，分为若干个类别，并且使得同一个组内数据具有比较高的相似度，而相异组的对象数据关联距离较大。聚类分析的应用十分广泛（刘艳霞等，2008），在生物学领域里，聚类分析可以推导动植物的分类，基因的分类分析，获得对种群中固有结构的认识。在商务市场领域，聚类分析可以帮助市场分析工程师从客户的基本信息库中发现不同的客户群体，针对不同的客户群，制定不同的
购买模式，从而可以使利益最大化。在模式识别中，聚类可以用于语音识别、字符识别、雷达信号识别、文本识别等方面。聚类分析方法还可以应用于机器自动化和工具状态检测，以及进行气候分类、食品检验和水质分析，另外，数据挖掘中的聚类分析的一个重要功能是仅仅用聚类分析构成算法工具来描述、分析数据，并且概括其分布。另外，聚类分析也可以作为其他数据挖掘方法的预处理步骤。因此，在广泛的应用领域中，聚类方法起着非常重要的作用。 聚类分析原理和应用 聚类就是抽象的或者物理的数据，依据它们的相似性或者相似程度，将其分为若干组，同一组内的成员具有高度的相似性质，聚类就是具有相似特性的对象的集合，跟平常说的“物以类聚”相似（方开泰等，1982）。聚类分析就是使用聚类算法来发现有意义的类，主要依据是把相似的样本划分为一类，而把差异大的样本区分开来，这样所生成的簇是一组数据对象的集合，这些对象与同一簇中的对象彼此相似，而与其他簇的对象彼此相异。在应用中经常把一个簇中的数据对象当成一个整体来对待（罗可等，2003）。簇：一个数据对象的集合。在同一簇中，对象具有相似性，不同簇中，对象之间是相异的。 聚类分析(Clustering analysis)：把一个给定的数据对象集合分成不同的簇,即在空间X 中给定一个有限的取样点集或从数据库中取得有限个例子的集合，{X i}n i=1。聚类的目标是将数据聚集成类，使得类间的相似性最小，而类内的相似性尽可能得大。 聚类的数据描述为：
关键词共词分析、聚类分析和多维尺度分析 功能： 1、寻找近几年研究热点（热点图），为论文的选题做准备 2、直接为论文服务 方法举例： 关键词：自闭症 研究工具：Bicomb共词分析软件、、excel、中国知网（CNKI） 研究进程： A：中国知网（官网）-左上“资源总库”-左上“中国学术期刊网络出版总库” 主题：自闭症，年限范围：2000-2014，来源类别：全选-检索 每页显示：50-一页页全选后再删除一定不要研究的文献-尽量多选择文献（最好全部） 导出/参考文献-全选-导出-自定义（支持需输出更多文献信息）-全选-导出-保存-txt 打开txt-编辑-全部替换（前面英文删除）-另存为txt-编码：ANSI【多操作几遍，不然提取不出来或会出现00000，而不是00000,00001,00002等】 B：书目共现分析系统-增加（右上角）-项目编号：1-格式类型：cnki中文txt-提取-选择文档-关键字段：关键词-提取（红色）-统计-关键字：关键词-∑统计-矩阵-关键字：关键词-≥5≤280-词篇矩阵-生成-导出至txt-保存 C：打开SPSS-文件-打开文本数据-下一步-删除第一行-度量标准：“名义”变为“度量”-分析-分类-系统聚类-V1标准个案-V2到Vn变量-统计量：选择“合并进程表”“相似性矩阵”-绘制：树状图-方法（二分类-Ochiai）-结果：近似矩阵（最大的表格）导出到excel-多维尺度分析【树状图如果是虚线，可能是spss版本问题或其他问题】 D：SPSS-excel导入-打开数据-excel-删除第一行-删除1：、2：、3：、4：、5：、、、-复制粘贴到变量视图-度量标准：“名义”变为“度量”-字符串变为数值【第一个分类不要改字符串】-分析-度量-多维尺度最后一个ALSCAL-变量移动-从数据创建距离-度量（E）-标准化：Z 得分-选项：组图
SPSS聚类分析过程 聚类的主要过程一般可分为如下四个步骤： 1.数据预处理（标准化） 2.构造关系矩阵（亲疏关系的描述） 3.聚类（根据不同方法进行分类） 4.确定最佳分类（类别数） SPSS软件聚类步骤 1. 数据预处理（标准化） →Analyze(分析) →Classify (分类，归类)→Hierachical Cluster Analysis（层序聚类分析）→Method（方法，条理，）然后从对话框中进行如下选择 从Transform Values框中点击向下箭头，此为标准化方法，将出现如下可选项，从中选一即可： 标准化方法解释：None：不进行标准化，这是系统默认值；Z Scores（Z-Scores, 英文名又叫Standardized Population Data, 是以标准差单位来表现的一组观察值）：标准化变换；Range –1 to 1：极差标准化变换（作用：变换后的数据均值为0，极差为1，且|x ij*|<1，消去了量纲的影响；在以后的分析计算中可以减少误差的产生。）；Range 0 to 1（极差正规化变换 / 规格化变换）； 2. 构造关系矩阵 在SPSS中如何选择测度（相似性统计量）: →Analyze →Classify →Hierachical Cluster Analysis →Method 然后从对话框中进行如下选择 常用测度（选项说明）：Euclidean distance：欧氏距离（二阶Minkowski距离），用途：聚类分析中用得最广泛的距离；Squared Eucidean distance：平方欧氏距离；Cosine：夹角余弦(相似性测度；Pearson correlation：皮尔逊相关系数； 3. 选择聚类方法
系统聚类分析方法 聚类分析是研究多要素事物分类问题的数量方法。基本原理是根据样本自身的属性，用数学方法按照某种相似性或差异性指标，定量地确定样本之间的亲疏关系，并按这种亲疏关系程度对样本进行聚类。 常见的聚类分析方法有系统聚类法、动态聚类法和模糊聚类法等。 1. 聚类要素的数据处理 假设有m 个聚类的对象，每一个聚类对象都有个要素构成。它们所对应的要素数据可用表3.4.1给出。（点击显示该表）在聚类分析中，常用的聚类要素的数据处理方法有如下几种。 ①总和标准化 ②标准差标准化
③极大值标准化 经过这种标准化所得的新数据，各要素的极大值为1，其余各数值小于1。 ④极差的标准化 经过这种标准化所得的新数据，各要素的极大值为1，极小值为0，其余的数值均在0与1之间。 2. 距离的计算 距离是事物之间差异性的测度，差异性越大，则相似性越小，所以距离是系统聚类分析的依据和基础。 ①绝对值距离
选择不同的距离，聚类结果会有所差异。在地理分区和分类研究中，往往采用几种距离进行计算、对比，选择一种较为合适的距离进行聚类。
例：表3.4.2给出了某地区九个农业区的七项指标，它们经过极差标准化处理后，如表3.4.3所示。 对于表3.4.3中的数据，用绝对值距离公式计算可得九个农业区之间的绝对值距离矩阵：
3. 直接聚类法 直接聚类法是根据距离矩阵的结构一次并类得到结果。 ▲ 基本步骤： ①把各个分类对象单独视为一类； ②根据距离最小的原则，依次选出一对分类对象，并成新类；③如果其中一个分类对象已归于一类，则把另一个也归入该类；如果一对分类对象正好属于已归的两类，则把这两类并为一类；每一次归并，都划去该对象所在的列与列序相同的行；④那么，经过m-1次就可以把全部分类对象归为一类，这样就可以根据归并的先后顺序作出聚类谱系图。 ★直接聚类法虽然简便，但在归并过程中是划去行和列的，因而难免有信息损失。因此，直接聚类法并不是最好的系统聚类方法。 [举例说明]（点击打开新窗口，显示该内容） 例：已知九个农业区之间的绝对值距离矩阵，使用直接聚类法做聚类分析。 解： 根据上面的距离矩阵，用直接聚类法聚类分析：
数据挖掘结课报告 学院：专业：学号：姓名： 摘要：数据挖掘（Data Mining）是利用一种或多种计算机学习技术，从数据中自动分析并提取信息的处理过程。数据挖掘的目的是寻找和发掘数据中潜在的有价值的信息、知识、规律、联系和模式。它是当前热门的、具有广阔商业应用前景的一个研究领域。本文笔者结合专业所学，简单介绍了数据挖掘在本专业应用。并做了数据挖掘试验工作，分析了相应结果。 关键词：数据挖掘；地球物理；分类预测；聚类分析；关联规则 §1 介绍 国内外的数据挖掘技术的应用研究，均只是从数据驱动的角度实施挖掘过程，而忽略了领域专家的所具有的专业背景知识，缺乏人机交互机制。因此，根据各种地球物理勘探数据的特征，从勘探领域模型驱动的角度出发，引入数据挖掘技术，确定其挖掘思路，建立各种挖掘方法之间的联系，利用其数学模型和数学分析方法从海量的数中获得最大增益信息来指导勘探，不仅是数据的需要，更重要的是为地球物理勘探提供了一种高效率、高精度、低成本、高回报的新方法[1]。在国内，部分学者将数据挖掘这门新方法在地球物理应用领域进行了积极探索[1-3]。李雄炎等[1](2009)在石油天然气勘探领域进行了数据挖掘应用探索。朱传华等[3](2010)应用数据挖掘技术，从滑坡灾害历史数据中挖掘出有利于滑坡灾害预测预报的有效信息，为预警指挥系统服务。可以说，数据挖掘在地球物理方面的应用前景较好，但需要国内外学者进一步探索，发挥交叉学科作用，使数据挖掘可以服务于地球物理领域。本文仅利用老师提供的非地球物理资料样本，操作weka进行一些简单实验，熟悉数据挖掘方法。 §2实验 2.1 分类预测 分类是以寻找一个分类函数或者建立一个分类模型为目的[4-6]。其中决策树算法则是数据挖掘领域中研究分类问题最常见的方法，本文将以J48(C4.5)和Naive Bayes为例进行试验，本次实验笔者选择的数据样本均为zoo.arff，结果如下图1所示。
一文全面了解分类分析和聚类分析 当我们面对大量数据的时候，总试图将大量的数据进行划分，然后依次划分的数据群组进行分析，而分类和聚类就是我们常用的两种数据划分技术。在我们的应用中，我们常常没有过多的去区分这两个概念，觉得聚类就是分类，分类也差不多就是聚类。然而这两者之间有着本质的区别，接下来，我们就具体来探讨下分类与聚类之间在数据挖掘中的区别。 所谓分类(Classification)，就是按照某种标准给对象贴标签(label)，再根据标签来区分归类；而聚类，则是在是指事先没有“标签”的情况下，通过某种聚集分析，找出事物之间存在聚集性原因的过程。 从机器学习上看，分类作为一种监督学习方法，它的目标在于通过已有数据的确定类别，学习得到一个分类函数或分类模型(也常常称作分类器)，该模型能把数据库中的数据项映射到给定类别中的某一个类中。简单的说，就是我们在进行分类前，得到的数据已经标示了数据所属的类别，分类的目标就是得到一个分类的标准，使得我们能够更好的把不同类别的数据区分出来。就如下图所示，分类分析的目的就是要找出区分红色数据和绿色数据的标准，分类分析的过程就是算法不断递进，使得标准更为准确的过程。 图：分类分析的过程 与分类技术不同，在机器学习中，聚类是一种无指导学习。即聚类是在预先不知道分类的情况下，根据信息相似度原则进行信息聚类的一种方法。聚类的目的是将大量的数据通过“属于同类别的对象之间的差别尽可能的小，而不同类别上的对象的差别尽可能的大”的原则进行分类；因此，聚类的意义就在于将观察到的内容组织成类分层结构，把类似的事物组
织在一起。通过聚类分析，人们能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间的有趣的关系。 图：聚类分析的过程 分类作为一种监督学习方法，要求必须事先明确知道各个类别的信息，并且断言所有待分类项都有一个类别与之对应。但是很多时候，我们在进行数据分析的时候，事前并不能得到各个类别的信息。那么在这个时候，我们就需要使用聚类分析的方法，通过聚类分析，将数据进行分类，去识别全局的分布模式，更好的去探索不同类别数据属性之间的区别和联系，从而找到数据的区分标识，并以此来进行更好的数据分类分析工作。
摘要 聚类作为一种知识发现的重要方法，它广泛地与中文信息处理技术相结合，应用于网络信息处理中以满足用户快捷地从互联网获得自己需要的信息资源。文本聚类是聚类问题在文本挖掘中的有效应用，它根据文本数据的不同特征，按照文本间的相似性，将其分为不同的文本簇。其目的是要使同一类别的文本间的相似度尽可能大，而不同类别的文本间的相似度尽可能的小。整个聚类过程无需指导，事先对数据结构未知，是一种典型的无监督分类。 本文首先介绍了文本聚类的相关的技术，包括文本聚类的过程，文本表示模型，相似度计算及常见聚类算法。本文主要研究的聚类主要方法是k-均值和SOM 算法，介绍了两种算法的基本思想和实现步骤，并分析两种算法的聚类效果。同时介绍了两种算法的改进算法。 关键词：文本聚类聚类方法K-MEAN SOM
Abstract Clustering as an important knowledge discovery method, which extensively with Chinese information processing technology, used in network information processing to meet the users to quickly access from the Internet, the information resources they need. Text clustering is a clustering problem in the effective application of text mining, which according to the different characteristics of text data, according to the similarity between the text, the text will be divided into different clusters. The aim is to make the same class as large as possible the similarity between the text, and different types of text as small as possible the similarity between. The clustering process without guidance, prior to the data structure is unknown, is a typical unsupervised classification. This paper studies the effect of influencing factors that text clustering, text representation of the model such as the Boolean model, vector space model, probabilistic retrieval model and language model. Also studied the analysis of such text clustering algorithm: hierarchical clustering, agglomerative hierarchical clustering algorithm, hierarchical clustering algorithm to split and so on. Also studied the text clustering algorithm analysis and methods of improvement. Key words：Text clustering clustering method k-mean som