模式识别中两种相似性测度算法比较

第２７卷第９期　２０１１年５月　甘肃科技　Ｇａｎｓｕ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　，０Ｚ．２７Ⅳ０．９　ＭＢｖ．　２０１１　

模式识别中两种相似性测度算法比较　

季少石　（苏州大学电子与通信工程，江苏苏州２１５００６）　

摘要：针对模式识别中采用的相似性测度方法进行了研究，分析了两种相似性测度的优缺点。得出了基于最佳逼　近距离的相似性测度优越性，比传统相似性测度具有更高的准确率，特别适合用于临界区域内样本的聚类决策。　关键词：模式识别；相似性；测度；最佳逼近；距离　中图分类号：ＴＰ３０１．６　

相似性测度是描述模式与模式之间、样本与样　本之间、或者某一个样本同模式中的样本的相似性　的一种尺度。它可以用来度量差异性。距离和角度　都是在模式识别中使用的相似性的测度，其中以距　离较为常用。本研究介绍的两种模式识别中基于距　离的相似性测度方法，通过比较，得出在某些方面基　于最佳逼近距离法的优越性。　

１欧氏距离法　

欧氏距离即欧几里德距离，其数学模型如式　（１）所示：　Ｄ（Ｘｉ，　）＝Ｉｌ　一　ＩＩ＝［（置。一　）。＋…＋　（　ｉ　一　）。］　（１）　】　其中Ｘｉ，　为ｎ维模式样本，Ｘｉ＝［五　，　…　］，　＝［　，　…　］．欧氏距离实际上是两个样　本之间的模值，用来表示相似性测度比较直观，距离　越小，则表示相似性越大。而且只要相对距离不发　生变化，欧氏距离就不会变化，即使样本在ｎ维空间　的坐标发生变化，也不会影响最后的分类。欧氏距　离的计算方法比较简单，但是描述的只是两个样本　之间的距离尺度，或者描述某一样本与某一类聚类　中心的距离，但是确无法反映样本与聚类的紧致性　程度。如图１所示，虽然样本　到聚类Ａ和聚类　的聚类中心的距离相等，但是直观上样本　与聚类　Ａ关系更为紧致．在这种情况下如果使用欧氏距离　法就可能会产生误判的结果，而下面介绍的最佳逼　近距离法则可以避免类似情况发生。　

２最佳逼近距离法　

最佳逼近距离是建立在正交投影的基础之上，　根据最佳逼近定理：　—　Ａ　●一ｔ…　＿’　－　…ｒ‘’　一藁謇圣心　；‘／　…｛…一｝一　…－◆一　０夕　：　；、、Ｌ　——　十一　一一　《　ｒ＿『ｒ　巧、ｉ　｝　ｊ；黼ｒ　；！‘　！　｛　

图１欧氏距离　假设　是　空间中的一个子空间，Ｙ是　中的任　意向量，Ｙ是Ｙ在　上的正交投影，那么Ｙ是　中最　接近Ｙ的点，也就是指　

ｌｌ　Ｙ—Ｙ　ＩＩ＜ｌ１　Ｙ—ｔ，Ｉｌ　（２）　对所有属于ｗｙ．异于Ｙ的　成立［　，如图２所　示。　

Ｗ　图２最佳逼近距离　也就是说向量Ｙ与子空间　中任意向量距离　

的最小值即为Ｄ　＝Ｉｌ　Ｙ—Ｙ　ｌｌｏ　Ｄ　即为最佳逼近　距离。　根据正交分解定理，如果｛“　・・　｝是　中的　

任意正交基，那么　第９期　季少石：模式识别中两种柑似性测度算法比较　１９　

多＝　一＋Ｕｐ／．Ｚ　３）＇，　——１＋…＋　（ｊ　Ｊ　１‘　１　ｐ。“ｐ　

可得　＝ＩＩ　Ｙ－（　…＋　Ｉ　

（４）　由公式（４）得到Ｄ　的计算公式，只要知道子　空间　中的任意正交基，就可以得到向量ｙ到子空　间　的最短距离。此公式不仅适用于一维和二维　向量数据，也可适用在Ｔｔ维的向量数据。　将上述最佳逼近距离的算法引入相似性测度，　将待分类样本作为向量Ｙ，而由多个样本构成的聚　类作为子空间　，聚类中的样本即为构成子空间　的正交基，计算过程如图３所示．根据样本的数量　和维数，分成两中情况：　

图３最佳逼近距离算法流程　１）样本的数量Ｐ小于等于样本维数ｎ，由于最　佳逼近公式适用于点到向量或ｎ维子空间的距离，　必须先通过变换坐标原点，将坐标原点变换到其中　一个样本上，然后计算出样本到聚类的最佳逼近距　离。　２）样本的数量Ｐ大于样本维数ｎ，由于　为子　空间，所以　中选取的正交基的个数必须小于等于　样本的维数，我们可以依次选取　个样本计算最佳　逼近距离，计算最佳逼近距离前一样必须经过坐标　原点变换，得到最佳逼近距离然的一组数据，这组数　据的最小值即是样本到聚类的最佳逼近距离。　特别注意的是由于模式识别中计算最佳逼近距　离的时候，由有限个样本构成的区域非无限扩展的，　当在子空间上的投影超出构成子空间正交基的区域　范围时，不能使用公式（４），此时的最佳逼近距离与　样本点间最小欧氏距离一致。　最佳逼近距离的优点是通过计算样本与聚类的　正交投影距离，反映出样本与某一聚类的紧致性程　度，能兼顾到类间分散和类内聚合，对于提高判决的　准确性有很大的帮助。能有效弥补欧氏距离法等只　能反映两个样本之间的距离尺度，或者描述某一样　本与某一类聚类中心距离的局限性。　

３数值实例　

本文采用两个二维样本组成的聚类Ａ和Ｂ，以　及一个待判决样本Ｙ，如图４所示。其中　Ａ＝［６，３］　，［６，５］　，［７，４］　，［７，６］　，［８，５］　，［８，　７］　，［９，６］Ｔ［９，７］　，［１０，６］　Ｂ＝［１，２］　，［１，３］　，［２，１］　，［２，３］　，［２，４］　，［３，　０］　，［３，２］Ｔ［４，０］　，［４，１］　Ｙ＝［５，３］　

…　

Ｂ　旅递　

…　．：｝：　－　…　…　一＿｝…　一丰…　

．．一　一　…一一　…　一一｛．…　｝一｝一—　４一一｛…～Ｌ…．　图４最佳逼近距离　可得：聚类　的聚类中　￣ｑ７ｏ／９，４９／９］　，聚类　的聚类中心［３，１６／９］　，分别使用欧氏距离法和最　佳逼近距离法的结果进行判决，然后依据判决的结　果对聚类进行评价，结果见表１。　

表１　欧式距离法和最佳逼近距离法对比　

（下转第１１６页）

　１ｌ６　甘肃科技　第２７卷　

（１３）植筋所采用的技术、材料、植筋抗拔试验　技术要求需市建委或有关单位认可；并具有相关资　质单位的检测合格报告。　２．４钢管桩承载力检测与检验　（１）施工过程中应做好现场验收记录，包括钢　管焊接、成孔和注浆等各项工序指标考核。　（２）采用载荷试验方法来检验钢管桩的竖向承　载力，在同一条件下的试桩数量不宜小于总桩数的　１％，且不应小于三根；在建造上部结构前应检验桩　位、桩数和桩头强度。　本工程所用桩为端承桩，根据市建委及质监站　的要求，随机抽取三根桩做荷载试验，三根桩的Ｑ—　ｓ曲线基本相同，以ｌ＃号桩为例，Ｑ—ｓ曲线如图３　所示。　试验荷载最大加载到４７４ｋＮ时，总沉降量为　１６．０７ｍｍ，卸载至零后，残余沉降量为１１．７７ｍｍ，回　弹４．３０ｍｍ，回弹率２６．７６％，对应于单桩竖向抗压　承载力特征值２３７ｋＮ的单桩沉降为４．８０ｒａｍ，Ｑ—Ｓ　曲线呈缓变型，加载至４７４ｋＮ时，Ｑ—Ｓ曲线未出现　陡降段，综合分析，该桩的竖向抗压承载力极限值　Ｑｕ￣＞４７４ｋＮ。　

３结论　０　９５　ｔ４２　ｌ９Ｄ　２３７：２８４　３３２　３７９船７　４７４　

图３　ｌ　桩荷载位移曲线　本工程通过钢管桩对基础进行加固，控制了房　屋沉降，用微型钢管桩对基础进行加固，施工简便易　行，质量容易控制，值得大力推广。　

参考文献：　［１］ＧＢ　５０００７—２００２，建筑地基基础设计规范［Ｓ］．中国建　筑工业出版社．　［２］ＧＢ　５００１０—２００２，混凝土结构设计规范［Ｓ］．中国建筑　工业出版社．　［３］ＪＧＪ　９４—２００８，建筑桩基技术规范［Ｓ］．中国建筑工业　出版社．　・●…・●…・●…・●…・●…・●…・●…・●…・●…・●…－●…・●…・●…・●…・●…・●…・●…・●…・●…・●…・●…・●…・●…・●…－●…－●…・●…・●…・●…・●…・●…・●…・●…・●…－●…・●…・●…・●…・●…・●…・●…・●…・●…・●…・●…・●“　（上接第ｌ９页）　

４结论　

相似性测度是聚类和判决的依据，直接影响到　聚类的合理性，而判别一个聚类是否合理可以用类　问分散性和类内聚合性来评价。从以上的结果可以　得知在某些情况下，采用最佳逼近距离法得出的结　果比欧氏距离法得出的结果更加合理。但是采用最　佳逼近距离法所需要计算步骤比欧氏距离法要复　杂，在计算效率方面最佳逼近距离法要差。因此，在　某些重视精度，同时可以容忍损失部分效率的场合，　可以考虑使用最佳逼近法。　参考文献：　

［１］齐敏，李大健，郝重阳．模式识别导论［Ｍ］．北京：清　华大学出版社，２００９（６）：１５－１８．　［２］Ｌａｙ　Ｄ　ｃ．刘深泉等译．线性代数及其应用（原书第３　版）［Ｍ］．北京：机械工业出版社，２００５（８）：３４５－３４９．　［３］杨振刚，邓飞其．ＣＢＲ中案例相似性测度研究［Ｊ］．。计　算机应用与软件，２００８，２５（６）：２２２－２２３．　［４］王洪，冯嘉礼．定性映射正交基空间下的模式识别技　术［Ｊ３．２００６，３２（１７）：９５－９６．　［５］刘庚，徐海樵．雷达辐射源的两种识别算法比较［Ｊ］．　舰船电子工程，２００８（１１）：１１１－１２６．　［６］　薛前，徐德昌．时间序列的相似性测度［Ｊ］．生物信息　学，２００９，７（１）：７５－７７．　［７］夏良正，李晓兵，罗庆姚．一种新的基于投影的二维　矩不变量快速算法［Ｊ］．东南大学学报，１９９３，２３（１）：　４ｌ４８．　［８］孙吉贵，刘杰，赵连宇．聚类算法研究［Ｊ］．软件学报，　２００８，１９（１）：４８　１．　［９］　赵宇海，武晓新，刘志勇，等．一种有效的基因投影聚　类算法［Ｊ］．广西师范大学学报（自然科学版），２００９，　２７（１）：１０５－１０８．　［１０］Ｘｕ　Ｚｅｓｈｕｉ．Ｏｎ　ｓｉｍｉｌａｒｉｔｙ　ｍｅａｓｕｒｅ￣ｏｆ　ｉｎｔｅｒｖａｌ—ｖａｌｕｅｄ　ｉｎｔｕｉｔｉｏｎｉｓｔｉｅ　ｆｕｚｚｙ　ｓｅｔｓ　ａｎｄ　ｔｈｅ　ｉｒａｐｐｌｉｅａ　ｔｉｏｎ　ｔｏ　ｐａａｅｍ　ｒｅｃｏｇｎｉｔｉｏｎｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｕｔｈｅａｓｔ　Ｕｎｉｖｅｒｓｉｔｙ，２００７，　２３（１）：１３９－１４３．　［１Ｉ］Ｙａｎ　Ｄｕａｎｗｕ，Ｌｉ　Ｘｉａｏｐｅｎｇ，Ｗａｎｇ　Ｌ　ｅ　Ｉ，Ｃｈｅｎｇ　Ｘ　ｉａｏ．　Ｏｎｔｏｌｏｇｙ—ｂａｓｅｄ　ｓｉｒｅ　ｉｌａｒｉｔｙ　ｍｅａｓｕｒｅ　ｆｏｒ　ｔｅｘｔ　ｃｌｕｓｔｅｒｉｎｇ　［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆＳｏｕｔｈｅａｓｔ　Ｕｎｉｖｅｒｓｉｔｙ，２００６，２２（３）：３８９．　３９３．