最佳匹配檢索

檢索，就是根據給定的某個值，在檢索表中查找一個關鍵字等於給定值得記錄的運算或操作。在計算機進行檢索是對已存入計算機中的數據進行檢索。最佳匹配檢索是指基於利用匹配算法或一些規則找到最佳匹配結果。最佳匹配檢索有著廣泛套用，像檢索，自然語言處理等。

基本介紹

• 中文名：最佳匹配檢索
• 外文名：optimal match retrieval
• 學科：計算機科學
• 目的：檢索出最佳匹配結果
• 套用：圖像檢索，自然語言處理
• 實現：利用匹配算法或一些規則

簡介

最佳匹配檢索是一個廣泛的概念，目前還沒有一個統一的解釋。在不同的套用領域，實現最佳匹配檢索的方法一般是不相同的，但都有一點是相同的，儘可能實現最佳。最佳匹配可以指在檢索時間代價、空間代價和結果d等指標中一個或者一個以上。例如在漢字分詞中，最佳匹配是對分詞詞典按詞頻大小順序排列，並註明長度，降低時間複雜度。優點：易於實現。缺點：匹配速度慢。對於未登錄詞的補充較難實現。缺乏自學習。

圖像最佳匹配檢索

基於內容的圖像檢索，作為圖像處理與模式識別中一直以來的研究熱點，在最近10多年得到了長足的發展，它主要解決怎樣從圖像庫中選出人們想要的圖片。基於內容的含義主要是指用圖像本身的視覺信息，包括顏色、紋理、形狀和空間關係等。

子區域最佳匹配算法

區域最佳匹配法首先將圖像抽象為圖論中的連通圖，將代表目標的圖示抽象為圖中的節點。

然後按照中心點法將圖劃分為若干個子圖，這些子圖的形狀大小由且僅由節點的空間分布 決定。中心點法描述的是以某一節點為中心的鄰域構成子區域模式的方法。如果按廣度優 先法對圖進行遍歷，可得到子區域順序向量。根據待檢索圖和據庫圖順序向量的對應元素 值可計算兩個圖中對應子區域的相似距離。最後通過加權求和得到兩個圖間的距離，這個 距離直接表示出兩圖的相似性。

二分圖最佳匹配

二分圖：簡單來說，如果圖中點可以被分為兩組，並且使得所有邊都跨越組的邊界，則這就是一個二分圖。準確地說：把一個圖的頂點劃分為兩個不相交集 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”的底部。