相似性和相异性的度量
相似性和相异性是重要的概念，因为它们被许多数据挖掘技术所使用，如聚类、最近邻分类和异常检测等。在许多情况下，一旦计算出相似性或相异性，就不再需要原始数据了。这种方法可以看作将数据变换到相似性（相异性）空间，然后进行分析。
首先，我们讨论基本要素--相似性和相异性的高层定义，并讨论它们之间的联系。为方便起见，我们使用术语邻近度（proximity）表示相似性或相异性。由于两个对象之间的邻近度是两个对象对应属性之间的邻近度的函数，因此我们首先介绍如何度量仅包含一个简单属性的对象之间的邻近度，然后考虑具有多个属性的对象的邻近度度量。这包括相关和欧几里得距离度量，以及Jaccard和余弦相似性度量。前二者适用于时间序列这样的稠密数据或二维点，后二者适用于像文档这样的稀疏数据。接下来，我们考虑与邻近度度量相关的若干重要问题。本节最后简略讨论如何选择正确的邻近度度量。
1)基础
1. 定义
两个对象之间的相似度（similarity）的非正式定义是这两个对象相似程度的数值度量。因而，两个对象越相似，它们的相似度就越高。通常，相似度是非负的，并常常在0（不相似）和1（完全相似）之间取值。
两个对象之间的相异度（dissimilarity）是这两个对象差异程度的数值度量。对象越类似，它们的相异度就越低。通常，术语距离（distance）用作相异度的同义词，正如我们将介绍的，距离常常用来表示特定类型的相异度。有时，相异度在区间[0, 1]中取值，但是相异度在0和之间取值也很常见。
2. 变换
通常使用变换把相似度转换成相异度或相反，或者把邻近度变换到一个特定区间，如[0, 1]。例如，我们可能有相似度，其值域从1到10，但是我们打算使用的特定算法或软件包只能处理相异度，或只能处理[0, 1]区间的相似度。之所以在这里讨论这些问题，是因为在稍后讨论邻近度时，我们将使用这种变换。此外，这些问题相对独立于特定的邻近度度量。
通常，邻近度度量（特别是相似度）被定义为或变换到区间[0, 1]中的值。这样做的动机是使用一种适当的尺度，由邻近度的值表明两个对象之间的相似（或相异）程度。这种变换通常是比较直截了当的。例如，如果对象之间的相似度在1（一点也不相似）和10（完全相似）之间变化，则我们可以使用
如下变换将它变换到[0, 1]区间：s' = (s-1)/9，其中s和s'分别是相似度的原值和新值。一般来说，相似度到[0, 1]区间的变换由如下表达式给出：s'=(s-min_s) / (max_s - min_s)，其中max_s和min_s分别是相似度的最大值和最小值。类似地，具有有限值域的相异度也能用d' = (d - min_d) / (max_d - min_d) 映射到[0, 1]区间。
然而，将邻近度映射到[0, 1]区间可能非常复杂。例如，如果邻近度度量原来在区间[0 1000]上取值，则需要使用非线性变换，并且在新的尺度上，值之间不再具有相同的联系。对于从0变化到1000的相异度度量，考虑变换d' = d / (1 + d)，相异度0、、2、10、100和1000分别被变换到0、、、、和。在原来相异性尺度上较大的值被压缩到1附近，但是否希望如此则取决于应用。另一个问题是邻近度度量的含义可能会被改变。例如，相关性（稍后讨论）是一种相似性度量，在区间[ -1, 1]上取值，通过取绝对值将这些值映射到[0, 1]区间丢失了符号信息，而对于某些应用，符号信息可能是重要的。
将相似度变换成相异度或相反也是比较直截了当的，尽管我们可能再次面临保持度量的含义问题和将线性尺度改变成非线性尺度的问题。如果相似度（相异度）落在[0, 1]区间，则相异度（相似度）可以定义为d = 1 - s（或s = 1 - d）。另一种简单的方法是定义相似度为负的相异度（或相反）。例如，相异度0，1，10和100可以分别变换成相似度0,- 1,- 10和- 100。
负变换产生的相似度结果不必局限于[0, 1]区间，但是，如果希望的话，则可以使用变换
s = 1/(d + 1)，。对于变换s = 1/(d + 1)，相异度0, 1, 10, 100分别被变换到1, , , ；对于，它们分别被
变换到, , , ；对于s =，它们分别被变换到, , , 。在
这里的讨论中，我们关注将相异度变换到相似度。
一般来说，任何单调减函数都可以用来将相异度转换到相似度（或相反）。当然，在将相似度变换到相异度（或相反），或者在将邻近度的值变换到新的尺度时，也必须考虑一些其他因素。我们提到过一些问题，涉及保持意义、扰乱标度和数据分析工具的需要，但是肯定还有其他问题。
2) 简单属性之间的相似度和相异度
通常，具有若干属性的对象之间的邻近度用单个属性的邻近度的组合来定义，因此我们首先讨论具有单个属性的对象之间的邻近度。考虑由一个标称属性描述的对象，对于两个这样的对象，相似意味什么呢由于标称属性只携带了对象的相异性信息，因此我们只能说两个对象有相同的值，或者没有。因而在这种情况下，如果属性值匹配，则相似度定义为1，否则为0；相异度用相反的方法定义：如果属性值匹配，相异度为0，否则为1。
对于具有单个序数属性的对象，情况更为复杂，因为必须考虑序信息。考虑一个在标度{poor, fair, OK, good, wonderful}上测量产品（例如，糖块）质量的属性。一个评定为wonderful的产品P1与一个评定为good的产品P2应当比它与一个评定为OK的产品P3更接近。为了量化这种观察，序数属性的值常常映射到从0或1开始的相继整数，例如，{poor = 0, fair =1, OK = 2, good = 3, wonderful = 4}。于是，P1与P2之间的相异度d(P1, P2) = 3-2 = 1，或者，如果我们希望相异度在0和1之间取值，d(P1, P2) = (3-2)/4 = ；序数属性的相似度可以定义为s = 1-d。
序数属性相似度（相异度）的这种定义可能使读者感到有点担心，因为这里我们定义了相等的区间，而事实并非如此。如果根据实际情况，我们应该计算出区间或比率属性。值fair与good的差真和OK与wonderful的差相同吗可能不相同，但是在实践中，我们的选择是有限的，并且在缺乏更多信息的情况下，这是定义序数属性之间邻近度的标准方法。
对于区间或比率属性，两个对象之间的相异性的自然度量是它们的值之差的绝对值。例如，我们可能将现在的体重与一年前的体重相比较，说"我重了10磅。"在这类情况下，相异度通常在0和x之间，而不是在0和1之间取值。如前所述，区间或比率属性的相似度通常转换成相异度。
表2-7总结了这些讨论。在该表中，x和y是两个对象，它们具有一个指明类型的属性，d(x, y)和s(x, y)分别是x和y之间的相异度和相似度（分别用d和s表示）。其他方法也是可能的，但是表中的这些是最常用的。
下面两节介绍更复杂的涉及多个属性的对象之间的邻近性度量：(1)数据对象之间的相异度；(2)数据对象之间的相似度。这样分节可以更自然地展示使用各种邻近度度量的基本动机。然而，我们要强调的是使用上述技术，相似度可以变换成相异度，反之亦然。
3) 数据对象之间的相异度
本节，我们讨论各种不同类型的相异度。我们从讨论距离（距离是具有特定性质的相异度）开始，然后给出一些更一般的相异度类型的例子。
距离
我们首先给出一些例子，然后使用距离的常见性质更正式地介绍距离。一维、二维、三维或高维空间中两个点x和y之间的欧几里得距离（Euclidean distance）d由如下熟悉的公式定义：
其中，n是维数，而xk和yk分别是x和y的第k个属性值（分量）。我们用图2-15、表2-8和表2-9解释该公式，它们展示了这个点集、这些点的x和y 坐标以及包含这些点之间距离的距离矩阵（distance matrix）。
公式（2-1）给出的欧几里得距离可以用公式（2-2）的闵可夫斯基距离（Minkowski distance）来推广：
其中r是参数。下面是闵可夫斯基距离的三个最常见的例子。
r = 1，城市街区（也称曼哈顿、出租车、L1范数）距离。一个常见的例子是
汉明距离（Hamming distance），它是两个具有二元属性的对象（即两个二元向量）之间不同的二进制位个数。
r = 2，欧几里得距离（L2范数）。
r =，上确界（Lmax或L 范数）距离。这是对象属性之间的最大距离。更
注意不要将参数r与维数（属性数）n混淆。欧几里得距离、曼哈顿距离
和上确界距离是对n的所有值（1, 2, 3,...）定义的，并且指定了将每个维（属性）上的差的组合成总距离的不同方法。
表2-10和表2-11分别给出表2-8数据的L1距离和L 距离的邻近度矩
阵。注意，所有的距离矩阵都是对称的，即第ij个表目与第ji个表目相同，
距离（如欧几里得距离）具有一些众所周知的性质。如果d(x, y)是两个点x
和y之间的距离，则如下性质成立。
(1) 非负性。(a) 对于所有x和y，d(x, y)≥0，(b) 仅当x = y时d(x, y) =
0。
(2) 对称性。对于所有x和y，d(x, y) = d(y, x)。
(3) 三角不等式。对于所有x，y和z，d(x, z) ≤ d(x, y) + d(y, z)。
满足以上三个性质的测度称为度量（metric）。有些人只对满足这三个性质的相异性度量使用术语距离，但在实践中常常违反这一约定。这里介绍的三个性质是有用的，数学上也是令人满意的。此外，如果三角不等式成立，则该性质可以用来提高依赖于距离的技术（包括聚类）的效率。尽管如此，许多相异度都不满足一个或多个度量性质。下面我们给出两个这种测度的例子。
例1非度量的相异度：集合差。基于集合论中定义的两个集合差的概念举例。设有两个集合A和B，A-B是不在B中的A中元素的集合。例如，如果A = {1, 2, 3, 4}，而B = {2, 3, 4}，则A-B = {1}，而B-A = 空集。我们可以将两个集合A和B之间的距离定义为d(A, B) = size(A-B)，其中size是一个函数，它返回集合元素的个数。该距离测度是大于或等于零的整数值，但不满足非负性的第二部分，也不满足对称性，同时还不满足三角不等式。然而，如果将相异度修改为d(A, B) = size(A-B) + size(B-A)，则这些性质都可以成立。
例2非度量的相异度：时间。这里给出一个更常见的例子，其中相异性测度并非度量，但依然是有用的。定义时间之间的距离测度如下：
例如，d(1PM, 2PM) = 1小时，而d(2PM, 1PM) = 23小时。这种定义是有意义的，例如，在回答如下问题时就体现了这种定义的意义："如果一个事件在每天下午1点发生，现在是下午2点，那么我们还需要等待多长时间才能等到该事件再度发生"
4）数据对象之间的相似度
对于相似度，三角不等式（或类似的性质）通常不成立，但是对称性和非负性通常成立。更明确地说，如果s(x, y)是数据点x和y之间的相似度，则相似度具有如下典型性质。
(1) 仅当x = y时s(x, y) = 1。（0≤s≤1）
(2) 对于所有x和y，s(x, y) = s(y, x)。（对称性）
对于相似度，没有与三角不等式对应的一般性质。然而，有时可以将相似度简单地变换成一种度量距离。稍后讨论的余弦相似性度量和Jaccard相似性度量就是两个例子。此外，对于特定的相似性度量，还可能在两个对象相似性上导出本质上与三角不等式类似的数学约束。
例3 非对称相似性度量。考虑一个实验，实验中要求人们对屏幕上快速闪过的一小组字符进行分类。该实验的混淆矩阵（confusion matrix）记录每个字符被分类为自己的次数和被分类为另一个字符的次数。例如，假定"0"出现了200次，它被分类为"0"160次，而被分类为"o"40次。类似地，"o"出现200次并且分类为"o"170次，但是分类为"0"只有30次。如果取这些计数作为两个字符之间相似性的度量，则得到一种相似性度量，但这种相似性度量不是对称的。在这种情况下，通过选取s'(x, y) = s' (y, x) = (s(x, y) + s(y, x))/2，相似性度量可以转换成对称的，其中s'是新的相似性度量。
5) 邻近性度量的例子
本节给出一些相似性和相异性度量的具体例子。
1. 二元数据的相似性度量
两个仅包含二元属性的对象之间的相似性度量也称为相似系数（similarity coefficient），并且通常在0和1之间取值，值为1表明两个对象完全相似，而值为0表明对象一点也不相似。有许多理由表明在特定情形下，一种系数为何比另一种好。
设x和y是两个对象，都由n个二元属性组成。这样的两个对象（即两个二元向量）的比较可生成如下四个量（频率）：
f00 =x取0并且y取0的属性个数
f01 =x取0并且y取1的属性个数
f10 =x取1并且y取0的属性个数
f11 =x取1并且y取1的属性个数
简单匹配系数（Simple Matching Coefficient, SMC）,一种常用的相似性
该度量对出现和不出现都进行计数。因此，SMC可以在一个仅包含是非题的测验中用来发现回答问题相似的学生。
Jaccard系数（Jaccard Coefficient）,假定x和y是两个数据对象，代表一个事务矩阵的两行（两个事务）。如果每个非对称的二元属性对应于商店的一种商品，则1表示该商品被购买，而0表示该商品未被购买。由于未被顾客购买的商品数远大于被其购买的商品数，因而像SMC这样的相似性度量将会判定所有的事务都是类似的。这样，常常使用Jaccard系数来处理仅包含非对称的二元属性的对象。Jaccard系数通常用符号J表示，由如下等式定义：
例4 SMC和Jaccard相似性系数。为了解释这两种相似性度量之间的差别，我们对如下二元向量计算SMC和J：
x = (1, 0, 0, 0, 0, 0, 0, 0, 0, 0)
y = (0, 0, 0, 0, 0, 0, 1, 0, 0, 1)
f01 = 2 x取0并且y取1的属性个数
f10 = 1 x取1并且y取0的属性个数
f00 = 7 x取0并且y取0的属性个数
2. 余弦相似度
通常，文档用向量表示，向量的每个属性代表一个特定的词（术语）在文档中出现的频率。当然，实际情况要复杂得多，因为需要忽略常用词，并使用各种技术处理同一个词的不同形式、不同的文档长度以及不同的词频。
尽管文档具有数以百千计或数以万计的属性（词），但是每个文档向量都是稀疏的，因为它具有相对较少的非零属性值。（文档规范化并不对零词目创建非零词目，即文档规范化保持稀疏性。）这样，与事务数据一样，相似性不能依赖共享0的个数，因为任意两个文档多半都不会包含许多相同的词，从而如果统计0-0匹配，则大多数文档都与其他大部分文档非常类似。因此，文档的相似性度量不仅应当像Jaccard度量一样需要忽略0-0匹配，而且还必须能
够处理非二元向量。下面定义的余弦相似度（cosine similarity）就是文档相似性最常用的度量之一。如果x和y是两个文档向量，则
其中，" . "表示向量点积，即：
。
例5两个文档向量的余弦相似度。该例计算下面两个数据对象的余弦相似度，这些数据对象可能代表文档向量：
如图2-16所示，余弦相似度实际上是x和y之间夹角（余弦）的度量。这样，如果余弦相似度为1，则x和y之间夹角为0 ，并且除大小（长度）之外，x和y是相同的；如果余弦相似度为0，则x和y之间夹角为90 ，并且它
图2-16 余弦度量的几何解释
公式（2-7）可以写成公式（2-8）的形式：
其中， = x / || x ||，而 = y / || y ||。x和y被它们的长度除，将它们规范化成具有长度1。这意味在计算相似度时，余弦相似度不考虑两个数据对象的量值。（当量值是重要的时，欧几里得距离可能是一种更好的选择。）对于长度为1的向量，余弦度量可以通过简单地取点积计算。从而，在需要计算大量对象之间的余弦相似度时，将对象规范化，使之具有单位长度可以减少计算时间。
3. 广义Jaccard系数（Tanimoto系数）
广义Jaccard系数可以用于文档数据，并在二元属性情况下归约为Jaccard系数。广义Jaccard系数又称Tanimoto系数。（然而，还有一种系数也称Tanimoto系数。）该系数用EJ表示，由下式定义：
4. 相关性
两个具有二元变量或连续变量的数据对象之间的相关性是对象属性之间线性联系的度量。（更一般属性之间的相关性计算可以类似地定义。）更准确地，两个数据对象x和y之间的皮尔森相关（Pearson's correlation）系数
这里我们使用标准的统计学记号和定义：
例6完全相关。相关度总是在 -1到1之间取值。相关度为1（-1）意味x
和y具有完全正（负）线性关系，即X
k = aY
k
+ b，其中a和b是常数。下面
两个x和y的值集分别给出相关度为- 1和+ 1的情况。为简单起见，第一组中取x和y的均值为0。
x = (- 3, 6, 0, 3,- 6)
y = (1,-2, 0,- 1, 2)
x = (3, 6, 0, 3, 6)
y = (1, 2, 0, 1, 2)
例7非线性关系。如果相关度为0，则两个数据对象的属性之间不存在线性关系。然而，仍然可能存在非线性关系。在下面的例子中，数据对象的属性之间
存在非线性关系y
k =x
k
^2，但是它们的相关度为0。
x = ( 3,- 2,- 1, 0, 1, 2, 3)
y = (9, 4, 1, 0, 1, 4, 9)
例8相关性可视化。通过绘制对应属性值对可以很容易地判定两个数据对象x 和y之间的相关性。图2-17给出了一些这种图，x和y具有30个属性，这些属性的值随机地产生（服从正态分布），使得x和y的相关度从 -1到1。图中每个小圆圈代表30个属性中的一个，其x坐标是x的一个属性的值，而其y坐标是y的相同属性的值。
图2-17 解释相关度从 -1到1的散布图
如果通过减去均值，然后规范化使其长度为1来变换x和y，则它们的相
关度可以通过求点积来计算。注意，这与其他情况下使用的标准化不同，在其他情况下，我们使用变换和。
Bregman散度。本节，我们简略介绍Bregman散度（Bregman
divergence），它是一族具有共同性质的邻近函数。这样，可以构造使用Bregman发散函数的一般数据挖掘算法，如聚类算法，具体的例子是K均值聚类算法。注意，本节需要向量计算方面的知识。
Bregman散度是损失或失真函数。为了理解损失函数，考虑如下情况：设x 和y是两个点，其中y是原来的点，而x是它的某个失真或近似，例如，x可能是由于添加了一些随机噪声到y上而产生的。损失函数的目的是度量用x近
似y导致的失真或损失。当然，x和y越类似，失真或损失就越小，因而Bregman散度可以用作相异性函数。
有如下正式定义。
定义：Bregman散度给定一个严格凸函数（连同一些通常满足的适度限
制），由该函数生成的Bregman散度（损失函数）D(x, y)通过下面的公式给出：
例我们使用平方欧几里得距离给出Bregman散度的一个具体例子。为了简化数学计算，我们仅限于一维。设x和y是实数，而 (t) 是实数值函数，。在此情况下，梯度归结为导数，而点积归结为乘积。例如，公式（2-12）变成公式（2-13）。
该例的图形在图2-18中给出，其中y = 1。在x = 2和x = 3上给出了Bregman散度。
图2-18 图示Bregman散度
6）邻近度计算问题
本节讨论与邻近性度量有关的一些重要问题：(1)当属性具有不同的尺度（scale）或相关时如何处理；(2)当对象包含不同类型的属性（例如，定量属性和定性属性）时如何计算对象之间的邻近度；(3)当属性具有不同的权重（即并非所有的属性都对对象的邻近度具有相等的贡献）时，如何处理邻近度计算。
1. 距离度量的标准化和相关性
距离度量的一个重要问题是当属性具有不同的值域时如何处理。（这种情况通常称作"变量具有不同的尺度。"）前面，使用欧几里得距离，基于年龄和收入两个属性来度量人之间的距离。除非这两个属性是标准化的，否则两个人之间的距离将被收入所左右。
一个相关的问题是，除值域不同外，当某些属性之间还相关时，如何计算距离。当属性相关、具有不同的值域（不同的方差）、并且数据分布近似于高斯（正态）分布时，欧几里得距离的拓广，Mahalanobis距离是有用的。具体地说，两个对象（向量）x和y之间的Mahalanobis距离定义为：
其中是数据协方差矩阵的逆。注意，协方差矩阵是这样的矩阵，它的第
ij个元素是第i个和第j个属性的协方差，由公式（2-11）定义。
例在图2-19中有1000个点，其x属性和y属性的相关度为。在椭圆长轴两端的两个大点之间的欧几里得距离为，但Mahalanobis距离仅为6。实践中，计算Mahalanobis距离的费用昂贵，但是对于其属性相关的对象来说是值得的。如果属性相对来说不相关，只是具有不同的值域，则只需要对变量进行标
图2-19 二维点的集合。两个大点代表的点之间的Mahalanobis距
离为6，它们的欧几里得距离为
2. 组合异种属性的相似度
前面的相似度定义所基于的方法都假定所有属性具有相同类型。当属性具有不同类型时，就需要更一般的方法。直截了当的方法是使用表2-7分别计算出每个属性之间的相似度，然后使用一种导致0和1之间相似度的方法组合这些相似度。总相似度一般定义为所有属性相似度的平均值。
不幸的是，如果某些属性是非对称属性，这种方法效果不好。例如，如果所有的属性都是非对称的二元属性，则相似性度量先归结为简单匹配系数--一种对于二元非对称属性并不合适的度量。处理该问题的最简单方法是：如果两个对象在非对称属性上的值都是0，则在计算对象相似度时忽略它们。类似的方法也能很好地处理遗漏值。
概括地说，算法可以有效地计算具有不同类型属性的两个对象x和y之间的相似度。修改该过程可以很轻松地处理相异度。
3. 使用权值
在前面的大部分讨论中，所有的属性在计算邻近度时都会被同等对待。但是，当某些属性对邻近度的定义比其他属性更重要时，我们并不希望这种同等对待的方式。为了处理这种情况，可以通过对每个属性的贡献加权来修改邻近度公式。
如果权的和为1，则公式（2-15）变成
7）选取正确的邻近性度量
下面是一些一般观察，可能会对你有所帮助。首先，邻近性度量的类型应当与数据类型相适应。对于许多稠密的、连续的数据，通常使用距离度量，如欧几里得距离等。连续属性之间的邻近度通常用属性值的差来表示，并且距离度量提供了一种将这些差组合到总邻近性度量的良好方法。尽管属性可能有不同的取值范围和不同的重要性，但这些问题通常都可以用前面介绍的方法处理。
对于稀疏数据，常常包含非对称的属性，通常使用忽略0-0匹配的相似性度量。从概念上讲，这反映了如下事实：对于一对复杂对象，相似度依赖于它们共同具有的性质数目，而不是依赖于它们都缺失的性质数目。在特殊的情况下，对于稀疏的、非对称的数据，大部分对象都只具有少量被属性描述的性质，因此如果考虑它们都不具有的性质的话，它们都高度相似。余弦、Jaccard 和广义Jaccard度量对于这类数据是合适的。
数据向量还有一些其他特征需要考虑。例如，假定对于比较时间序列感兴趣。如果时间序列的量值是重要的（例如，每个时间序列表示同一单位不同年份的总销售），则可以使用欧几里得距离。如果时间序列代表不同的量（例如，血压和氧消耗量），通常需要确定时间序列是否具有相同的形状，而不是相同的量值，那么相关度可能更可取（使用考虑量和级的差异的内置规范化）。
在某些情况下，为了得到合适的相似性度量，数据的变换或规范化是重要的，因为这种变换并非总能在邻近性度量中提供，例如，时间序列数据可能具有显著影响相似性的趋势或周期模式。此外，正确地计算相似度还需要考虑时间延迟。最后，两个时间序列可能只在特定的时间周期上相似，例如，气温与天然气的用量之间存在很强的联系，但是这种联系仅出现在取暖季节。
实践考虑也是重要的。有时，一种或多种邻近性度量已经在某个特定领域使用，因此，其他人已经回答了应当使用何种邻近性度量的问题；另外，所使用的软件包或聚类算法可能完全限制了选择；如果关心效率，则我们可能希望选择具有某些性质的邻近性度量，这些性质（如三角不等式）可以用来降低邻近度计算量。
然而，如果通常的实践或实践限制并未规定某种选择，则正确地选择邻近性度量可能是一项耗时的任务，需要仔细地考虑领域知识和度量使用的目的。可能需要评估许多不同的相似性度量，以确定哪些结果最有意义。
—178 — 基于数据挖掘的符号序列聚类相似度量模型 郑宏珍，初佃辉，战德臣，徐晓飞 (哈尔滨工业大学智能计算中心，264209) 摘 要：为了从消费者偏好序列中发现市场细分结构，采用数据挖掘领域中的符号序列聚类方法，提出一种符号序列聚类的研究方法和框架，给出RSM 相似性度量模型。调整RSM 模型参数，使得RSM 可以变为与编辑距离、海明距离等价的相似性度量。通过RSM 与其他序列相似性度量的比较，表明RSM 具有更强的表达相似性概念的能力。由于RSM 能够表达不同的相似性概念，从而使之能适用于不同的应用环境，并在其基础上提出自组织特征映射退火符号聚类模型，使得从消费者偏好进行市场细分结构研究的研究途径在实际应用中得以实现。 关键词：符号序列聚类；数据挖掘；相似性模型 Symbolic Sequence Clustering Regular Similarity Model Based on Data Mining ZHENG Hong-zhen, CHU Dian-hui, ZHAN De-chen, XU Xiao-fei (Intelligent Computing Center, Harbin Institute of Technology, Harbin 264209) 【Abstract 】From a consumer point of the sequence of preference, data mining is used in the field of symbolic sequence clustering methods to detect market segmentation structure. This paper proposes a symbolic sequence clustering methodology and framework, gives the similarity metric RSM model. By adjusting RSM model, parameters can be changed into RSM and edit distance, Hamming distance equivalent to the similarity metric. RSM is compared with other sequence similarity metric, and is more similar to the expression of the concept of capacity. As to express different similarity, the concept of RSM can be applied to different applications environment. Based on the SOM annealing symbol clustering model, the consumer preference for market segmentation can be studied in the structure, which means it is realized in practical application. 【Key words 】symbolic sequence clustering; data mining; similarity model 计 算 机 工 程Computer Engineering 第35卷 第1期 V ol.35 No.1 2009年1月 January 2009 ·人工智能及识别技术·文章编号：1000—3428(2009)01—0178—02文献标识码：A 中图分类号：TP391 1 概述 在经济全球化的环境下，面对瞬息万变的市场和技术发展，企业要想在国内外市场竞争中立于不败之地，必须对客户和市场需求做出快速响应。目前，通过市场调研公司或企业自身的信息系统，收集来自市场和消费者的数据相对容易，而如何理解数据反映的市场细分结构和需求规律却是相当困难的。 为解决这一问题，许多研究者选择消费者的职业、收入、年龄、性别等特征数据作为细分变量，利用统计学传统聚类方法得到市场细分结构[1-2]。在实际应用中，不同的细分变量会导致不同的市场细分结果[3]。 为此，本文从用户偏好序列数据对市场进行细分。通过对符号序列数据相似性的研究，给出一个可形式化的RSM 相似性度量模型和算法概要。该度量模型考虑了2对象之间相似与相异2个方面的因素，通过参数的调整，可以根据问题的具体性质表达不同的相似性概念。并在此基础上，将在数值型数据领域表现良好的SOM 神经网络引入到符号序列数据的聚类问题上，给特征符号序列的机器自动识别提供了可能性。 2 符号序列聚类问题 序列聚类问题作为发现知识的一种重要的探索性技术，受到数据挖掘与知识发现研究领域的极大重视。企业决策者在进行市场和产品相关战略时，迫切需要某些技术手段来理解序列数据，这也正是本文研究的序列聚类问题的工程背景。 下面给出符号序列的相关定义。 定义1 设12{,,,}n A a a a ="为有限符号表，A 中的l 个符号12,,,l a a a "构成的有序集称为符号序列，记为s = 12{,,,}l a a a "，并称l 是s 的长度，记为s 。A 上所有有限长 度符号序列集合记为A *。例如：符号表{a , b , c , d , e , f , g }，则
相似性和相异性的度量 相似性和相异性是重要的概念，因为它们被许多数据挖掘技术所使用，如聚类、最近邻分类和异常检测等。在许多情况下，一旦计算出相似性或相异性，就不再需要原始数据了。这种方法可以看作将数据变换到相似性（相异性）空间，然后进行分析。 首先，我们讨论基本要素--相似性和相异性的高层定义，并讨论它们之间的联系。为方便起见，我们使用术语邻近度（proximity）表示相似性或相异性。由于两个对象之间的邻近度是两个对象对应属性之间的邻近度的函数，因此我们首先介绍如何度量仅包含一个简单属性的对象之间的邻近度，然后考虑具有多个属性的对象的邻近度度量。这包括相关和欧几里得距离度量，以及Jaccard和余弦相似性度量。前二者适用于时间序列这样的稠密数据或二维点，后二者适用于像文档这样的稀疏数据。接下来，我们考虑与邻近度度量相关的若干重要问题。本节最后简略讨论如何选择正确的邻近度度量。 1)基础 1. 定义 两个对象之间的相似度（similarity）的非正式定义是这两个对象相似程度的数值度量。因而，两个对象越相似，它们的相似度就越高。通常，相似度是非负的，并常常在0（不相似）和1（完全相似）之间取值。 两个对象之间的相异度（dissimilarity）是这两个对象差异程度的数值度量。对象越类似，它们的相异度就越低。通常，术语距离（distance）用作相异度的同义词，正如我们将介绍的，距离常常用来表示特定类型的相异度。有时，相异度在区间[0, 1]中取值，但是相异度在0和之间取值也很常见。 2. 变换 通常使用变换把相似度转换成相异度或相反，或者把邻近度变换到一个特定区间，如[0, 1]。例如，我们可能有相似度，其值域从1到10，但是我们打算使用的特定算法或软件包只能处理相异度，或只能处理[0, 1]区间的相似度。之所以在这里讨论这些问题，是因为在稍后讨论邻近度时，我们将使用这种变换。此外，这些问题相对独立于特定的邻近度度量。 通常，邻近度度量（特别是相似度）被定义为或变换到区间[0, 1]中的值。这样做的动机是使用一种适当的尺度，由邻近度的值表明两个对象之间的相似（或相异）程度。这种变换通常是比较直截了当的。例如，如果对象之间的相似度在1（一点也不相似）和10（完全相似）之间变化，则我们可以使用如下变换将它变换到[0, 1]区间：s' = (s-1)/9，其中s和s'分别是相似度的原值和新值。一般来说，相似度到[0, 1]区间的变换由如下表达式给出：s'=(s-min_s) / (max_s - min_s)，其中max_s和min_s分别是相似度的最大
1 相似度文献总结 相似度有两种基本类别： （1）客观相似度，即对象之间的相似度是对象的多维特征之间的某种函数关系，比如对象之间的欧氏距离；（2）主观相似度，即相似度是人对研究对象的认知关系，换句话说，相似度是主观认知的结果，它取决于人及其所处的环境，主观相似度符合人眼视觉需求，带有一定的模糊性[13]。 1.1 客观相似度 客观相似度可分为距离测度、相似测度、匹配测度。它们都是衡量两对象客观上的相近程度。客观相似度满足下面的公理，假设对象 A 与B 的相似度判别为(,)A B δ，有: (1) 自相似度是一个常量：所有对象的自相似度是一个常数，通常为 1，即 (,)(,)1A A B B δδ== (2) 极大性：所有对象的自相似度均大于它与其他对象间的相似度，即 (,)(,)(,)(,)A B A A A B B B δδδδ≤≤和。 (3) 对称性：两个对象间的相似度是对称的，即(,)(,)A B B A δδ=。 (4) 唯一性：(,)1A B δ=，当且仅当A B =。 1.1.1 距离测度 这类测度以两个矢量矢端的距离为基础，因此距离测度值是两矢量各相应分量之差的函数。设{}{}'' 1212,,,,,,,n n x x x x y y y y == 表示两个矢量，计算二者之间距离测度的具体方式有多种，最常用的有： 1.1.1.1 欧氏距离：Euclidean Distance-based Similarity 最初用于计算欧几里德空间中两个点的距离，假设 x ，y 是 n 维空间的两个点，它们之间的欧几里德距离是： 1/221(,)()n i i i d x y x y x y =??=-=-????∑（1.1）
第14章CSS颜色与度量单位 学习要点： 1.颜色表方案 2.度量单位 本章主要探讨HTML5中CSS颜色和度量单位等问题，包括颜色的选取方式、相对长度和绝对长度等。 一．颜色表方案颜色的表现形式主要有三种方式：颜色名称、十六进制代码和十进制代码。p{ color:red; } 解释：这是将一个段落内的文字设置为红色，采用的是英文颜色名称。问题是，其他各种颜色我们将如何设置？ 在古老的HTML4时，颜色名称只有16种。 颜色名称十六进制代码十进制代码含义 black#0000000,0,0黑色 silver#c0c0c0192,192,192银灰色 gray#808080128,128,128灰色 white#ffffff255,255,255白色 maroon#800000128,0,0栗色 red#ff0000255,0,0红色 purple#800080128,0,128紫色 fuchsia#ff00ff255,0,255紫红 green#0080000,128,0绿色 lime#00ff000,255,0闪光绿 olive#808000128,128,0橄榄色 yellow#ffff00255,255,0黄色 navy#0000800,0,128海军蓝
blue#0000ff0,0,255蓝色 teal#0080800,128,128水鸭色 aqua#00ffff0,255,255浅绿色 当然，目前颜色名称远远不止这些，可以搜索更多的HTML颜色表或CSS颜色表查阅。这里提供一些页面如下： https://www.doczj.com/doc/7d3276727.html,/page/z1015m9220j18754.htmlhttp://finle.me/colors .htmlhttps://www.doczj.com/doc/7d3276727.html,/tags/html_ref_colornames.asp 在上面的表格中，我们也罗列出对应的十六进制和十进制颜色表示方法。使用方法如下：//红色的十六进制方案 p{ color:#ff0000; } 十进制表示方法就比较多样化，有四种方案： 函数说明示例 rgb(r,g,b)用RGB模型表示颜色rgb(0,128,128) rgba(r,g,b,a)同上，a表示透明度0~1之间rgba(0,128,128,0.5) hsl(h,s,l)用HSL模型（色相、饱和度 和透明度）来表示颜色 hsl(120,100%,30%) hsla(h,s,l,a)同上，a表示透明度0~1之间hsla(120,100%,30%,0.5) p{ color: rgb(112, 128,114); color: rgba(0, 128, 128,0.5); color: hsl(120, 100%,30%); color: hsla(120, 100%, 30%,0.5); } 目前又有一个疑问，这些值从哪里获取。除了颜色表之外，想要微调自己的颜色值。我们可以使用photoshop等平面设计软件的调色板获取相应的值。
颜色直方图： 全局颜色直方图：反映的是图像中颜色的组成分布，即出现了哪些颜色以及各种颜色出现的概率，Swain 和 Ballard最先提出了使用颜色直方图作为图像颜色特征的表示方法。他们还指出:颜色直方图相对于图像的以观察轴为轴心的旋转以及幅度不大的平移和缩放等几何变换是不敏感的，颜色直方图对于图像质量的变化(如模糊)也不甚敏感。颜色直方图的这种特性使得它比较适合于检索图像的全局颜色相似性的场合，即通过比较颜色直方图的差异来衡量两幅图像在颜色全局分布上的差异。 颜色直方图的主要性质有:直方图中的数值都是统计而来，描述了该图像中关于颜色的数量特征，可以反映图像颜色的统计分布和基本色调;直方图只包含了该图像中某一颜色值出现的频数，而丢失了某象素所在的空间位置信息;任一幅图像都能唯一的给出一幅与它对应的直方图，但不同的图像可能有相同的颜色分布，从而就具有相同的直方图，因此直方图与图像是一对多的关系;如将图像划分为若干个子区域，所有子区域的直方图之和等于全图直方图;一般情况下，由于图像上的背景和前景物体颜色分布明显不同，从而在直方图上会出现双峰特性，但背景和前景颜色较为接近的图像不具有这个特性。 累加直方图：当图像中的特征并不能取遍所有可取值时，统计直方图中会出现一些零值。这些零值的出现会对相似性度量的计算带来影响，从而使得相似性度量并不能正确反映图像之间的颜色差别。为解决这个问题，在全局直方图的基础上，Stricker和Orengo进一步提出了使用“累加颜色直方图”的概念。在累加直方图中，相邻颜色在频数上是相关的。相比一般直方图，虽然累加直方图的存储量和计算量有很小的增加，但是累加直方图消除了一般直方图中常见的零值，也克服了一般直方图量化过细过粗检索效果都会下降的缺陷。一般的颜色直方图由于颜色空间是三维的，具有相同的三通道独立分布，但其联合分布并不为一。这种不考虑联合分布的方法，会导致在结果集中不相似的图像数目增加。
在数据分析和数据挖掘的过程中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。最常见的是数据分析中的相关分析，数据挖掘中的分类和聚类算法，如K最近邻（KNN）和K均值（K-Means）。当然衡量个体差异的方法有很多，最近查阅了相关的资料，这里整理罗列下。 为了方便下面的解释和举例，先设定我们要比较X个体和Y个体间的差异，它们都包含了N个维的特征，即X=（x1, x2, x3, … x n），Y=（y1, y2, y3, … y n）。下面来看看主要可以用哪些方法来衡量两者的差异，主要分为距离度量和相似度度量。 距离度量 距离度量（Distance）用于衡量个体在空间上存在的距离，距离越远说明个体间的差异越大。 欧几里得距离(Euclidean Distance) 欧氏距离是最常见的距离度量，衡量的是多维空间中各个点之间的绝对距离。公式如下： 因为计算是基于各维度特征的绝对数值，所以欧氏度量需要保证各维度指标在相同的刻度级别，比如对身高（cm）和体重（kg）两个单位不同的指标使用欧式距离可能使结果失效。 明可夫斯基距离(Minkowski Distance) 明氏距离是欧氏距离的推广，是对多个距离度量公式的概括性的表述。公式如下： 这里的p值是一个变量，当p=2的时候就得到了上面的欧氏距离。 曼哈顿距离(Manhattan Distance) 曼哈顿距离来源于城市区块距离，是将多个维度上的距离进行求和后的结果，即当上面的明氏距离中p=1时得到的距离度量公式，如下：
切比雪夫距离(Chebyshev Distance) 切比雪夫距离起源于国际象棋中国王的走法，我们知道国际象棋国王每次只能往周围的8格中走一步，那么如果要从棋盘中A格(x1, y1)走到B格(x2, y2)最少需要走几步？扩展到多维空间，其实切比雪夫距离就是当p趋向于无穷大时的明氏距离： 其实上面的曼哈顿距离、欧氏距离和切比雪夫距离都是明可夫斯基距离在特殊条件下的应用。 马哈拉诺比斯距离(Mahalanobis Distance) 既然欧几里得距离无法忽略指标度量的差异，所以在使用欧氏距离之前需要对底层指标进行数据的标准化，而基于各指标维度进行标准化后再使用欧氏距离就衍生出来另外一个距离度量——马哈拉诺比斯距离（Mahalanobis Distance），简称马氏距离。 相似度度量 相似度度量（Similarity），即计算个体间的相似程度，与距离度量相反，相似度度量的值越小，说明个体间相似度越小，差异越大。 向量空间余弦相似度(Cosine Similarity) 余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间 差异的大小。相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上。公式如下： 皮尔森相关系数(Pearson Correlation Coefficient) 即相关分析中的相关系数r，分别对X和Y基于自身总体标准化后计算空间向量的余弦夹角。公式如下：
（一）概述 为什么要数据挖掘（Data Mining）？ 存在可以广泛使用的大量数据，并且迫切需要将数据转转换成有用的信息和知识 什么是数据挖掘？ 数据挖掘（Data Mining）是指从大量数据中提取或“挖掘”知识。 对何种数据进行数据挖掘？ 关系数据库、数据仓库、事务数据库 空间数据 超文本和多媒体数据 时间序列数据 流数据 （二）数据预处理 为什么要预处理数据？ 为数据挖掘过程提供干净、准确、简洁的数据，提高数据挖掘的效率和准确性，是数据挖掘中非常重要的环节； 数据库和数据仓库中的原始数据可能存在以下问题： 定性数据需要数字化表示 不完整 含噪声 度量单位不同 维度高 数据的描述 度量数据的中心趋势：均值、加权均值、中位数、众数 度量数据的离散程度：全距、四分位数、方差、标准差 基本描述数据汇总的图形显示：直方图、散点图 度量数据的中心趋势 集中趋势：一组数据向其中心值靠拢的倾向和程度。 集中趋势测度：寻找数据水平的代表值或中心值。 常用的集中趋势的测度指标： 均值： 缺点：易受极端值的影响 中位数：对于不对称的数据，数据中心的一个较好度量是中位数 特点：对一组数据是唯一的。不受极端值的影响。 众数：一组数据中出现次数最多的变量值。 特点：不受极端值的影响。有的数据无众数或有多个众数。
度量数据的离散程度 反映各变量值远离其中心值的程度（离散程度），从另一个侧面说明了集中趋势测度值的代表程度。 常用指标： 全距（极差）：全距也称极差，是一组数据的最大值与最小值之差。 R=最大值-最小值 组距分组数据可根据最高组上限-最低组下限计算。 受极端值的影响。 四分位距 (Inter-Quartilenge, IQR)：等于上四分位数与下四分位数之差（q3-q1） 反映了中间50%数据的离散程度，数值越小说明中间的数据越集中。 不受极端值的影响。 可以用于衡量中位数的代表性。 四分位数： 把顺序排列的一组数据分割为四（若干相等）部分的分割点的数值。 分位数可以反映数据分布的相对位置（而不单单是中心位置）。 在实际应用中四分位数的计算方法并不统一（数据量大时这些方法差别不大）。对原始数据： SPSS中四分位数的位置为(n+1)/4， 2(n+1)/4， 3 (n+1)/4。 Excel中四分位数的位置分别为(n+3)/4， 2(n+1)/4，（3 n+1)/4。 如果四分位数的位置不是整数，则四分位数等于前后两个数的加权平均。 方差和标准差：方差是一组数据中各数值与其均值离差平方的平均数，标准差是方差正的平方根。 是反映定量数据离散程度的最常用的指标。 基本描述数据汇总的图形显示 直方图(Histogram)：使人们能够看出这个数据的大体分布或“形状” 散点图 如何进行预处理 定性数据的数字化表示： 二值描述数据的数字化表示 例如：性别的取值为“男”和“女”，男→1，女→0 多值描述数据的数字化表示 例如：信誉度为“优”、“良”、“中”、“差” 第一种表示方法：优→1，良→2，中→3，差→4 第二种表示方法：
在做分类时常常需要估算不同样本之间的相似性度量(SimilarityMeasurement)，这时通常采用的方法就是计算样本间的“距离”(Distance)。采用什么样的方法计算距离是很讲究，甚至关系到分类的正确与否。对常用的相似性度量作一个总结。1.欧氏距离2.曼哈顿距离3. 切比雪夫距离4. 闵可夫斯基距离5.标准化欧氏距离6.马氏距离7.夹角余弦8.汉明距离9.杰卡德距离& 杰卡德相似系数10.相关系数& 相关距离11.信息熵12.兰氏距离13.斜交空间距离14.最大-最小相似度15.指数相似度16.KL距离 1. 欧氏距离(EuclideanDistance) 欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式。 (1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离： 三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离： (2)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离： 也可以用表示成向量运算的形式： (4)Matlab计算欧氏距离 Matlab计算距离主要使用pdist函数。若X是一个M×N的矩阵，则pdist(X)将X矩阵M行的每一行作为一个N维向量，然后计算这M个向量两两间的距离。 例子：计算向量(0,0)、(1,0)、(0,2)两两间的欧式距离 X= [0 0 ; 1 0 ; 0 2] D= pdist(X,'euclidean') 结果： D= 1.0000 2.0000 2.2361 2. 曼哈顿距离(ManhattanDistance)又称绝对值距离 从名字就可以猜出这种距离的计算方法了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(CityBlock distance)。 (1)二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离
1.4 数据仓库和数据库有何不同？有哪些相似之处？ 答：区别：数据仓库是面向主题的，集成的，不易更改且随时间变化的数据集合，用来支持管理人员的决策，数据库由一组内部相关的数据和一组管理和存取数据的软件程序组成，是面向操作型的数据库，是组成数据仓库的源数据。它用表组织数据，采用ER数据模型。 相似：它们都为数据挖掘提供了源数据，都是数据的组合。 1.3 定义下列数据挖掘功能：特征化、区分、关联和相关分析、预测聚类和演变分析。使用你熟悉的现实生活的数据库，给出每种数据挖掘功能的例子。 答：特征化是一个目标类数据的一般特性或特性的汇总。例如，学生的特征可被提出，形成所有大学的计算机科学专业一年级学生的轮廓，这些特征包括作为一种高的年级平均成绩(GPA：Grade point aversge)的信息， 还有所修的课程的最大数量。 区分是将目标类数据对象的一般特性与一个或多个对比类对象的一般特性进行比较。例如，具有高GPA 的学生的一般特性可被用来与具有低GPA 的一般特性比较。最终的描述可能是学生的一个一般可比较的轮廓，就像具有高GPA 的学生的75%是四年级计算机科学专业的学生，而具有低GPA 的学生的65%不是。 关联是指发现关联规则，这些规则表示一起频繁发生在给定数据集的特征值的条件。例如，一个数据挖掘系统可能发现的关联规则为：major(X, “computing science”) ? owns(X, “personal computer”) [support=12%, confidence=98%] 其中，X 是一个表示学生的变量。这个规则指出正在学习的学生，12% （支持度）主修计算机科学并且拥有一台个人计算机。这个组一个学生拥有一台个人电脑的概率是98%（置信度，或确定度）。 分类与预测不同，因为前者的作用是构造一系列能描述和区分数据类型或概念的模型（或功能），而后者是建立一个模型去预测缺失的或无效的、并且通常是数字的数据值。它们的相似性是他们都是预测的工具： 分类被用作预测目标数据的类的标签，而预测典型的应用是预测缺失的数字型数据的值。 聚类分析的数据对象不考虑已知的类标号。对象根据最大花蕾内部的相似性、最小化类之间的相似性的原则进行聚类或分组。形成的每一簇可以被看作一个对象类。聚类也便于分类法组织形式，将观测组织成类分 层结构，把类似的事件组织在一起。 数据演变分析描述和模型化随时间变化的对象的规律或趋势，尽管这可能包括时间相关数据的特征化、区分、关联和相关分析、分类、或预测，这种分析的明确特征包括时间序列数据分析、序列或周期模式匹配、和基于相似性的数据分析 2.3 假设给定的数据集的值已经分组为区间。区间和对应的频率如下。――――――――――――――――――――――――――――――――――――― 年龄频率――――――――――――――――――――――――――――――――――――― 1~5 200 5~15 450 15~20 300 20~50 1500 50~80 700 80~110 44 ―――――――――――――――――――――――――――――――――――――计算数据的近似中位数值。 解答：先判定中位数区间：N=200+450+300+1500+700+44=3194；N/2=1597 ∵ 200+450+300=950<1597<2450=950+1500； ∴ 20~50 对应中位数区间。
优先出版 计 算 机 应 用 研 究 第32卷 -------------------------------- 基金项目：黑龙江省教育厅科学技术研究资助项目(12541125) 作者简介：高雪瑶(1979-)，女，黑龙江省哈尔滨市人，副教授硕导，博士，主要研究方向为计算机图形学与CAD(gaoxueyao@https://www.doczj.com/doc/7d3276727.html,)；姜宏山(1989-)，男，硕士研究生，主要研究方向为计算机图形学与CAD ；张春祥(1974-)，男，教授硕导，博士，主要研究方向为计算机图形学与自然语言处理；卢志茂(1972-)，男，教授硕导，博士，主要研究方向为自然语言处理． 基于面匹配的模型相似性度量方法 * 高雪瑶1a ，姜宏山1a ，张春祥1b ，卢志茂2 (1．哈尔滨理工大学 a ．计算机科学与技术学院；b ．软件学院，哈尔滨 150080；2．大连理工大学 计算机科学与技术学院，辽宁 大连 116024) 摘 要：模型相似性度量是CAD 模型检索中的一个重要问题。为了准确地衡量两个模型的相似程度，本文提出了一种基于面匹配的模型相似性计算方法。使用面邻接图表示模型的拓扑结构，根据面的组成边数来构造两个模型之间的面匹配矩阵，同时，使用贪心算法来计算模型之间的相似性。在实验中，使用本文所提出的方法来度量目标CAD 模型和源CAD 模型之间的相似程度。实验结果表明：该方法能够有效地衡量模型之间的差异。 关键词：模型相似性；面邻接图；面匹配矩阵；贪心算法 中图分类号：TP391.7 文献标志码：A Method of model similarity measurement based on face matching GAO Xue-yao 1a , JIANG Hong-shan 1a , ZHANG Chun-xiang 1b , LU Zhi-mao 2 (1. a. School of Computer Science & Technology, b. School of Software, Harbin University of Science & Technology, Harbin 150080, China; 2. School of Computer Science & Technology, Dalian University of Technology, Dalian 116024, China) Abstract: Model similarity measurement is an important problem in retrieval of CAD models. In order to measure the similarity degree between two models precisely, this paper proposes a method to compute the similarity of models based on face matching. It uses a face relational graph to express the topological structure in the model and constructs the face matching matrix between two models. At the same time, it applies the greedy algorithm to compute the similarity between these two models. In experiments, it uses the proposed method of this paper to measure the similarity degree between target CAD model and source CAD model. Experimental results show that the method can measure the difference of models efficiently. Key Words: model similarity; face relational graph; face matching matrix; greedy algorithm 0 引言 CAD 模型相似性计算是三维模型检索中的重要组成部分，对检索系统的效率和可靠性都有着很大程度的影响。针对现有模型检索算法对局部细节特征描述不充分的现状，白晓亮提出了一种基于最大公共子图的三维CAD 模型检索算法。提取CAD 模型的B-Rep 信息，使用属性邻接图来表示模型。利用最大公共子图来检测CAD 模型中所包含的相似特征，根据相似特征来实现CAD 模型的相似性评价[1]。张欣提出了一种利用属性图来比较CAD 模型形状相似性的算法。根据图的邻接矩阵和顶点属性来构造图顶点序列，通过动态编程求出最大公共子图，得到CAD 模型之间的形状相似度。根据求出的未知模型与已知模型之间的形状相似度，利用概率方法来实现未知模型的自动语义标注[2]。王小凤提取三维模型深度图像边界方向的直方图和Zernike 矩特征，利用特征距离来度量两个模型之间的相似性[3]。王洪申利用模型的B-rep 表示过滤出与欲检索结构组成面相似 的面。通过删除不相关的面，将可能相似的局部结构从待检索模型中分离出来。利用二分图最优匹配算法计算分离出来的结构和欲检索结构之间的相似系数，以度量模型之间的相似程度 [4]。Tao 使用面属性关系图来表示CAD 模型，将实体模型的表 面边界分解为局部凸面、凹面和平面。在分解过程中，保持其突出几何特征数量的最小化。利用区域代码来描述表面区域以及它们在CAD 模型中的连接关系。通过比较区域属性代码来评估两个模型之间的相似性[5]。Wang 在三维模型表面任取若干个点，记录每个点的法向量，连接任意两点形成线段。计算线段的欧几里得距离，求出两端点的法向量与该线段的夹角。根据两个夹角将所得线段分为三个集合。针对每个集合，使用欧几里得距离来构造形状分布曲线。通过比较模型的三条形状分布曲线来求出两个模型的相似度[6]。Supasasi 使用Reeb 图来表示三维模型的结构属性，将其分解为若干个子部件。利用姿态无关的形状符号来描述每一个子部件的表面。使用最大公共子图来表示其拓扑结构，以度量三维模型之间的相似程度[7]。Wei
距离和相似性度量 相似性度量或者距离函数对于像聚类，邻域搜索这样的算法是非常重要的。前面也提到，网页去重复也是相似性应用的一个例子。然而，如何定义个合适的相似或者距离函数，完全依赖于手头的任务是什么。一般而言，定义一个距离函数d(x,y),需要满足以下几个准则：1. d(x,x) = 0 ;//到自己的距离为0 2. d(x,y)>=0 // 距离要非负 3. 对称性，d(x,y) = d(y,x) //如果A到B距离是a，那么B 到A的距离也应该是a 4. 三角形法则(两个之和大于第三边）d(x,k)+ d(k,y) >= d(x,y) 满足这4个条件的距离函数很多，一般有几类是比较常见的，通常来自比较直观的形象，如平面的一个两点的直线距离。下面讨论应用比较广泛的几类距离或相似性度量函数，欧拉距离，余弦函数cosine，Pearson函数，Jaccard index，edit distance。如果一个对象d(如：一篇文档）表示成一个n维的向量（d1,d2,….,dn),每一个维度都为对象的一个特征，那么这些度量函数极容易得到应用。1.范数和欧拉距离 欧拉距离，来自于欧式几何（就是我们小学就开始接触的几何学），在数学上也可以成为范数。如果一个对象对应于空
间的一个点，每一个维度就是空间的一个维度。特殊情况，如果n=1，那么，小学我们就学过，直线上两个点的距离是|x1-x2|。推广到高纬情况，一个很自然的想法是，把每一个维度的距离加起来不就可以呢。这就形成了传说中的一范数：看，是不是很简单。有一范数就有二范数，三范数。。。无穷范数。其实，二范数来的更加直观，我们都知道二维空间，三维空间的两点的距离公式。他就是二范数，在二维三维上的形式了。 好了，一鼓作气,p范数(p-norm) 无穷范数： 空间两点的距离公式（2-范数），是最常用的距离公式，他就是传说中的欧拉距离。多简单。2. cosine similarity cosine similarity是备受恩宠啊，在学向量几何的时候，应该接触过这个神奇的公式 分子是两 个向量的点积，||A||是向量的长度，这个公式神奇的地方是，随着角度的变化的，函数是从-1，1变化的。向量夹角的余 弦就是两个向量的相似度。cosine similarity 说，如果两个 向量的夹角定了，那么无论一个向量伸长多少倍，他们的相似性都是不变的。所以，应用cosine 相似性之前，要把对 象的每一个维度归一化。在搜索引擎技术中，cosine 相似性在计算查询和文档的相似性的时得到了很好的应用。对查询
三、芯片发光颜色（COLW） 红（Red）：R（610nm-640nm）黄（Yellow）：Y（580nm-595nm）兰（Blue）：B（455nm-490nm）兰绿（Cyan）：C（490nm-515nm）绿（Green）：G（501nm-540nm）紫（Purple）：P（380nm-410nm）琥珀（Amber）：A（590nm-610nm）白（White）：W2 黄绿（Kelly）：K（560nm-580nm）暖白（Warm white）W3 四、颜色波长 ★红： R1：610nm-615nm R2：615nm-620nm R3：620nm-625nm R4：625nm-630nm R5：630nm-635nm R6：635nm-640nm ★黄： Y1：580nm-585nm Y2：585nm-590nm Y3：590nm-595nm ★琥珀色： A1：600nm-605nm A2：605nm-610nm ★兰绿： G1：515nm-517.5nm G2：517.5-520nm G3：520nm-525nm G4：525nm-530nm G5：530nm-535nm G6：535nm-540nm ★兰： B1：455nm-460nm B2：460nm-462.5nm B3：462.5nm-465nm B4：460nm-465nm B5：465nm-470nm B6：470nm-475nm B7：475nm-480nm B8：480nm-485nm B9：485nm-490nm ★黄绿： K1：560nm-565nm K2：565nm-570nm K3：570nm-575nm K4：575nm-580nm ★纯绿： C1：490nm-495nm C2：495nm-500nm C3：500nm-515nm
数据挖掘之相似性度量 机器学习或数据挖掘，就是在数据中寻求答案的算法。 而寻求的答案就是训练完成的数据模型。 大部分的数据建模方法都属于这两种： 1）数据汇总，对数据进行简洁的近似描述 如pagerank、聚类 2）特征抽取 如频繁项集（同时频繁出现的元素子集）、相似项（共同元素比例较高的集合对） 在机器学习或数据挖掘之前，还需要概率，或信息论的一些相关知识，现实世界的对象需要转换为计算机的度量方式。 1. TF.IDF 2. 熵的相关概念 3. 相似度的度量及计算 4. 对文本相似度的分析 5. 局部敏感Hash的分析LSH 6. 查找相似项的处理流程 7. 几种距离度量方式 相关知识： 1. TF.IDF 文本分类时，一个重要指标：TF.IDF，分为两个阶段：同一文档中的统计；以文档为粒度，所有文档的统计。 TF： term frequency 词项频率，同一篇文档中，所有词项出现频率的归一化 IDF：inverse document frequency 逆文档频率，所有文档数目，与某一词出现的
文档的数目的比率关系 其中的关系： 不仅仅是一个公式，里面包含了信息论中熵的概念。IDF就是一个特定条件下关键词的概率分布的交叉熵。应用了对数运算。 2. 熵的相关概念 熵，表示信息量的大小，与概率相关。随机变量的不确定性越大，即概率小，其熵也就越大，将其搞清楚，所需的信息量也就越大。 -Pi * log(2, Pi) 求和。一个系统越混乱，则每个变量的概率越小，其熵也就越大。 信息论在通信编码的表示也是一样的，一个变量，在系统中的概率越小，其编码也就越长，因为短的编码要留给概率大的变量。即熵越大，其编码也就越长，这样压缩的效率就比较高。发送一段信息，其需要的编码长度（二进制），也就是 -Pi * log(2, Pi) 求和。或者，可以说，熵越大，信息量越大，一个概率较低的词，可能就是系统信息比较关键的词。 互信息：两个随机变量的相关/依赖程度，可以用来解释一个变量已知时，另外一个变量的不确定的变化。即不确定信息的减少量。 自信息：一个随机变量（信源）发出的信息，这个信息所带来的信息量的度量。一次事件发生的提供的信息量-log(2, Pi)，有时与熵的含义相同（当事件只发生一次时）。 而熵是平均信息量，所有自信息的期望。当信息确定时，确定场（无随机性）的熵最小。等概场的熵最大。 熵率：又称字符熵、词熵。信息量的大小随着消息长度的增加而增加。-（1/n）（求和Pi*log(2, Pi)） 联合熵：同联合分布函数的形式类似，联合随机变量所表示的平均信息量（期望）。H(x, y) = -求和P(x,y) log(2, P(x, y)) 条件熵：H(y|x) = -求和P(x,y) log(2, P(y|x)) 联合熵 = 条件熵 + 单变量熵, H(x, y) = H(y|x) + H(x) 互信息的熵 I (x; y) = H(x) - H(y | x) = H(y) - H(y|x), 描述了X中包含有多少Y的信息量，或者是Y中包含了多少X的信息量。 当X, Y相互独立，则其互信息为0. 当I(x; y) >> 0，则两个事件X,Y高度相关；当I（x; y）<<0，则两个事件X，Y 互补分布。
第一章 1、数据仓库就是一个面向主题的、集成的、相对稳定的、反映历史变化的数据集合。 2、元数据是描述数据仓库内数据的结构和建立方法的数据，它为访问数据仓库提供了一个信息目录，根据数据用途的不同可将数据仓库的元数据分为技术元数据和业务元数据两类。 3、数据处理通常分成两大类：联机事务处理和联机分析处理。 4、多维分析是指以“维”形式组织起来的数据（多维数据集）采取切片、切块、钻取和旋转等各种分析动作，以求剖析数据，使拥护能从不同角度、不同侧面观察数据仓库中的数据，从而深入理解多维数据集中的信息。 5、ROLAP是基于关系数据库的OLAP实现，而MOLAP是基于多维数据结构组织的OLAP实现。 6、数据仓库按照其开发过程，其关键环节包括数据抽取、数据存储与管理和数据表现等。 7、数据仓库系统的体系结构根据应用需求的不同，可以分为以下4种类型：两层架构、独立型数据集合、以来型数据结合和操作型数据存储和逻辑型数据集中和实时数据仓库。 8、操作型数据存储实际上是一个集成的、面向主题的、可更新的、当前值的（但是可“挥发”的）、企业级的、详细的数据库，也叫运营数据存储。 9、“实时数据仓库”以为着源数据系统、决策支持服务和仓库仓库之间以一个接近实时的速度交换数据和业务规则。 10、从应用的角度看，数据仓库的发展演变可以归纳为5个阶段：以报表为主、以分析为主、以预测模型为主、以运营导向为主和以实时数据仓库和自动决策为主。 第二章 1、调和数据是存储在企业级数据仓库和操作型数据存储中的数据。 2、抽取、转换、加载过程的目的是为决策支持应用提供一个单一的、权威数据源。因此，我们要求ETL 过程产生的数据（即调和数据层）是详细的、历史的、规范的、可理解的、即时的和质量可控制的。 3、数据抽取的两个常见类型是静态抽取和增量抽取。静态抽取用于最初填充数据仓库，增量抽取用于进行数据仓库的维护。 4、粒度是对数据仓库中数据的综合程度高低的一个衡量。粒度越小，细节程度越高，综合程度越低，回答查询的种类越多。 5、使用星型模式可以从一定程度上提高查询效率。因为星型模式中数据的组织已经经过预处理，主要数据都在庞大的事实表中。 6、维度表一般又主键、分类层次和描述属性组成。对于主键可以选择两种方式：一种是采用自然键，另一种是采用代理键。 7、雪花型模式是对星型模式维表的进一步层次化和规范化来消除冗余的数据。 8、数据仓库中存在不同综合级别的数据。一般把数据分成4个级别：早期细节级、当前细节级、轻度综合级和高度综合级。 第三章 1、SQL Server SSAS提供了所有业务数据的同意整合试图，可以作为传统报表、在线分析处理、关键性能指示器记分卡和数据挖掘的基础。 2、数据仓库的概念模型通常采用信息包图法来进行设计，要求将其5个组成部分（包括名称、维度、类别、层次和度量）全面地描述出来。 3、数据仓库的逻辑模型通常采用星型图法来进行设计，要求将星型的各类逻辑实体完整地描述出来。 4、按照事实表中度量的可加性情况，可以把事实表对应的事实分为4种类型：事务事实、快照事实、线性项目事实和事件事实。 5、确定了数据仓库的粒度模型以后，为提高数据仓库的使用性能，还需要根据拥护需求设计聚合模型。 6、在项目实施时，根据事实表的特点和拥护的查询需求，可以选用时间、业务类型、区域和下属组织等多种数据分割类型。