[發明專利]一種動態K值聚類構建主題R樹方法

有效

• 申請號: 202010025090.5
• 申請日: 2020-01-10
• 公開（公告）號: CN111221937B
• 公開（公告）日: 2023-05-09
• 發明（設計）人: 鄒志文;秦程
• 申請（專利權）人: 江蘇大學
• 主分類號: G06F16/31
• 分類號: G06F16/31;G06F16/35;G06F16/29;G06F18/23213
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種動態K值聚類構建主題R樹方法，其特征在于，包含如下步驟：

1)利用地圖開放的api獲取城市中路網數據Citydataloca₁、loca₂…loca_M，其中loca_i＝lon_i、lat_i、poi_i表示第i個地理位置信息，其中lon_i、lat_i、poi_i分別表示經度、維度、空間文本信息；

2)獲取指定的最小外接矩形MBR，將其看作一個大類，此時初始聚類數k＝1，通過經緯度得到MBR初始類數據均值點C₁；

3)選取距離初始類數據均值點C₁最遠的空間數據C₂、距離C₂最遠的空間數據C₃作為新的數據均值點，計算C₁、C₂的經緯度之差，得到第二個MBR，計算C₂，C₃的經緯度之差，得到第三個MBR；

4)此時k值相應增加，計算當前k值對應的聚類測度函數值J_k；

5)將J_k與前一次聚類測度函數值J_k-1進行比較，若此時函數收斂，則取當前k值為聚類數；若此時函數發散，則對新的MBR重復步驟2)到步驟5)，k值繼續遞增至M；

6)通過距離指標R得到當前數據均值點C_k鄰近空間數據集poiList；

7)通過文本主題分類對poiList中的poi數據進行分類，找出出現次數最多的地理數據作為聚類中心，再遞歸找出各個MBR的聚類中心P_k；

8)以k個聚類中心P_k作為根節點的子節點，進行聚類構建R樹；并以每個子節點作為子樹的根節點重復步驟3)-步驟7)，進行聚類構建R樹；

9)自底向上對每個節點構建主題倒排索引，父級存儲著聚類中心的主題索引，形成主題R樹；

所述步驟2)中MBR初始類數據均值點C₁的獲取方法如下：

2.1)通過地圖開放的api在地圖上指定四個地理坐標loca₁、loca₂、loca₃、loca₄；

2.2)計算這四個點的經緯度之差，得到初始類數據均值點C₁的經緯度信息；所述步驟4)中，計算當前k值對應的聚類測度函數值J_k的方法如下：其中，S_j為MBR劃分區域內的路網數據集，p指S_j中的單個路網數據，k為聚類數，r為S_j的數據均值點；

所述步驟6)中，通過距離指標R得到鄰近空間數據集poiList的方法如下：

6.1)定義距離指標其中，n表示MBR下路網數據的數量，D表示給定的MBR區域面積，用d_i表示一個MBR下的路網數據到數據均值點Ci的距離，若d_i＝R，則將第i個數據記為該數據的鄰近空間數據；

6.2)得到聚類數據均值點C_k領近空間數據集poiListloca_p1,loca_p2…loca_pn；

所述步驟8)中，進行聚類構建R樹的方法如下：

8.1)k值遞增，當聚類測度函數收斂時，取這k個聚類中心P_k作為根節點的子樹，構建R樹的第二層；

8.2)假設父節點有n個空間數據，檢查每個聚類后的空間數據個數N_j，若則此時停止分配；若則通過距離分配到最近的且未填滿的P_i；

8.3)以每個子節點作為子樹的根節點重復步驟3)-步驟7)，進行聚類構建R樹；

所述步驟9)中，進行自底向上對每個節點構建主題倒排索引的方法如下：

9.1)對鄰近空間數據集poiList的每個空間文本信息進行主題分類，對其建立主題倒排索引；

9.2)將聚類中心P_k作為父級的主題索引，再自底向上構建主題倒排索引。