快速跨最佳和地理值域分群法

Abstract

之前的研究已點出關於最佳化和地理位置值域的跨值域分群問題。然而，之前的研究既沒有明確地定義地理位置值域連續性限制，也沒有提出足夠效率的演算法。本篇論文定義了跨值域分群問題的連續性限制。在此本篇論文著重的問題裡，使用者必須制定連續性限制的參數和分群數量。我們提出的演算法「K-means with Local Search 」（簡稱為 KLS）由三個階段組成：轉換階段、粗略分群階段以及微調分群階段。首先，將符合連續性限制的資料以 ConGraph 表示（ConGraph意為 CONnected Graph）。接著，藉由ConGraph的協助，加上K-means和 local search 的概念，我們設計了一個有效率的粗略分群法。最後，將粗略分群的結果在最少的準確度損失下，微調成符合使用者要求的分群數。我們的實驗結果顯示出 KLS 能夠正確且有效率地完成分群。

Prior works have elaborated on the problem of joint clustering in the optimization and geography domains. However, prior works neither clearly specify the connected constraint in the geography domain nor propose efficient algorithms. In this paper, we formulate the joint clustering problem in which a connected constraint and the number of clusters should be specified. We propose an algorithm K-means with Local Search (abbreviated as KLS) consisting of three phases: the transformation phase, the coarse clustering phase and the fine clustering phase. First, data objects that fulfill the connected constraint is represented as the ConGraph (standing for CONnected Graph). In light of the ConGraph, by adapting the concept of K-means and local search, an algorithm is devised to coarsely cluster objects for the purpose of efficiency. Then, these coarse cluster results are fine tuned to minimize the dissimilarity of the data objects in the optimization domain. Our experimental results show that KLS can find correct clusters efficiently.