基于k-means++的動態構建空間主題R樹方法

（江蘇大學計算機科學與通信工程學院，江蘇鎮江 212013）

0 引言

隨著移動互聯網的迅猛發展，推動了基于地理位置信息服務（Location-Based Service，LBS）的大量普及。最典型的例子就是地圖類的服務，比如百度地圖、高德地圖、外賣平臺等，伴隨著的還有空間數據的極速增長。由于空間數據的多維性以及位置關系的多樣性，空間數據的處理與存儲問題已經成為了亟待解決的問題。大多數空間數據索引的構建是通過R-樹來完成的，R-樹是B-樹在高維上的擴展［1］，R-樹結構簡明、動態性高、適用范圍廣［2］。在進行R-樹樹空間區域檢索時，從根節點出發，由頂向下逐層縮小范圍直到葉子節點滿足搜索條件。

目前，學術界對R-樹的研究主要有兩個方面：一種是針對空間聚類算法方面的研究；另一種是針對R-樹結構相關算法調整方面的研究。聚類算法構建R-樹中，將R-樹操作中的分裂算法改進為聚類算法中的多路分裂，對R-樹的研究轉向為聚類構建。2016 年胡昱璞［2］提出動態確定k值的空間聚類算法（Dynamical K-Value spatial Clustering algorithm，DKSC），該算法通過聚類劃分空間數據，把同一子空間的數據組織在同一個子樹下，從根節點到葉子節點逐層構建R-樹，形成高效的R-樹空間索引。2017 年彭召軍等［3］針對傳統的k-means聚類算法對初始值非常敏感，聚類過程較為復雜的問題，在R*-樹的構建過程中引入聚類技術，對R*-樹的基本結構加以改進，提高索引樹的空間利用率。R-樹相關算法的調整研究，一般是對R-樹插入算法中的分裂算法重構或是改變插入節點模式。2017 年楊澤雪［4］針對已有的QR-樹（Quad R-tree，QR-tree）索引結構在節點分配中，可能存在較小的對象落入較大的節點中的問題，提出一種混合空間索引結構松散QR-樹（Loose Quad R-tree，LQR-tree），有效地解決了節點下移的問題，彌補了QR-樹的查詢缺陷。

現有的聚類構建R-樹方法存在著各種優缺點。例如利用k-medoids 算法［5-6］聚類空間數據，構造索引的過程中，需要指定聚類數k值，這不符合空間數據的分布不規律性，k值不定；又如利用聚類算法構建空間數據索引時，初始聚類中心隨機或指定選取，聚類結果容易受到離群空間數據的干擾；現有的聚類構建R-樹方法中，改進了各類聚類算法，但僅僅是基于空間數據地理位置上的改進，并沒有考慮空間數據文本間的聯系，在聚類中心的選取上未考慮語義級的選取，只是基于歐氏距離的選取。

k-means++［7-8］聚類算法對k-means 算法確定初始聚類中心提出改進，步驟如下：1）從數據集中隨機選擇一個樣本作為初始聚類中心；2）計算每個樣本到聚類中心的距離；3）選取距離前一個聚類中心距離最遠的樣本作為新的聚類中心；4）重復步驟2）、3）得到k個聚類中心。本文就是對聚類中心選取以及k值確定作出優化。

主題模型主要利用吉布斯采樣、變分推斷、非負矩陣分解等機器學習算法從高維稀疏的文本特征空間中推斷出潛在主題信息［9］。以潛在狄利克雷分布（Latent Dirichlet Allocation，LDA）模型［10］為代表的主題模型是一種非監督的機器學習方法，它能有效地提取大規模文檔集和語料庫中的隱含主題，其良好的降維能力、建模能力及擴展性，使其成為近年來主題挖掘領域中熱門研究方向之一［11］。空間數據包含空間位置數據和空間文本數據［12-14］，現有的構建R-樹僅僅是對空間位置數據進行劃分；而空間文本數據，例如：肯德基、沙縣小吃，是具有關聯性的文本數據，可劃分為美食，是對文本數據的分類。因此，將主題模型LDA 引入進R-樹的構建中理論上具有可行性［15］。

現有的R-樹空間聚類技術在聚類中心的選取上通常通過隨機指定或者只計算空間數據間的歐氏距離，未考慮空間數據中文本數據間的主題相關度。本文在k-means++的基礎上，提出了一種動態k值構建空間主題R-樹（Topic R-Tree，TR-tree）方法，通過引入LDA 主題模型，優化聚類中心選取、優化聚類測度函數來動態確定k值，使得聚類算法構建R-樹結構更加緊湊，R-樹節點間文本數據關聯性更高，從而提高R-樹檢索效率。

1 相關定義

針對k-means++的動態構建空間主題R-樹方法中存在的問題，進行如下定義：

定義1聚類均值點：

數據均值點Ci（i=1，2，…，k）為劃分區域的距離中心最近的空間數據，其中Q、P分別為可以劃分一個區域的兩個空間數據。

定義2距離指標：

其中：n表示一個區域下空間數據的數量；D表示區域面積（m2）；若一個區域下的空間數據到數據均值點Ci的距離小于R，則將該數據記為Ci的鄰近空間數據。

定義3聚類測度函數：

聚類測度函數的作用是在聚類劃分的過程中，直到聚類測度函數值收斂，此時確定聚類數k值。本文設計的聚類測度函數將距離及主題概率結合，得到poiListi中與每個數據均值點Ci的距離，以及它們的主題概率之和。其中，poiListi為鄰近空間數據集，d指poiListi中的單個空間數據，k為聚類數，Ci為數據均值點，a為關于距離及主題的平衡參數，取值在0～1。a越大代表傾向距離影響因素，越小代表傾向主題概率影響因素，ωd為每個空間數據與數據均值點相同的主題的概率。在每次劃分一個區域后通過距離指標R得到其鄰近空間數據后，計算此時對應k值的聚類測度函數Jk，并與上一個k值所對應的Jk-1比較；若此時函數收斂則取當前k值為當前區域聚類數，若函數分散則繼續劃分，從而動態確定k值。

2 構建TR-tree

k-means++算法優化了k-means算法的聚類中心選取的問題，但同樣在k值選取上采用先確定k值。在不確定的空間數據中，先確定k值不符合實際空間數據的分布，因此本文改進了k-means++算法，采取動態確定k值的算法，更符合空間數據分布不確定的情況，使得聚類算法構建R-樹結構更緊湊，R-樹空間索引效率更高。

算法的基本思想是：獲取指定的最小外接矩形，將其看作一個大類，初始聚類數k=1，根據定義1 得到最小外接矩形（Minimum area Bounding Rectangle，MBR）［16］初始類數據均值點；通過定義2距離指標R得到當前數據均值點Ci鄰近空間數據集poiListi；通過文本主題分類對poiListi中的poi數據進行分類，得到每個空間數據的主題分布概率ωd；計算當前k值對應的聚類測度函數值Jk；將Jk與前一次聚類測度函數值Jk-1進行比較，若此時函數收斂，則取當前k值為當前R-樹這一層的聚類數；若此時函數發散，則通過距離選取距離前一個數據均值點最遠的空間數據作為后續數據均值點，得到后續MBR；對新的MBR繼續劃分，直至k值遞增至M；其中M為R-樹節點的最大條目數，對于R-樹中的節點，M和m分別為一個節點中的最大和最小條目數，如果節點是根節點，則該節點所容納的條目數范圍為2～M；如果節點不是根節點，則該節點所容納的條目數范圍為m～M。通過主題概率，找出poiListi中出現次數最多的地理數據作為聚類中心，再遞歸找出各個MBR 的聚類中心PK；以k個聚類中心PK作為根節點的子節點，進行聚類構建R-樹，構建R-樹時，優先選取與PK主題概率相似度較高的空間數據并且該空間數據滿足距離指標R，保證每個節點上的子樹主題概率相似度較高，PK為poiListi中出現概率最高的空間數據，在進行R-樹構建時，又優先選擇與PK主題概率相似的空間數據，因此提高了子樹的主題關聯度；假設父節點有n個空間數據，檢查每個聚類后的空間數據個數N，子節點的聚類個數為k，若N=n/k，則此時停止分配；若N＞n/k則通過距離分配到最近的且未填滿的PK；以每個子節點作為子樹的根節點重復進行聚類構建R-樹，形成主題R-樹。

構建TR-tree主要分為3個步驟：

步驟1 得到k個聚類數，例如圖1 所示，C1和C16可劃分一個MBR，C8為該區域初始聚類均值點，選取距離C8最遠的C16劃分新的區域R2；計算此時的J2，函數分散繼續劃分，選取距離C16最遠的C1及距離C1最遠的C11為新的區域R1，再次判斷J3；從而得到聚類數k值。

圖1 確定k個聚類簇Fig.1 Determination of k clusters

步驟2 聚類中心的確定：通過步驟1得到每個數據均值點Ci的鄰近空間數據集poiListi，將出現概率最多的數據作為此區域的聚類中心。

步驟3 構建空間主題R-樹：構建時優先選擇鄰近空間數據集poiListi中與聚類中心PK主題相似度較高的空間數據，例如圖2 所示，根據一個空間區域初始數據均值點為C6，通過距離指標R得到poiListi=｛C5，C6，C7，C8，C9｝，計算主題概率，計算聚類測度函數值并且重新劃分；得到R3、R4、R5、R6空間區域并且對其中主題概率較大的空間數據作為聚類中心；在構建R-樹時，C5滿足R3、R5 的距離指標R，但其主題概率偏向C2，因此劃分到R3中，構建的R-樹如圖3所示。

圖2 根據距離指標劃分MBRFig.2 MBR division by distance index

圖3 TR-treeFig.3 TR-tree

構建TR-tree算法偽代碼如下。

輸入：n個空間數據D=｛d1，d2，…，dn｝

輸出：子樹頭節點

3 實驗與結果分析

3.1 實驗環境與數據集

為了驗證TR-tree 的性能，將本文提出的TR-tree 與R*-樹［3］、NDRKR-樹（Nearest neighbor Dynamic K R-tree，NDRKRtree）［17］進行對比，R*-tree 采取改進的k-means 算法進行聚類構建，NDRKR-tree 采取改進的k-means 算法以及通過歐氏距離確定聚類測度函數，本文優化聚類測度函數，引入LDA 主題模型，進行以下對比實驗。實驗平臺為2.3 GHz Inter Corei5 戴爾筆記本，操作系統為Window 10，編程語言是Python，編程工具為PyCharm。數據集分為兩個部分：空間文本數據為阿里云天池公開的天貓商品描述文案數據（實際數據進行LDA 主題映射時，每一段語句都會分為很多類主題，選取主題概率最高的推斷其為這類主題，對大量數據進行LDA主題映射有較好的主題分類）；空間位置數據為公開的杭州市POI地理位置數據。

為了使實驗結果具有代表性，實驗數據中空間文本數據隨機取天貓商品描述文案D1：15 000、D2：20 000、D3：25 000、D4：30 000 個，地理位置數據隨機取杭州市公開的POI 數據D1：15 000、D2：20 000、D3：25 000、D4：30 000 個，將其整合為空間數據。實驗參數：M為R-樹節點的最大數目其與動態k值相關，平衡參數a代表主題與歐氏距離的關系。

3.2 性能及實驗分析

取參數M=10，平衡參數a=0.2，TR-tree 與R*-tree、NDRKR-tree 進行構建時間、查找時間以及節點間重疊度進行對比實驗。

3.2.1 構建R-tree時間

由圖4 知，TR-tree 在整體的構建時間上相較于其他兩個構建算法上時間略有增加，這主要是由于本文提出的算法在確定聚類中心時增加了LDA 主題映射從而增加了算法的時間復雜度。

圖4 不同算法構建R-tree時間的對比Fig.4 Comparison of R-tree construction time of different algorithms

3.2.2 算法查找時間

從圖5知TR-tree的查找效率相較于其他兩個算法有明顯的提升，尤其在數據量大的情況下較為明顯，這是由于隨著數據的增加，數據間的主題相關度更加明確，數據間的關聯度也更高，從而提升了查找效率。

圖5 不同算法查找時間的對比Fig.5 Comparison of search time of different algorithms

3.2.3 節點間重疊度

圖6 為3 個算法在節點重疊度方面的比較，從結果可知TR-tree 在數據量越大時，節點間重疊度相較其他兩個算法越小，正是由于數據間的主題相關度越高，子樹節點間的主題更加明確，從而使節點的重疊度降低，從而查詢效率越高。

圖6 不同算法節點間重疊度的對比Fig.6 Comparison of overlapping degree between nodes in different algorithms

3.2.4 多組平衡參數

表1表示取參數M=10，平衡參數分別為0.2、0.5、0.8下，數據集D1、D2、D3、D4 在TR-tree 算法中節點間的重疊度。由式（3）可知，a越小代表聚類測度函數與主題關聯度越高，從結果可知隨著數據的增大，a越小節點間的重疊度越小，間接說明主題關聯度越高，TR-tree節點重疊度越低。

表1 不同平衡參數的節點重疊度Tab.1 Degree of overlapping degree between nodes with different balance parameters

表2 為TR-tree 在數據集D1、D2、D3、D4 時查找時間的實驗數據。由表2 可知，當節點數目取20，a取0.2，數據量增大時，查找效率優于其他對比數據，表明當數據量增大時，主題映射較為準確，對聚類測度函數起到了約束作用，從而影響k值的確定以及節點間的關聯度，進而提高了查找效率。

綜上所述，本文提出的基于k-means++的空間主題R-樹，在查找效率、節點間的重疊度在空間數據量較大時，優于其他兩個對比算法。

表2 數據集查找時間 單位：sTab.2 Dataset search time unit：s

4 結語

在k-means++算法的基礎上，本文結合LDA 主題模型，優化動態選取聚類中心算法，提高R-樹子樹的主題關聯度；優化聚類測度函數，通過距離加主題概率確定聚類數k值，動態構建空間主題R-樹。通過實驗將本文方法TR-tree與R*-tree、NDRKR-tree 進行對比，驗證了TR-tree 在空間查找效率以及節點重疊度方面具有明顯的優勢。接下來可對TR-tree 進行下一步的研究，主要在如何提高R-樹的構建速度方面，在聚類測度函數中，需要計算空間數據間的距離，時間復雜度有待提升，以及如何對聚類測度函數進行進一步的優化。