知识探勘的利器-丛集算法（2）.pdfVIP

知识探勘的利器一丛集算法(2) ◆ 钟庆丰 以下我们将为各位介绍一下这些方法之间的特性与应 并条件要满足： 用情形。 3．三角不等式 (triangle inequality) 对所有X．、X。及Xk而言．满足[S(X．．X。)4-S(X。．X k)】 距离与相似度的量测 S(X．．Xk)≥ S(X．，X。)S(X。．Xk) 4．反射性 (reflexivity) 相似度的测量对于分类对象具有很重要的意义 (例 唯且若唯X．=×。．S(X．．X。)=1。 如：对于对象辨识、对象搜寻…等)．因为这是计算机视 对一个有N个输入模式 (input pattern)之数据集而言． 觉里面的辨识工作．也是人工视觉智能发展的重要一环。 我们可以定义一个N X N的对称矩阵 (我们一般称为 ”邻 但要讨论相似度之前．我们必须先了解要测量的相似标准 近矩阵 (proximity matrix)“)．并以第(i．j)个元素代表 为何以及要如何测量。而要回答这些问题．我们必须对何 所要表示的第i个及第j个模式 ( ， 1．…．N)的表现相似 谓 ”对象 (objects)”有更深刻的定义认识。这的确是一件 度或是相异度。典型的距离函数 (distance functions)通 不容易的事情．因为数据对象的定义会因为运作环境及应 常被用以测量连续特征．对定性 (qualitative)变量而言， 用种类之差异而略有不同。 其 ”相似度的测量 通常具有更重要的角色。测量方法的 在此．我们暂时就将数据对象理解为 一个拥有一连 选择与所要解决的问题有关，例如：对一个具有二元特征 串特征 (features)的一个集合体“之概念．并通常以多维 (binary features)的数据而言．其常先使用相似度之测量： 向量 (multidimensional vectors)作为该对象之表现方式。 有了相似度之数据后，相异度之测量便是全部成分减去相 对于要描述一个数据对象之特征．可以采定性方式或定量 似度的部分之后所得之剩余部分 (即是D．。=1一s．．)。为了 方式．或以连续变量概念或是二元变量概念等为之。但不 方便说明．我们以两个二元下标来表示一个对象特征．并 管用哪一种方式定义特征．其主要的功能都在于提供一个 以f。。与f，，来表示同时在~tL--物中所 ”同时欠缺”或 ”同时 可对应的测量机制。站在测量的观点上．我们常以距离作 表现”之特征 (换句话说，没有同时欠缺或表现的特征即 为相异度 (dissimilarity)的一种同义词。 用f 。或f 表示)。让我们考虑两个数据点X．与X。．其常见的 换言之．一个数据集X的相异度 (即距离差异)定义应 相似度测量型态使以公示来表示。但在此要注意的是 系 满足两个基本条件．一个是对称性 (symmetry)．另一个 数的数值代表不同意义．其中当 =1时．其表示 是一 正数性 (positivity)。即是D cX．．X )=D cX。．X．)与对所有X．、 种简单的matching系数；当 =2时．则表示此为Roger及 ×。而言．满足D(X．．X。)／0性质。且如果条件满足： Tanimoto测量；当 =1／2时．则表示此为Gower及Legendre 1．三，II不等式 (triangle inequality) 测量。这些测量是直接计算两物体间的吻合程度．未吻合 对所有X，、X 及×k而言．满足D(X．．X )+D(X ，X。)≥ 的部分则会基于他们的相似情况再另做加权处