# [2017SSTD] Towards Spatially- and Category-Wise k-Diverse Nearest Neighbors Queries

## 摘要

k-nearest neighbor (k-NN) queries 被廣泛使用。在原始的定義中，k-NN queries 只關注靠近性 (closeness) ，與答案集的多樣性 (diversity) 無關。然而有些情景下，我們會希望答案集與搜尋條件距離相近，並且多樣性要盡可能高，例如: User 正在附近尋找餐館，則返回距離較近且不同類型的餐館。

本論文提出兩種利用 linear skyline 、尋找空間方面和類別方面的 k-NN，並且可以根據任何 2 個競爭標準 (靠近性與多樣性) 的線性組合，找出最優解。本篇論文的實驗（通過更改許多參數）表明，我們的方法比單純的方法快若干個數量級。

## 引言

k-NN 查詢被廣泛使用在許多領域包括 database 和 data mining 等，然而 k-NN 有一個潛在的缺點: k-NN 僅針對搜索條件求出最短距離的解，卻完全不考慮這些解彼此之間的關係，這造成 k-NN 輸出的解同質性很高，缺乏全局的資訊。

舉個場景: 假設要排序文檔，並回傳 k 個跟查詢條件相關的文檔，若這 k 個文檔的內容差異越大則讀者蒐集到的資訊就越多。

由此促使一些研究將多樣性納入搜索，即盡可能尋找接近的元素，同時又盡可能讓 k 個元素多樣化。在本篇論文，我們加入**空間多樣性**和**類別的多樣性**來探討 k-NN queries ，稱之為 **k-Diverse NNs** (kDNNs)。

- **空間多樣性**
兩個 data point 的空間多樣性取決於它們之間的距離。舉例: 有些遊客想要探索離他不遠的景點，但同時希望所有景點在這座城市的不同區域，這樣才能多探索一點，不會只在同一區逛。
- **類別多樣性**
類別多樣性是通過 data point 的類別 (或 label) 之間的差異來建模的。舉例: User 尋找附近的餐館，這樣最好回傳各式不同國家、料理風格的餐館讓 User 有較多選擇，而不是選來選去都是類似的料理。

以前的研究在同時處理 k-NN 和多樣性時主要有兩個缺點，本論文中提出的方法克服了以下缺點:
(1) 依賴 User 提供的線性組合來判別多樣性的程度
(2) 因為這項議題是 NP-hard，以往的論文並沒有提供最佳解決方案

為了在靠近性與多樣性這兩個條件之間找出最佳的答案集，我們使用 「[linear skyline queries](https://ieeexplore.ieee.org/document/7113306)」。 傳統 [skyline quries](http://dblab.csie.ncku.edu.tw/home/intro/ldb/index.html) 將靠近性與多樣性各視為一個維度，將資料點 (元素) 散落在這個平面上，其中若 A 點的較 B 點靠近 query q 且 A 點的多樣性較 B 點高，則稱 「A dominate B」。 kDNN 的結果集不會包含任何被其他元素 domiate 的元素，linear skyline quries 幫助我們過濾較差的解，並直觀呈現。

linear skyline 有兩個特點:
(1) 回傳較傳統 skyline 更小的集合
(2) 集合套用任何靠近性與多樣性的線性組合都是最佳解

>
**Fig. 1.** 傳統天際線與線性天際線的圖解。其中連接起來的點表示未被任何其他點 dominate 的資料點

本文主要貢獻是提出 2 種利用 skyline 求 kDNN quries 最佳解的演算法。在我們的演算法中，候選集合是依據與查詢條件的靠近度遞減排序，也就是順序越後面的集合距離查詢條件越遠。這有利於檢查候選點是否在 skyline 上，因為每個更後面的子集合必須比先前的子集有更高的多樣性，否則會被 dominate。

本論文的其餘章節如下: 在第 2 節中，我們將簡要介紹相關研究；在第 3 節中正式定義 kDNN quries； 在第 4 節中進行實驗與評估演算法；第 5 節討論實驗的結果；第 6 節總結我們的發現和對於未來研究方向的建議。

## 相關研究

要求靠近性同時保持多樣性的想法源自於信息檢索，在 Maximal Marginal Relevance (MMR) 是最早針對這種需求發明的演算法，MMR 在每個 step 都會產生比前一個 step 靠近性與多樣性更高 (高邊際相關性) 的解。

在另一篇論文中，Vieira 等人考察了若干種方法，由於他們聲稱他們提出的 Greedy Marginal Contribution (GMC) 和 Greedy Randomized with Neighborhood Expansion (GNE) 效果最好，我們針對這兩種方法討論，GMC 與 MMR 相似，會依據邊際相關性排序解。 GNE 則會先設定結果集的數量，在每次迭代中隨機選擇排名最高的元素，並將其和當前結果集中的元素交換，以求得更佳結果集。在後文會拿我們提出的方法與 GNE 比較，因為它是精度最高的解法。

*很雜，暫時沒翻譯後面*

## 定義問題

k-Diverse NN (kDNN) 將多樣性納入 k-NN 問題中，目的是為了找到一組有 k 個元素的解，這組解的元素必須盡可能靠近 query $q$ 且這組解的元素盡可能多樣化。

令數據點的集合 $P= \{p_1,p_2, ... ,p_n\}$ ，本論文將數據點 $p_i \in P$ 與 $q$ 的歐幾里得距離定義為 $d(p_i,q)$，$d(p_i,q)$ 越小則 $p_i$ 與 $q$ 越靠近。沿用上述定義，令子集合 $S \subseteq P$，$S$ 與 $q$ 的距離定義為 $q$ 到 $S$ 中任一元素的最大距離，即 $\displaystyle d(q,S) = \max_{s_i \in S}\{d(q,s_i)\}$。

本論文將多樣性分為兩類: 空間多樣性與種類多樣性。前者由兩個資料點的距離決定，令 $p_i,p_j \in P$，空間多樣性 $div(p_i,p_j) = d(p_i, p_j)$ ，如此定義是為了找到在空間中分佈良好並覆蓋不同區域的資料點。關於類別多樣性，假設 $G = \{g_1,g_2,...,g_{|G|}\}$ 為所有種類的集合，對於 $p_i \in P$ 所屬的種類標示為 $g(p_i) \in G$ ，注意不同的資料點可以屬於同一個種類。

接下來我們針對每個種類間的差異表示為矩陣 $M_{|G|×|G|}=(m_{p,q})$ ，為了簡單起見讓 $0≤m_{p,q}≤1$ ，當 $p = q$ 時 $m_{p,q} = 0$ 代表完全沒有差異。更進一步說明，我們將種類 $g_p$ 與種類 $g_q$ 的差異表示為 $m_{p,q}$ ；將資料點 $p_i$ 與資料點 $p_j$ 的種類的差異表示為 $m_{g(p_i),g(p_j)}$。

最後，集合 $S \in P$ 的空間多樣性定義為集合 $S$ 中任兩個資料點的最短距離，即 $\displaystyle div(S)=\min_{(p_i,p_j ) \in S \wedge (p_i \neq p_j)}\{div(p_i,p_j)\}$。

接下來定義 skyline 與 linear skyline 的 domination:

**Definition 1.**

令子集合 $R$、$T$ 為大小為 $k$ 的集合且 $R,T \subseteq P$，當

$$\begin{align*}
&d(q, R) < d(q, T) \ \ and \ \ div(R) \geq div(T) \ \ or \\
&d(q, R) \leq d(q, T) \ \ and \ \ div(R) > div(T)
\end{align*}$$

此時稱 $R \ dominates \ T$ ，記為 $R \prec T$，意義是 R 更靠近 query $q$ 並且多樣性不小於 $T$，或 $R$ 具有較高的多樣性並且與 $q$ 的距離不大於 $T$ 與 $q$ 的距離。

對於傳統 skyline，在天際線上的點全是 non-dominated，定義為:

$$\{S \subseteq P \ s.t. \ \nexists R \subseteq P: R ≺ S, |S|=|R|=k\}$$

在本論文提出的解法中，我們會先找出傳統的 skyline 然後從中找出 linear skyline。

**Definition 2.**

令 $SK$ 為一傳統 skyline、$w$ 是二維的權重向量、向量 $r$ ($t$) 表示元素 $R$ ($T$) 的靠近性與多樣性，當

$$\forall w \in {\rm I\!R^2} \ \ \exists R \in SK' : w^Tr > w^Tt $$

此時稱 $SK' \subseteq SK \ lineary \ dominates \ T \in SK$ ，記為 $SK' \prec_{lin} T$。所有元素皆為 linearly non-dominated 的最大集合稱為 linear skyline。

請注意，與傳統 skyline 的 domination 方式相比，尋找一組 linear skyline 的 domination 需要與其他一個以上的集合進行比較。由此我們定義本論文要探討的問題:

**Problem Definition.**

給定 query $q$、正整數 $k$、資料點的集合 $P$，k-Diverse NN (kDNN) 查找所有 $k$ 個元素的 linearly non-dominated 集合 $S \subseteq P$。

## 解決方法

我們提出了兩種使用 linear skyline 的 kDNN 的演算法，這兩種演算法都是先找出傳統的 skyline，再求取 linear skyline。首先依照 $d(q,S)$ 的升序排序候選集合，同時，因為這些候選集合都是 non-dominated，意味著越後面的集合多樣性越高。排序較前面的候選集合可以建立多樣性的 lower bound，表示為 $minDiv$。本論文提出的兩種解決方案都使用上述方法來過濾子集。

第一種解法稱為 **Recursive Range Filtering (RRF)**，RRF 使用遞迴在每個回合從候選集合 $C$ 挑選一個元素加進 partial solution $S'$ ，使得 $S'$ 的多樣性高於 $minDiv$。第二種解法稱為 **Pair Graph (PG)**，其原理為排除包含元素對 $(p_i,p_j) \subseteq P$ 且 $div(p_i,p_j)<minDiv$ 的集合，以確保剩餘的候選集有足夠多樣性。

在介紹 RRF 和 PG 之前，我們先為比較基準建立一個暴力演算法 **brute-force (BF)**，BF 會生成所有大小為 $k$ 的集合 $S \subseteq P$，若 $S$ 未被任何任何其他集合 dominate，就將 $S$ 加入 skyline。

RRF 和 PG 既適用於類別多樣性又適用於空間多樣性，但注意對於類別多樣性時，只需要找出每個類別中距離 query $q$ 最近的點，就能找到整個 skyline ，換句話說，只要找到這些點演算就可以停止。

RRF 和 PG 均基於下面介紹的演算法 1，只有其中的 $findSetMaxDiv$ 有各自的實作方式，而 $findSetMaxDiv$ 用以求得一樣靠近性下擁有最大多樣性的集合。


我們解釋一下演算法 1: 以 query 點 $q$、答案集的大小 $k$、資料點的集合 $P$ 作為 input。
第 1 行的 $S$ 代表最靠近 $q$ 的集合，擁有最小的 $d(q,S)$
第 2 行將 $s_i \in S$ 從 $P$ 中移除，也就是將天際線 $P$ 中移除
第 3 行將 $S$ 加入用以檢驗的集合 $P'$
第 4 行將 $S$ 加入集合 $skyline$
第 5 行將初始的最小多樣性 $minDiv$ 設為 $div(S)$，也就是 $S$ 中任兩元素的最短距離
接 6 來進入迴圈，執行直到 $P$ 裡沒有元素
第 7 行找出距離 query $q$ 最近的元素 $p_d$
第 8 行將 $p_d$ 從 $P$ 移除
第 9 行 $C \subseteq P'$ 是一個候選集合，裡面每個元素與 $p_d$ 的多樣性都大於 $minDiv$
第 10 行 $findSetMaxDiv$ 尋找擁有最大多性 $div(S)$ 的集合 $S$ ，並且 $div(S) > minDiv$、$p_d \in S$、$S \subseteq C$，RRF 和 PG 對此有不同實作
第 11 行到第 14 行會將 $skyline$ 與 $S$ 聯集，然後更新 $minDiv$ 為 $div(S)$
第 15 行將 $p_d$ 加入檢驗集合 $P'$

因為每次迴圈中 $p_d$ 必定是集合 $S$ 裡距離 $q$ 最遠的資料點，所以 $d(q,S)=d(q,p_d)$，由此知道 $findSetMaxDiv$ 檢查的所有集合與 $q$ 的距離都相同，因為這些集合必定包含 $p_d$。

*下面驗證演算法的正確性先不翻譯*

### 4.1 Recursive Range Filtering (RRF)

接下來說明 RRF 的 $findSetMaxDiv$ 實作


首先宣告 RRF 所需的變數:
- 一個集合 $S'$，初始元素只有 $p_d$
- $C$ 為演算法 1 第 9 行求得的集合，稍後會用來與 $S$ 進行運算
- $n$ 為要加入 $S'$ 的元素個數使得 $S'$ 能湊齊 $k$ 個元素
- $setMaxDiv$ 為擁有最大多樣性的集合，初始為空集合
- $minDiv$ 即之前提過的多樣性的 lower bound

第 1~8 行，若只需要加入一個元素到 $S'$，則只需要一個個將 $c_i \in C$ 加入 $S'$ 計算多樣性，然後將多樣性最大的集合設為 $SetMaxDiv$ ，$n=1$ 可以視為 RRF 遞迴演算法的中止條件
第 10~19 行 for 迴圈從 $C$ 中抽取出元素 $c_i$ 與目前的 $S'$ 聯集，將 $S'$ 和 $n-1$ 傳入 $findSetMaxDiv$ 求擁有最大多樣性的集合。

*下面舉例不翻譯*

### 4.2 Pair Graph Solution (PG)

PG 的想法是將元素兩兩配對，使得 $div(p_i,p_j) > minDiv$ 以構造一 non-dominated 集合。兩個元素對如果有共同元素便可以組合成集合，例如: $div(p_i,p_j) > minDiv$ 且 $div(p_j,p_l) > minDiv$ 時，可以得到 $S_3=\{p_i,p_j,p_l\}$；同樣的，$S_3$ 可以與 $div(p_l,p_m)>minDiv$ 結合變成 $S_4=\{p_i,p_j,p_l,p_m\}$。注意，不保證 $div(S_4) > minDiv$，除非 $div(p_i,p_l),div(p_i,p_m),div(p_j,p_m) > minDiv$。

>
**Fig. 3.** 範例圖

圖 3 展示 PG 的步驟，假設 $p_d=p_6$、$k=4$、$minDiv=1$，按照先前的定義，所有 non-dominated 集合都必須包含 $p_d$ ，所以我們將 $p_6$ 設為起始點，並且以行經 4 點的路徑代表集合，分別為 $PT_1=(p_6,p_1,p_3,p_5), \ PT_2=(p_6,p_3,p_4,p_5), \ PT_3=(p_6,p_1,p_3,p_4)$。計算每個路徑各自的多樣性，$PT_1$ 的多樣性為 $1.12$，因為這是 $PT_1$ 中任兩點最小的多樣性，因為 $1.14 > minDiv$ 所以 $PT_1$ 是加入 skyline 的候選集合；再來 $PT_2$ 的多樣性為 $1.35$，所以 $PT_2$ 是更佳的候選集合；再來 $PT_3$ 無法成為候選集合，因為 $p_1,\ p_4$ 沒有邊相連，因此 $div(p_1,p_4) < minDiv$。最後得到 $PT_2$ 為多樣性最高的集合。

下面解釋演算法


使用 Dijkstra’s 演算法
第 1、2 行 $\mathcal{P}$ 代表 $p_d$ 與候選集合 $C$ 中的元素對，以及 $C$ 中多樣性大於 $minDiv$ 的元素對
第 3 行 $G(V,E)$ 是根據 $\mathcal{P}$ 建立的圖
第 4~7 行先將每個邊 (行經兩個點的路徑) 都加入 $queue$ 中，$queue$ 會依照每個 $PT$ 中的邊的最大多樣性來降序排列
第 8 行當 $queue$ 非空時執行迴圈
第 9 行從 $queue$ 中取出擁有最高多樣性的邊的路徑命名為 $PT$
第 10、11 行若 $PT$ 包含 $k$ 個點則回傳
第 13 行將 $v$ 設為 $PT$ 的最後一個點
第 14~18 行一一取出與 $v$ 之間有邊的點，若 $ub(PT \cup u) > minDiv$ 即 $PT$ 的邊的最大多樣性大於 $minDiv$ 時，把 $PT \cup u$ 加入 $queue$ 中，這呼應前面提到的:有共同元素可以組合成新的集合

*Theorem 不翻譯*

### 4.3 From Conventional Skylines to Linear Skylines

為了從傳統 skyline 擷取 linear skyline，我們參考另一篇論文，該論文提出 bi-criteria road network。假設 $SK$ 是傳統 skyline、$D,R,T \in SK$，他們可以用二維的 cost vector 來表示，分別為 $d,r,t$，令 $n$ 為 $R$ 與 $T$ 之間的一個向量的法向量，若 $n^Tr=n^Tt>n^Td$ ，則稱 $R,T$ linearly dominate $D$，即 $\{r,t\} \prec_{lin} d$。

擷取 linear skyline 的流程為以上述方式不斷從傳統 skyline 淘汰在任兩個向量之下的向量。假設 $LS$ 是儲存 skyline 的列表，目前有 $i$ 個元素，當要插入新元素 $S^{i+1}$ 時，依序由列表的尾端到首端檢查是否滿足 $\{s^{i-1},s^{i+1}\} \prec_{lin} s^{i}$，若滿足此條件則將 $S^i$ 從 $LS$ 移除，然後檢查 $\{s^{i-2},s^{i+1}\} \prec_{lin} s^{i-1} \ ...$，直到檢查完 $LS$ 的首個元素或是確定 $S^{i+1}$ 為 linear non-dominated。

## 5 實驗

首先觀察 RRF, PG, BF 的效能，再來說明為何 PG、RRF 比另一篇論文的 GNE 好。我們的程式以 java 實作，運行在 4 個 linux vCPU 與 8 GB 記憶體上。輸入的資料點數量介於 $100$ 至 $1000$ 之間，為常態分布、高斯分布或叢集，$k$ 介於 $3$ 到 $10$ 之間。實驗結果 (1) 用對數當作圖表刻度，(2) 如果 $10$ 分鐘內還沒執行結束則終止程式並計作執行 $10$ 分鐘

### 5.1 空間多樣性

首先評估 BF, RRF, PG 在考慮空間多樣性時的特性，兩點的空間多樣性由歐氏距離決定。

>
**Fig. 4.** 考慮空間多樣性的執行時間

- **$k$ 的影響**
由 Fig. 4a 可以發現當 $k > 3$，BF 無法在 10 分鐘內給出答案。在 $k=3$ 時 RRF 約莫比 PG 快 30%，但是當 $k$ 更大時 PG 比 RRF 更快，分析其中原因是 RRF 在每一層遞迴都必須針對所有 $c_i$ 計算多樣性而浪費時間，並且每個候選集合都會被考慮到。而 PG 則會優先考慮多樣性 upper bound 較高的集合，當找到一個大小為 $k$ 的集合就停止計算，所以當 $k$ 較大時 PG 速度會比 RRF 快，對於 $k=3$，PG 的 upper bound 計算和 queue 操作的成本相對較 RRF 的演算法高。
- **資料點數量的影響**
與前面分析的結果類似，BF 在任何數量下效果都很差、RRF 在數量少時執行時間較短、PG 在數量多時執行時間較短
- **資料點分布的影響**
因為 BF 是暴力法，資料分布不會有任何影響、...

### 5.2 種類多樣性

### 5.4 效能

## 總結

本篇論文解決了 kDNN 查詢，即 k-NN 查詢的一種變體，這個問題包括找到盡可能靠近查詢點的元素，同時又要盡可能地多樣化。我們已經考慮了兩種不同的多樣性概念，即空間多樣性和分類多樣性。過去研究提出的解決方案都很類似，並且要求用戶為每種類型的多樣性定義權重，我們的方法基於 linear skyline 可以找到所有在 $任意$ 線性組合下 $最佳$ 的結果。

RRF 利用遞迴不斷減少集合的候選點同時找出多樣性夠大的解，PG 透過修剪多樣性小的元素組來過濾多樣性小的集合。實驗表明 (1) RRF和PG都比簡單的解決方案快幾個數量級 (2) 對於更高的 $k$ 值和更多的點，PG 的性能優於 RRF，反之 RRF 優於 PG。

在未來的研究中，我們希望調查道路網絡中的kDNN查詢，實際數據集的使用，並進一步探索其他領域（例如文本檢索）中的多樣性概念。