王慧東，宋耀蓮，田榆杰

(昆明理工大學(xué) 信息工程與自動化學(xué)院，昆明 650500)

0 引 言

時空聚類分析是時空數(shù)據(jù)挖掘領(lǐng)域的重要分支，是計算機科學(xué)與地球信息科學(xué)交叉領(lǐng)域中最前沿、最具挑戰(zhàn)的研究課題之一[1]。其目的在于從時空數(shù)據(jù)庫中提取具有相似特征的密集時空對象集合，它是從空間維度到時空維度的擴展。時空數(shù)據(jù)的可視化分析[2-4]同樣是近年數(shù)據(jù)可視化研究領(lǐng)域的熱點前沿，以可視環(huán)境下交互式挖掘分析實現(xiàn)問題可以更高效地表達數(shù)據(jù)包含的信息。

時空聚類在疾病異常趨勢[5]、全球氣候變化[6]、犯罪熱點分析[7]、地理現(xiàn)象分析[8]等領(lǐng)域的研究中起到了重要作用，輔助用戶更好地發(fā)現(xiàn)和分析事務(wù)發(fā)展變化的趨勢和規(guī)律。趙其杰等[9]針對小樣本及混疊類群提出一種密度-距離的新式聚類優(yōu)化方法；李曉璐等[10]針對具有密度分布非均勻特征的數(shù)據(jù)集，提出基于高斯混合模型的DBSCAN聚類算法分析車站內(nèi)乘客的聚集特征；XIE等[11]針對DBSCAN算法聚類精度的問題，提出了一種設(shè)定參數(shù)的新方法來提高聚類的準確率；BIRANT等[12]基于DBSCAN算法之上考慮了時間因素，并提出ST-DBSCAN時空聚類算法，但其人為參數(shù)設(shè)置過多，導(dǎo)致聚類結(jié)果隨機性增大；JOSHI[13]等基于密度聚類思想，通過拓撲鄰接關(guān)系定義時空鄰域，進而定義時空核點進行擴展聚類，該方法主要針對時空數(shù)據(jù)進行聚類；PEI[14]等在密度分解思想上提出了WKN時空聚類算法，該算法減少了參數(shù)的設(shè)置量，但是該算法僅適用于三維時空數(shù)據(jù)，無法考慮非時空的屬性因素。傳統(tǒng)的時空聚類算法主要針對固定屬性的時空數(shù)據(jù)進行聚類分析，并且現(xiàn)有算法中，閾值設(shè)定的主觀因素較多，客觀性不足，存在較大隨機性，容易導(dǎo)致聚類結(jié)果不理想。

ST-DBSCAN算法只能處理固定屬性的時空數(shù)據(jù)，本文首先對特征屬性進行分類，再通過引入Gower相似系數(shù)、Dice相似系數(shù)與歐幾里德距離構(gòu)建多屬性相似計算模型用于多屬性的時空數(shù)據(jù)聚類分析；基于ST-DBSCAN采用人為設(shè)定閾值的方法存在較大隨機性，本文提出一種繪制時空對象距離頻數(shù)柱狀圖的方法來設(shè)定閾值；最后，結(jié)合北京市計算機行業(yè)職位招聘數(shù)據(jù)進行仿真實驗。

1 ST-DBSCAN算法概述

ST-DBSCAN是基于密度的時空聚類算法，時空密度聚類是從空間密度聚類到時空維度的擴展，它將對象密度當(dāng)作對象間相似計算的標準，把時空簇從一系列不同密度區(qū)域中提取出來。由于在空間維度的基礎(chǔ)上多考慮了時間因素，所以該算法需要設(shè)定的聚類參數(shù)為3個：時間距離閾值temporal_threshold，空間距離閾值spatial_threshold和時空對象量閾值MinPts，前2個參數(shù)用于確定時空鄰近域，后一個用來確定時空鄰近域內(nèi)的對象數(shù)量。算法基本步驟如下。

步驟1建立一個三維的時空數(shù)據(jù)庫，庫中時空對象的經(jīng)度為x，緯度為y，時間為t，一條時空對象數(shù)據(jù)為一個對象點Pi={idPi,xi,yi,ti}，i為時空對象序號，所有對象點的集合為DP；

步驟2從DP中依次選取一個對象點Pi，判斷其是否已屬于現(xiàn)有簇中，是則重新選取下一個對象點，否則進行步驟3；

步驟3判斷對象點Pi是否為時空核心對象，是則進行步驟4，否則回到步驟2中重新選取下一個對象點；

步驟4搜尋時空核心對象點Pi的所有時空相鄰點Qi，若Qi不屬于任何已有的簇，則將Qi放入新建的簇中，若Qi屬于已有的簇，則不進行操作；

步驟5判斷簇A中新加入的對象是否為時空核心對象，若非時空核心對象，則將其標為邊緣時空對象不進行進一步操作，是則對該時空核心對象重復(fù)步驟4的操作；

步驟6重復(fù)步驟2—步驟5的工作，直到DP中所有對象都屬于某個簇，或為時空孤立點。

ST-DBSCAN算法只限于處理固定屬性的時空數(shù)據(jù)分析，且在閾值設(shè)定上存在較大隨機性容易導(dǎo)致其將噪聲歸到時空簇中或忽略部分低密度的簇。

2 改進的多屬性時空聚類算法

2.1 特征屬性分類

本文將時空事件數(shù)據(jù)對象定義為P={idP,x,y,t,Att}，其中，idP表示P的唯一對象標識符；x，y分別表示P對應(yīng)的地理經(jīng)、緯度坐標值；t表示P對應(yīng)的具體時間值；Att表示P的屬性特征集合。屬性特征定義為attribute，用att表示，att∈Att，Att={att1,att2,…，attp}為P個不同屬性特征的集合，attq={attq1,attq2,…，attqw}為第q個屬性項里的w個不同屬性值的集合。連續(xù)變量型的屬性特征用attu表示，attu∈Attu，Attu={attu1,attu2,…，attuj}為j個不同連續(xù)變量屬性特征的集合。有序分類變量的屬性特征用attof表示，attof∈Attof，Attof={attof1,attof2,…，attofg}為g個不同有序分類變量屬性特征的集合。無序分類變量的屬性特征用attnf表示，attnf∈Attnf，Attnf={attnf1,attnf2,…，attnfh}為h個不同無序分類變量屬性特征的集合。

2.2 多屬性相似計算模型

為了計算具有多種不同類型屬性特征的時空對象之間是否相似，本節(jié)提出了一種多屬性相似計算模型。其模型計算式為

(1)

(1)式中：E表示具有連續(xù)變量屬性特征的2個時空對象是否相似的結(jié)果；DG表示具有分類變量屬性特征的2個時空對象是否相似的結(jié)果。其中，E與DG值的判斷條件為

(2)

(3)

(2)—(3)式中：ΔE為具有多個連續(xù)變量屬性特征的2個時空對象的相似距離，該距離越小，2個時空對象相似度越大；ΔE_threshold為連續(xù)變量相似度閾值，當(dāng)ΔE≤ΔE_threshold(即E=1)時，2個時空對象相似；ΔDG為具有多個分類變量屬性特征的2個時空對象的相似度大小，ΔDG值越大，2個時空對象相似度越大；ΔDG_threshold為分類變量相似度閾值，當(dāng)ΔDG≥ΔDG_threshold(即DG=1)時，2個時空對象相似，且

(4)

(4)式中：ΔD與ΔG分別是具有多個無序和有序分類變量屬性特征的2個時空對象之間的相似度值。多維的連續(xù)變量屬性值之間的相似度距離通常采用歐氏距離計算方法，那么，2個時空對象中n維連續(xù)變量Attux={attux1,attux2,…，attuxn}間的相似度距離(即歐式距離)為

i∈[1,n]

(5)

將Dice相似系數(shù)應(yīng)用于計算2個時空對象的無序分類變量屬性值之間的相似度距離，表示為

(6)

2個時空對象中n維有序分類變量Attofx={attofx1,attofx2,…，attofxn}間的Gower系數(shù)為

i∈[1,n]

(7)

0≤δ(attofxi,attofyi)≤1

(8)

(7)—(8)式中，Ri為時空對象中第i個有序分類變量屬性特征中值的極差。

2.3 閾值設(shè)定方法

本文提出通過繪制時空對象距離頻數(shù)柱狀圖來設(shè)定時間與空間閾值的方法，需要計算空間距離ΔS與時間距離ΔT。若有2個時空對象點P1={idP1,x1,y1,t1}和P2={idP2,x2,y2,t2}，它們的時間距離為

ΔT=|t1-t2|

(9)

空間距離為

(10)

因本文后續(xù)研究中所采用的時空對象的位置均為實際地理位置即經(jīng)緯度，故將(10)式演變?yōu)?/p>

ΔS=|Distance((x1,y1)-(x2,y2))|=

R×arcos[cos(y1)×cos(y2)×cos(x1-x2)+

sin(y1)×sin(y2)]

(11)

(11)式中，R為地球赤道半徑。

該方法具體步驟如下。

步驟1計算時空對象事務(wù)集中兩兩時空對象在時間維度(或空間維度)下的時間(或空間)距離數(shù)值；

步驟2計算步驟1所得的各個距離大小值出現(xiàn)的頻數(shù)；

步驟3將步驟2所得的頻數(shù)數(shù)值對應(yīng)縱軸，距離大小值對應(yīng)橫軸，繪制出時空對象距離頻數(shù)柱狀圖，找出柱狀圖中最大距離頻數(shù)數(shù)值對應(yīng)的點，該點的時間(或空間)距離數(shù)值作為此維度下的時間閾值temporal_threshold(或空間閾值spatial_threshold)；

步驟4計算時空對象量閾值為

MinPts=ln(|DP|)

(12)

(12)式中，|DP|為時空對象點的總數(shù)。

2.4 算法流程

改進的多屬性時空聚類算法的實現(xiàn)過程大致如圖1。該算法共包括5個參數(shù)閾值：時間閾值temporal_threshold、空間閾值spatial_threshold、時空對象量閾值MinPts、連續(xù)變量相似度閾值ΔE_threshold、分類變量相似度閾值ΔDG_threshold。

圖1 多屬性時空聚類算法實現(xiàn)步驟流程圖Fig.1 Multi-attribute spatial-temporal clustering algorithm implementation steps

算法流程如下。

步驟1建立一個多維度的時空信息數(shù)據(jù)庫DP；

步驟2設(shè)置時空對象量閾值MinPts，根據(jù)多維時空數(shù)據(jù)集畫出時空對象距離頻數(shù)柱狀圖，確定空間閾值spatial_threshold、時間閾值temporal_threshold；

步驟3從DP依次選取一個對象點Pi，判斷其是否已屬于現(xiàn)有簇中，是則重新選取下一個對象點，否則進行步驟4；

步驟4判斷對象點Pi是否為時空核心對象，是則進行步驟5，否則回到步驟3中重新選取下一個對象點；

步驟5搜尋時空核心對象點Pi的所有時空相鄰點Qi，若Qi不屬于任何已有的簇，則進行步驟6，否則重新選取下一個Qi繼續(xù)本步驟；

步驟6通過混合屬性相似計算模型計算出Pi與Qi的混合屬性特征是否相似，相似則將Qi放入新建的簇中，否則重新選取下一個Qi繼續(xù)步驟5；

步驟7判斷簇中的各對象是否為時空核心對象，是則對該時空核心對象重復(fù)步驟5的操作，否則將不再進行下一步操作；

步驟8重復(fù)上述步驟3—步驟7的工作，直到DP中所有對象都屬于某個簇，或為時空孤立點；

步驟9將上述得到的簇標簽賦值給數(shù)據(jù)庫新建的字段“簇標簽”中。

3 實驗結(jié)果及分析

3.1 閾值設(shè)定實驗分析

本文隨機生成了一組數(shù)據(jù)集來驗證該方法的準確性。該數(shù)據(jù)集共有1 100個時空對象點，每個時空對象點有x，y，t3個值，x，y值分別對應(yīng)地理經(jīng)緯度坐標(即X，Y軸)，t對應(yīng)時間月份(即Z軸)。如圖2，黑點的集合即為實驗數(shù)據(jù)集，圖2中有2個黑色點密集區(qū)域，它們?yōu)槊芏认嗤?、形狀不?guī)則的待驗證時空簇，共計900個點；剩余的210個噪聲點散布在密集區(qū)域周圍，即離散區(qū)域。

圖2 實驗數(shù)據(jù)集散點圖Fig.2 Scatter image of the experimental data set

為了判斷聚類結(jié)果的好壞，本文將密集區(qū)域中被標記為時空簇的點數(shù)量占密集區(qū)域中所有對象點總數(shù)的百分比稱為正標率，將離散區(qū)域中被標記為時空簇的點數(shù)量占離散區(qū)域中所有對象點總數(shù)的百分比稱為誤標率。正標率越大，且誤標率越小，則說明該閾值設(shè)定得越合理。

繪制出該時空數(shù)據(jù)集的時空對象距離頻數(shù)柱狀圖部分截圖，如圖3。

圖3中時間和空間距離頻數(shù)最大數(shù)值分別對應(yīng)(4，15 830)和(5，3 349)點，即時間閾值temporal_threshold=4，空間閾值spatial_threshold=5，時空對象量閾值MinPts=ln(1100)≈7。通過ST-DBSCAN算法在4組不同閾值設(shè)定條件下對該數(shù)據(jù)集進行聚類分析，得出的聚類結(jié)果如圖4。

圖3 時空對象距離頻數(shù)柱狀圖(部分截圖)Fig.3 Spatial-temporal data object distance frequency columnar image

圖4 實驗數(shù)據(jù)集在4種閾值條件下的聚類結(jié)果圖Fig.4 Clustering results of experimental data sets under four threshold conditions

圖4的4幅聚類結(jié)果中，黑色點集群代表噪聲(即時空獨立點)，不同彩色點集群代表不同時空簇。圖4a中3個閾值均是本文所提方法來設(shè)定的，并將該方法所得閾值條件下的聚類結(jié)果圖作為參照圖與另外3個閾值條件下的聚類結(jié)果圖進行對比。圖4b—圖4d是在圖4a所設(shè)定的閾值基礎(chǔ)上分別對時空對象量閾值MinPts、空間閾值spatial_threshold、時間閾值temporal_threshold做了修改。從圖4a可以看出，該時空數(shù)據(jù)集中的待驗證時空點有98.5%分別被藍色和紅色標記出來，噪聲點被標記為時空簇的概率為1.38%，可見該閾值下的聚類結(jié)果較好；圖4b和圖4c將原本同屬于某一密度的時空簇被分為了多個不同密度的時空簇，導(dǎo)致正標率較低，聚類結(jié)果有較大誤差；圖4d將2個時空簇周圍的多個噪聲點也納入了簇中，使得誤標率較大，聚類結(jié)果精確度降低。通過該實驗分析，可以確定本文所提出的設(shè)定閾值的方法具有較強的合理性與準確性。

3.2 多屬性時空數(shù)據(jù)聚類分析

本文使用某主流招聘網(wǎng)站上發(fā)布的3 114條北京市計算機行業(yè)職位招聘數(shù)據(jù)構(gòu)建了實驗樣本數(shù)據(jù)庫。其中，時間、經(jīng)緯度的數(shù)據(jù)格式符合要求，不用進一步處理；“五險一金”屬于無序分類變量類型，其值的標識符可定義為0，1形式，0代表沒有，1代表有；“學(xué)歷”為有序分類變量類型，其值的轉(zhuǎn)換定義如表1；為了能計算連續(xù)變量對聚類結(jié)果的影響，本文將職位數(shù)據(jù)中的“薪資”按照其數(shù)值所在區(qū)間生成隨機整數(shù)，從而將薪資數(shù)據(jù)轉(zhuǎn)換為類似連續(xù)變量的類型。

表1 學(xué)歷值的轉(zhuǎn)換定義對應(yīng)表Tab.1 Educational conversion value correspondence table

職位數(shù)據(jù)集在時空維度及“五險一金”“學(xué)歷”“薪資”屬性特征條件下進行多屬性時空聚類分析，聚類后的結(jié)果如圖5，黑色點表示時空獨立點，即噪聲；不同的彩色點集表示不同的時空簇；因生成的簇數(shù)量較多，選取前10個體積較大的時空簇來進行結(jié)果分析；在三維坐標中，X軸為緯度，Y軸為經(jīng)度，Z軸為時間(12個月)。

圖5a為10個彩色時空簇和黑色時空獨立點分布情況經(jīng)緯度斜視圖，為方便觀察，圖5b中只顯示時空簇的分布情況。為進一步分析含有“五險一金”“學(xué)歷”“薪資”的職位數(shù)據(jù)在聚類后的結(jié)果，此處將各個時空簇中“五險一金”“學(xué)歷”“薪資”的情況用表2，表3展示出來。

表2 各時空簇中“五險一金”與“薪資”的數(shù)據(jù)統(tǒng)計Tab.2 Statistical results of different“five social insurance and one housing fund” and “salary” attributesin each spatiotemporal cluster

表3 各時空簇中“學(xué)歷”的數(shù)據(jù)統(tǒng)計Tab.3 Statistical results of “educational background” attributes in each spatiotemporal cluster

圖5 職位數(shù)據(jù)集在多屬性條件下的時空聚類結(jié)果圖Fig.5 Spatial-temporal clustering results of data sets under multi-attribute conditions

從圖6可以看出，10個時空簇中有“五險一金”的比例都比較高，僅簇1、簇20相對較低，結(jié)合這2個簇在圖5中的分布情況，可以分析出：在1月到2月期間的海淀區(qū)、昌平區(qū)一帶以及八月的西城區(qū)、宣武區(qū)、崇文區(qū)一帶，計算機行業(yè)職位招聘條件中有“五險一金”的幾率相對較低一些；學(xué)歷要求較高的是簇12、簇19、簇21和簇29，幾乎都要求大專以上學(xué)歷，學(xué)歷要求較低的是簇3和簇20；薪資待遇方面，簇12、簇21和簇29的薪資待遇較好，大部分都在8 000～12 000元/月。綜合上述分析結(jié)果得出：計算機行業(yè)職位招聘要求大專以上學(xué)歷，有五險一金；待遇較好的職位集中于7月的西城區(qū)、崇文區(qū)和11月的西城區(qū)，以及11月、12月的朝陽區(qū)、東城區(qū)。

4 結(jié)束語

時空數(shù)據(jù)挖掘作為數(shù)據(jù)挖掘的拓展，不僅考慮到了空間因素，還考慮到了時間因素，主要是側(cè)重于對空間對象進行動態(tài)性研究，以發(fā)現(xiàn)隱藏在動態(tài)空間對象下的規(guī)律模式和知識，目前已經(jīng)受到各個行業(yè)的極大關(guān)注。

時空聚類分析是時空數(shù)據(jù)挖掘方向較為前沿，且技術(shù)不夠完善的分支領(lǐng)域，本文通過研究分析當(dāng)前時空聚類算法的國內(nèi)外研究現(xiàn)狀與其存在的問題，從以下2點進行深入研究：①根據(jù)已有的時空聚類算法ST-DBSCAN在人為設(shè)定閾值上存在較大隨機性，從而導(dǎo)致聚類結(jié)果不理想的問題，本文提出了一種通過繪制時空對象距離頻數(shù)柱狀圖的方法來合理設(shè)定閾值，通過仿真實驗證明，新的閾值設(shè)定方法能夠更為準確地識別出部分低密度簇，提高了聚類的準確性；②針對ST-DBSCAN算法僅限于對固定屬性的時空數(shù)據(jù)進行聚類分析提出了一種新的改進型多屬性時空聚類算法，實驗結(jié)果表明，在加入了無序變量、有序變量和連續(xù)變量的條件下，該算法能夠針對多屬性的時空數(shù)據(jù)生成理想的聚類結(jié)果，在現(xiàn)實生活中具有很好的實用性。