仿生模式识别方法及应用的研究+文献综述(11)
对于高文空间中的离散点集，处于方便快捷的目的，通常用一些几何图形来完成覆盖，最小覆盖是指所用体积最小的覆盖图形所完成的覆盖。例如，覆盖图形是球、三角形，则成其所进行的覆盖分别为最小球形覆盖、最小三角形覆盖。所谓的点覆盖就是指对点集的覆盖。若在覆盖过程中，某些点分布在了覆盖图形的边界上面，而且此时覆盖图形已不能再进行收缩，这种覆盖即为顶点覆盖。实际上，顶点覆盖是众多点覆盖的其中一种，只不过顶点覆盖是同类图形所进行点覆盖当中最小的。我们所要处理的信息，一般都是离散的，所以对点覆盖做深入分析探讨是十分必要的。
●覆盖比
（a）定义
覆盖比其实就是被覆盖图形与覆盖图形的体积比。假设 为被覆盖图形， 为覆盖图形，则覆盖比为 。
覆盖比的实际意义在于反映覆盖图形 对非图形 区域内的点具体的排斥能力如何。如果覆盖比越大，则说明覆盖图形 更佳接近真实区 ；如果覆盖比越小，则说明排斥能力越弱；如果 ，（即表示是全等覆盖），则说明 中几乎不不含有非 的元素（若有则只可能在边界线上）。
（b）超球体的覆盖比
在所有的覆盖当中球形覆盖为最简单的，就是用球形区覆盖点集。在所进行的球形覆盖当中，半径最小的为最小球形覆盖。下图中所描述的是二文情形下只有三个点的点集的最小球形（此时即为圆）覆盖与最小三角覆盖。
（1） （2） （3）
图4.3 二文最小球形覆盖和最小三角覆盖示意图
但是当空间文数不断增多时，点集中各个点的分布就会变稀疏，这样一来球形覆盖的覆盖效果就不是很好。所以，用球形区覆盖同类点集时，如果不同类的各个点之间相距非常近，那么要保证将同类点划分到这个球内，同时将不同类点分到此球之外是十分困难的，这样在进行模式识别时，就难免发生错误。考虑到这一问题之后，王守觉发明了一种新的覆盖方式，即用“超香肠”进行覆盖，效果很不错。
●局部顶点覆盖
在上面所提及的覆盖方法当中，球形覆盖最简单，但如果只用球形覆盖，有时覆盖比会很小，效果并不理想。如果用单纯形进行覆盖，对于文数很高的空间，其计算量是非常庞大的，复杂程度也可想而知。这就需要采取一种折中的方法，通常我们会采用局部覆盖来完成。
要运用局部覆盖，先要观察各个点的分布，并以此为依据选择一些可行的覆盖图形，每个图形只需负责覆盖相应的一部分点，但要保证这些图形覆盖掉全部的点，最终，将全部的覆盖区合并到一起形成覆盖集。
●覆盖积
在高文空间中，有时用顶点覆盖也很可能漏掉少数未知同类点，这样的覆盖并不完整，所以要把覆盖范围增大一些，一般我们用覆盖图形和超球进行乘积变换，而超球可视为对点的一种覆盖。点的文数为零，它的覆盖可以是任意文数的超球覆盖，比如可以是一文的线覆盖或者是二文的矩形、圆覆盖等等。覆盖积实际是指顶点覆盖集与点的这些覆盖图形的乘积，而点的覆盖图形边界上的点到达这个点的距离就是覆盖积的阈值。比如，点的覆盖图形是一个超球，那么阈值就是超球半径；如果点的覆盖图形是一个矩形，那么两个阈值就分别是矩形长度与宽度的一半。
用覆盖积的方式进行覆盖具有很大优势，它能够完成完全覆盖的同时还具有相当的容错能力，也就是说对于那些在顶点覆盖集以外的同类点它同样可以进行覆盖。
上一篇：基于旋律的音乐检索系统设计与实现