[科普中国]-最佳匹配检索

简介

最佳匹配检索是一个广泛的概念，目前还没有一个统一的解释。在不同的应用领域，实现最佳匹配检索的方法一般是不相同的，但都有一点是相同的，尽可能实现最佳。最佳匹配可以指在检索时间代价、空间代价和结果d等指标中一个或者一个以上。例如在汉字分词中，最佳匹配是对分词词典按词频大小顺序排列，并注明长度，降低时间复杂度。优点：易于实现。缺点：匹配速度慢。对于未登录词的补充较难实现。缺乏自学习。

图像最佳匹配检索基于内容的图像检索，作为图像处理与模式识别中一直以来的研究热点，在最近10多年得到了长足的发展，它主要解决怎样从图像库中选出人们想要的图片。基于内容的含义主要是指用图像本身的视觉信息，包括颜色、纹理、形状和空间关系等。

子区域最佳匹配算法区域最佳匹配法首先将图像抽象为图论中的连通图，将代表目标的图标抽象为图中的节点。

然后按照中心点法将图划分为若干个子图，这些子图的形状大小由且仅由节点的空间分布 决定。中心点法描述的是以某一节点为中心的邻域构成子区域模式的方法。如果按广度优 先法对图进行遍历，可得到子区域顺序向量。根据待检索图和据库图顺序向量的对应元素 值可计算两个图中对应子区域的相似距离。最后通过加权求和得到两个图间的距离，这个 距离直接表示出两图的相似性。1

二分图最佳匹配二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集 UU 和VV ，使得每一条边都分别连接UU、VV中的顶点。如果存在这样的划分，则此图为一个二分图。

最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。

如果G为加权二分图,则权值和最大的完备匹配称为最佳匹配。

求一个二分图的最佳匹配的普遍算法是KM(Kuhn-Munkres)算法。

KM算法的基本思想是,把权值转化为可行顶标，再用匈牙利算法求出一组完备匹配,如果无法求出完备匹配，则修改可行顶标，直至找到完备匹配为止，这时的完备匹配为最佳匹配。

Kuhn－Munkras算法流程：

(1)初始化可行顶标的值

(2)用匈牙利算法寻找完备匹配

(3)若未找到完备匹配则修改可行顶标的值

(4)重复(2)(3)直到找到相等子图的完备匹配为止

最佳匹配搜索示例最佳匹配（Best Match）作为eBay默认的搜物品排序标准，可帮助买家找到真正需要的产品。对卖家来说，这意味着可将物品展示在买家面前，而向买家提供优质的产品和服务是决定你在“最佳匹配”中排名的关键。

“最佳匹配”考量因素最近销售记录（针对于“定价类物品”），是衡量卖家一条listing中，有多少item为不同的买家所购买。物品有越多的近期销售记录，越能取得曝光度。第一次被重新刊登的商品同样保留最近销售记录；

即将结束时间（针对于“拍卖类物品”），即“拍卖”物品的下架时间；

卖家评级（DSR）：包括物品描述，沟通，货运时间，运费。优秀评级卖家/Top Rated Seller”的商品一般排名较为靠前;

买家满意度：包含三个考量标准，即中差评数量/DSR1分2分的数量/INR/SNAD投诉数量；

物品“标题”相关度：买家输入的搜索关键字与最终成交商品的标题、关键字之间的匹配；

物品价格+运费：“最佳匹配”提高免运费物品的排名并降低高运费或运费不明的物品的排名。

不同刊登方式的物品的考量因素“最佳匹配 / Best Match”采用不同方式对不同刊登物品的方式进行排序，定义物品相关度的标准在定价物品和拍卖物品上是不同的。如，物品剩余时间这一项与定价物品不相关，但对于即将结束的拍卖物品则很重要。出于这些及更多其他原因，这两种方式的搜索排序基于不同的标准。

拍卖物品

对于拍卖物品，物品相关度、DSR“详尽卖家评级”以及物品剩余时间仍然是最佳匹配“搜索结果 / Research Results”排序中考虑的重要因素。拍卖物品在即将下架前仍将在搜索结果中获得更多的曝光量，运费也被考虑在内。设置合理的运费价格和提供包邮服务是实用的做法，尽管包邮的拍卖物品不会再增加额外的曝光量。

定价物品

对于定价物品，物品的相关度和卖家的DSR是最佳匹配的重要因素。物品剩余时间相对不重要，而物品的总成本（价格+运费）和近期销量（即销售速度越快对排序结果越有利）非常重要。为了让最新 上架的物品出现在搜索结果前，且在搜索结果前为买家呈现更广泛的物品选择，在这些类目中，定价物品的主要排序因素将以物品的上架时间替代物品表现分数。卖家表现评分也相当重要：优秀评级卖家将在定价产品的最佳匹配搜索中获得增量展示。低于新最低卖家标准的卖家将在拍卖产品和定价产品的最佳匹配搜索中获得比较差的排序。提供包邮服务的定价产品仍将获得额外的曝光量，而运费过高的拍卖产品和定价产品的曝光量将降低。

搜索结果排序有何调整在最佳匹配结果中，根据刊登物品方式的不同（例如拍卖或定价），每个物品将按照不同的标准进行排序——根据每种刊登方式设定的最相关标准——然后被混合显示。“仓储式物品 / Store Inventory Format”仍将继续被显示在“搜索结果 / Research Results”的底部。