第五章聚类分析.ppt

在已知类别的样本集基础上，用确定的或统计的判别函数对模式进行分类，设计分类器，这些已知的样本集称为训练集。根据判读好的训练集解决分类问题，称为有人管理或有教师的分类法。 第五章 聚类分析 没有训练集的情况下的样本分类问题，所选用的样本是预先不知其所属的类别，需要根据样本间的距离或相似性的程度自动地进行分类。 这种无人参预（或没有教师的）识别问题，称为聚类或无人管理的分类。 聚类分析方法是决定描述一个经验数据集的结构类型的一种非参数方法。 相似的数据被集中在一起，从数据集中分离出来，包含在特征空间中的一个模式集，其模式的密度比起周围区域中的密度大，就为一个聚类。 聚类原则：根据样本集，找出各点内在的相似性进行分类，相似的分为一类。 ⑴直观的相似性：从几何距离考虑，设阈值T，它是相似性度量的标准，靠经验确定，对分类影响很大。可用于粗分。 ⑵样本集群性（紧致性）：同一类的应该群集，不同类的应该远离。 ⑶特征空间量纲标尺的选择：量纲选择不同，分类也有差异。 为了克服这个缺点，常使特征数据标准化，使它与变量量纲标尺没有关系。 5.1相似性度量和聚类准则 一般用归并相似的模式和分开不相似的模式以形成聚类。 相似性归并是聚类最普通的形式。 各式各样的相似性和距离度量已经作为特征空间中模式样本的聚类准则。 5.1.1相似性度量(Similarity measure) 相似性度量将建立一个把模式分到一聚类中心域的原则。 ⒈欧氏距离(Euclidean distance)(常用) 对两个样本xi和xj，其欧氏距离定义为 加权欧氏距离也是一种常用的相似性度量。 wk是系数，其重要，wk大； 次要的，wk小。 ⒉马氏距离(Mahalanobis distance)(不常用) x是待识别样本，m是均值向量，∑是协方差矩阵。若∑为单位阵，则马氏距离与欧氏距离相似。 马氏距离的优点是排除了模式样本之间的相关性的影响。例如取一个模式特征向量，可能其中九个分量是反映同一特征A，而只有一个分量反映另一特征B，这时如用欧氏距离计算，主要反映了特征A，而用马氏距离则可避免这个缺点。 ⒊明氏距离(Minkowsky distance) m = 2时为欧氏距离； m = 1为绝对距离(用绝对值)； dij = |xi1－xj1| + … + | xid－xjd | 相似性度量不一定只限于距离，可以是下面的形式： ⒋角度相似性度量函数 sij是向量xi和xj之间夹角的余弦，当xi和xj相对于原点是同一方向时，函数值最大。 当聚类区域有扇形分布时往往采用这种相似性度量。如图5.1所示。 距离和角度相似性函数作为相似性的测度各有其局限性。 距离对于坐标系的旋转和位移是不变的，对于放大缩小并不具有不变性的性质。 角度相似性函数对于坐标系的旋转放大缩小是不变的，但对于位移不具有不变性的性质。 用角度相似性函数作为相似性的测度还有一个缺点，当本属不同类的样本分布在从模式空间原点出发的一条直线上时，所有样本之间角度相似性函数几乎都等于l，造成归为一类的错误。 ⒌Tanimoto 度量(常用) 若模式向量取二进制值0，1时有特殊意义，样本x具有第k个特征，xiTxj是两者共同的特征数； ⒌Tanimoto 度量(常用) 适用于疾病诊断、动植物分类和情报检索等方面。 上述介绍的相似性量度不是仅有的形式，而是属于比较简单和典型的。 距离函数应满足三个条件： ⑴非负性：对于一切i，j，dij(xi，xj)≥0，当xi = xj时，等号成立。 ⑵对称性：对于一切i，j，dij(xi，xj) = dji(xj，xi)，即距离是标量而不是向量。 ⑶三角不等式：dij(xi，xj) ≤ djk(xj，xk)+ dkj(xk，xj)，即相当于三角形两边之和必大于第三边。 5.1.2 聚类准则 假定有一组样本{x1，x2，…，xN}，要求对其进行确切分成ω1，ω2，…，ωc类。 同一类里的样本比不同类里的样本相似性高一些，于是可存在多种分类，到底何种分类方法最好？ 需要定义一个准则函数，则聚类问题就变成对准则函数求极值的问题。 ⒈试探方式： 针对具体的实际问题，定义一种相似性度量的阈值T，按最近邻原则分类，须不断检验、修正阈值T。 这种方法的误判率受T及起始样本影响。 ⒉误差平方和准则(最小方差划分)(常用) 误差平方和准则是聚类问题中最简单而又广泛应用的准则。 准则函数为 ⒉误差平方和准则(最小方差划分) 此种准则函数适用于集群性好，且各类容积相近情况。 如果类间距离小，容积相差悬殊，容易发生错误。 ⒉误差平方和准则(最小方差划分) 如图 (a)中所示的模式分类，使用这种准则进行聚类可获得最好的效果。 ⒉误差平方和准则(最小方差划分) 而如图 (b)