王星捷 衛(wèi)守林

1(核工業(yè)西南物理研究院 四川 成都 610041)2(成都理工大學(xué)工程技術(shù)學(xué)院 四川 樂(lè)山 614007)3(昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院 云南 昆明 650093)

0 引 言

聚類(lèi)分析[1]就是將參與分析的數(shù)據(jù)分成多個(gè)類(lèi)或者簇的過(guò)程，目的是讓在聚類(lèi)到同一個(gè)簇中的數(shù)據(jù)其各個(gè)對(duì)象之間的相似程度盡可能高，不同簇的各個(gè)數(shù)據(jù)的相似程度盡可能低。聚類(lèi)分析成為了數(shù)據(jù)挖掘和智能分析的重要組成部分，已經(jīng)廣泛應(yīng)用到了各個(gè)領(lǐng)域。

目前已有多種聚類(lèi)算法的研究。k-means算法[2]并不適宜于非凸面形狀的簇，并且對(duì)“噪聲”和孤立點(diǎn)數(shù)據(jù)比較敏感，文獻(xiàn)[3-6]提出一些算法來(lái)改進(jìn)K-means算法的問(wèn)題。CURE算法[7]在非球形幾何形狀的簇上具有良好的表現(xiàn)，而且相對(duì)于k-平均算法能夠很好地控制“噪聲”和孤立點(diǎn)，但是該算法成功與否的關(guān)鍵在于必須在算法中設(shè)定“固定數(shù)目的具有良好代表性的點(diǎn)”，并將其乘以一個(gè)“比較適當(dāng)?shù)氖湛s因子”。所謂的“固定數(shù)目”這是一個(gè)未知的、沒(méi)有實(shí)際以及理論參考的數(shù)值，在實(shí)際的算法實(shí)現(xiàn)過(guò)程中很難把握這個(gè)參數(shù)的具體確定，只能通過(guò)不斷嘗試與摸索來(lái)確定，使得該算法的“可解釋性”大大降低，文獻(xiàn)[8-9]提出一些算法來(lái)改進(jìn)CURE的問(wèn)題。DBSCAN算法[10]相對(duì)于CURE算法在保留其優(yōu)勢(shì)的情況，并將算法的參數(shù)減少為兩個(gè)，但DBSCAN算法需要人為確定Eps和min Pts兩個(gè)參數(shù)，導(dǎo)致聚類(lèi)結(jié)果的準(zhǔn)確度直接取決于用戶對(duì)參數(shù)的選擇，采用的區(qū)域查詢方式過(guò)程復(fù)雜且易丟失對(duì)象等問(wèn)題，文獻(xiàn)[11-13]提出了參數(shù)的改進(jìn)方法。文獻(xiàn)[14]提出了LDBSC算法是一種基于角度的空間實(shí)體局部分布度量方法，采用中值角度來(lái)反映每個(gè)實(shí)體的角度分布(或變化范圍)的集中趨勢(shì)，并用于度量空間實(shí)體的局部分布。該方法具有很好的抗噪能力，聚類(lèi)結(jié)果比DBSCAN聚類(lèi)結(jié)果更為合理，但是在全局范圍進(jìn)行搜索，出現(xiàn)的異常數(shù)較多，適用性差。本文以LDBSC算法為基礎(chǔ)，對(duì)算法的中值角度和閾值的計(jì)算方法進(jìn)行了改進(jìn)和優(yōu)化，提高了抗噪性，極大地降低了異常數(shù)，實(shí)現(xiàn)了適合全局搜索的角度聚類(lèi)算。

1 角度聚類(lèi)原理

文獻(xiàn)[14]提出了一種基于角度的空間實(shí)體局部分布度量方法。如圖1所示，在空間點(diǎn)集Sn中，若點(diǎn)O遠(yuǎn)離空間點(diǎn)集中其他點(diǎn)，則會(huì)導(dǎo)致O點(diǎn)與其他的任意兩點(diǎn)所成夾角的變化范圍和角度值都會(huì)相對(duì)偏小，因此可以通過(guò)這個(gè)特征來(lái)反映空間實(shí)體的局部分布情況。根據(jù)這種特性，局部分布聚類(lèi)中使用中值角度來(lái)反映所有實(shí)體的角度分布的變化過(guò)程，并用來(lái)度量空間實(shí)體的局部分布情況。然后通過(guò)設(shè)定閾值的方式將空間實(shí)體分為兩個(gè)部分，將其稱(chēng)為聚類(lèi)區(qū)和非聚類(lèi)區(qū)。局部分布聚類(lèi)算法中采用多次循環(huán)迭代搜索的方式，使得聚集部分聚成一個(gè)簇。由于這種聚類(lèi)過(guò)程考慮了空間實(shí)體的局部分布情況，因此文獻(xiàn)[14]中將這種算法稱(chēng)為基于局部分布的空間聚類(lèi)算法(LDBSC)。

圖1 空間實(shí)體的角度分布度量

文獻(xiàn)[14]中局部分布聚類(lèi)算法中所用的在給定搜索半徑內(nèi)的局部搜索方式難以體現(xiàn)數(shù)據(jù)的全局分布特性。該算法通過(guò)控制搜索半徑和設(shè)定最小實(shí)體數(shù)目的方式進(jìn)行聚類(lèi)使得算法必須建立在相當(dāng)豐富的先驗(yàn)知識(shí)上。只有通過(guò)大量的實(shí)際運(yùn)算并分析最終的運(yùn)算成果來(lái)確定哪種參數(shù)設(shè)定方式是相對(duì)比較合理的。由于算法是在設(shè)定的搜索內(nèi)進(jìn)行要素搜索，因此實(shí)際上難以體現(xiàn)每個(gè)判定點(diǎn)數(shù)據(jù)在全局的分布特征。最后算法采用的中值判定方式也會(huì)受到最大、最小值的影響，難以對(duì)全局?jǐn)?shù)據(jù)進(jìn)行合理地聚類(lèi)。

本文在該算法的基礎(chǔ)進(jìn)行了改進(jìn)，研究基于角度的全局聚類(lèi)算法。

2 算法設(shè)計(jì)

2.1 角度全局聚類(lèi)算法

角度判定方式能夠很好地判斷要素是否是遠(yuǎn)離點(diǎn)群，這是判定空間數(shù)據(jù)是否被聚類(lèi)的關(guān)鍵。設(shè)空間中離散點(diǎn)群共N個(gè)點(diǎn)，若點(diǎn)O遠(yuǎn)離點(diǎn)群中心，會(huì)導(dǎo)致O點(diǎn)與任意的兩點(diǎn)的夾角γ的平均值變??；若點(diǎn)O靠近點(diǎn)群中心同樣會(huì)導(dǎo)致點(diǎn)O與任意兩點(diǎn)的夾角γ的平均值變大。求得點(diǎn)群中每一個(gè)點(diǎn)O與除自身以外的所有點(diǎn)任意連點(diǎn)的夾角γ的平均值K。并計(jì)算所有點(diǎn)的角度平均值的平均值M。若該點(diǎn)處于聚類(lèi)區(qū)外，該點(diǎn)的角度平均值K將小于聚類(lèi)區(qū)內(nèi)的點(diǎn)的角度平均值M。將所有點(diǎn)的角度平均值的平均值M作為聚類(lèi)區(qū)邊界判定閾值，即K值大于M的所有點(diǎn)所在區(qū)域?yàn)榫垲?lèi)區(qū)，其余點(diǎn)所在區(qū)域?yàn)榉蔷垲?lèi)區(qū)。

如圖1所示實(shí)際上夾角γ是無(wú)法直接確定的，但是可以通過(guò)O點(diǎn)與C、D兩點(diǎn)所成的三角形的邊長(zhǎng)用三角函數(shù)求得。

空間距離計(jì)算公式如下：

(1)

SOC表示O、C兩點(diǎn)的距離，XOC表示O、C兩點(diǎn)的X坐標(biāo)差，YOC表示O、C兩點(diǎn)的Y坐標(biāo)差。O、D與C、D間的距離同理可計(jì)算。

夾角γ的三角函數(shù)計(jì)算公式如下：

(2)

γ表示O點(diǎn)與C、D兩點(diǎn)所成夾角，SOC表示點(diǎn)O到C的距離，SOD表示點(diǎn)O到D點(diǎn)距離，SCD表示點(diǎn)C到D點(diǎn)距離。cosγ表示O點(diǎn)與C、D兩點(diǎn)所成夾角的余弦值。

反三角函數(shù)求γ角度如下：

(3)

角度均值K的求解如下：

(4)

式中：i、j、k都為整數(shù)，Ki代表點(diǎn)群N中點(diǎn)與其他所有點(diǎn)所成夾角的平均值，N代表點(diǎn)群中點(diǎn)的數(shù)量，γ代表i點(diǎn)與除i以外任意兩點(diǎn)所成夾角序號(hào)分別為j、k。本文所研究的角度聚類(lèi)算法是針對(duì)每個(gè)要素進(jìn)行全局搜索，即每個(gè)要素與除自身以外的所有點(diǎn)的角度，并將該點(diǎn)與其余所有點(diǎn)所成角度的均值作為判定該點(diǎn)是否被聚類(lèi)的判定值。所以j點(diǎn)存在除i點(diǎn)之外的所有點(diǎn)共N-1個(gè)點(diǎn)，k點(diǎn)存在除j點(diǎn)、i點(diǎn)以外的所有點(diǎn)共N-2個(gè)點(diǎn)。因此共須遍歷(N-1)×(N-2)次，所以需要將最終的點(diǎn)i與所有點(diǎn)的角度和除以(N-1)×(N-2)得到i點(diǎn)與所有點(diǎn)的角度均值。

判定參考閾值計(jì)算如下：

(5)

式中：Ki代表點(diǎn)i的角度平均值，M代表點(diǎn)群所有點(diǎn)的角度平均值的平均值，N代表點(diǎn)群中點(diǎn)的數(shù)量。

合并式(4)與式(5)得到判定參考閾值公式如下：

(6)

2.2 抗噪性驗(yàn)證

判定要素是否屬于離群點(diǎn)的條件是比較判定要素的角度均值Ki與參考閾值M的大小關(guān)系，離群點(diǎn)由于遠(yuǎn)離點(diǎn)群導(dǎo)致Ki值較小，因此能夠通過(guò)這種方式可靠地找到數(shù)據(jù)中的離群點(diǎn)群O(p)和聚類(lèi)點(diǎn)群A(p)，如下式所示：

A(p)={Ki≥M|Ki∈Sn}

(7)

O(p)={Ki

(8)

(9)

結(jié)合式(9)與式(4)，得到：

(10)

從式(10)中可以看出實(shí)際導(dǎo)致角度均值的向上浮動(dòng)值為：X/((N-1)×(N-2))，記為Ky。

(11)

將式(11)簡(jiǎn)化為下式：

(12)

從式(12)可知，實(shí)際產(chǎn)生的浮動(dòng)值為：X/2，記為Py。

通過(guò)求解不等式的方式Ky

X/((N-1)×(N-2))

(13)

解不等式，得下式：

N<-3或N>3

(14)

對(duì)式(14)的結(jié)果進(jìn)行分析發(fā)現(xiàn)，在實(shí)際的引用中由于采用的是角度法進(jìn)行判定，因此判定的點(diǎn)群數(shù)目一定是大于3的，因此在任何情況下Ky都是小于Py的，因此可以得出采用角度均值判定的方式在單個(gè)要素的判定上具有更高的抗噪性。

設(shè)：在式(5)的判定閾值計(jì)算中獲得的最大角度均值為Kmax，最小角度均值為Kmin；若將Kmax上浮Z，則判定參考閾值隨之產(chǎn)生的數(shù)值將變?yōu)橄率剑?/p>

(15)

結(jié)合式(5)得下式：

M′=M+Z/N

(16)

判定參考閾值實(shí)際造成的上浮波動(dòng)為：Z/N，記為My。

根據(jù)文獻(xiàn)[14]中的局部分布聚類(lèi)算法所得到的判定閾值為：ε=τ(p)/3。即，將要素幅角中位數(shù)的極差的1/3作為判定閾值。結(jié)合文獻(xiàn)[14]中τ(p)，以及上文對(duì)最大角度最小角度的定義的到ε的計(jì)算公式如下：

ε=(max(Ψ(p))-min(Ψ(p)))/3

(17)

若max(Ψ(p))在某種異常情況下向上浮動(dòng)Z，導(dǎo)致ε的浮動(dòng)情況如下：

ε′=(max(Ψ(p))-min(Ψ(p))+Z)/3

(18)

結(jié)合式(18)和式(17)，得出下式：

ε′=ε+Z/3

(19)

由式(19)可知，產(chǎn)生的實(shí)際浮動(dòng)為Z/3，記為εy。

若要使得My小于εy，則建立不等式為：

Z/N

(20)

解不等式，得到N的取值范圍為：

N>3

(21)

同理，在任何情況下，采用該方式產(chǎn)生的判定參考閾值比局部分布聚類(lèi)算法中的方式更具有抗噪性。

通過(guò)上述論證，本文所使用的角度聚類(lèi)算法無(wú)論是在單個(gè)要素的聚類(lèi)判定還是整體判定閾值的獲取方面都具有良好的抗噪性。

2.3 算法描述

1) 獲取數(shù)據(jù)：通過(guò)讀取空間數(shù)據(jù)庫(kù)獲取所有的研究點(diǎn)位的數(shù)據(jù)，并將其保存在集合Sn中。

2) 計(jì)算要素角度均值Ki，從集合Sn中獲取點(diǎn)位數(shù)據(jù)，通過(guò)式(4)計(jì)算每個(gè)要素的角度均值Ki，并將所有要素的角度均值保存在集合Kn中。

3) 計(jì)算參考判定閾值，通過(guò)式(5)計(jì)算角度均值集合Kn的均值，將其作為參考判定閾值M。

4) 設(shè)定實(shí)際判定閾值，以參考判定閾值為標(biāo)準(zhǔn)設(shè)定實(shí)際的聚類(lèi)判定閾值PM。

5) 聚類(lèi)判定，遍歷角度均值集合Kn，將角度均值大于判定閾值對(duì)應(yīng)的商鋪點(diǎn)保存在聚類(lèi)集合An中，將角度均值小于判定閾值的商鋪點(diǎn)保存在離散集合On中。

6) 成果顯示，對(duì)聚類(lèi)點(diǎn)群進(jìn)行顯示，并對(duì)點(diǎn)群進(jìn)行邊界繪制。通過(guò)上述論證將以聚類(lèi)點(diǎn)群為基礎(chǔ)繪制聚類(lèi)區(qū)域。

3 實(shí)驗(yàn)分析

本文以樂(lè)山市區(qū)156平方公里為研究對(duì)象，對(duì)城區(qū)的高價(jià)值商業(yè)圈進(jìn)行聚類(lèi)分析測(cè)試。研究數(shù)據(jù)要素包括商鋪、醫(yī)院、行政單位、加油站、主干道、河流、學(xué)校、購(gòu)物中心、車(chē)站、居民樓、城市綠地、島嶼共12類(lèi)不同的要素，數(shù)據(jù)總量達(dá)到10余萬(wàn)條。

3.1 成果評(píng)價(jià)體系

1) 商業(yè)圈的范圍與規(guī)模[15]。城市商業(yè)圈是城市經(jīng)濟(jì)的核心地帶相對(duì)于整個(gè)城市區(qū)域而言是較小的，若產(chǎn)生的商業(yè)圈過(guò)于龐大則可能產(chǎn)生的商業(yè)圈存在誤差。

2) 高價(jià)值商業(yè)圈的分布[16]。城市商業(yè)圈是城市中商業(yè)價(jià)值最高的區(qū)域大多存在于城市的核心位置，且商業(yè)圈的形態(tài)與城市的整體分布形態(tài)相似。

3) 實(shí)際城市商業(yè)圈匹配程度。衡量理論結(jié)果是否符合實(shí)際時(shí)，最好的方式便是直接與現(xiàn)實(shí)情況進(jìn)行對(duì)比，因此直接將產(chǎn)生的理論商業(yè)圈與實(shí)際的城市進(jìn)行對(duì)比是最為可靠的判定方式。若商圈內(nèi)的區(qū)域在實(shí)際的城市中都是高商業(yè)價(jià)值的，則產(chǎn)生的分析結(jié)果是有效的；反之有誤。

4) 異常區(qū)域量。理論商業(yè)圈與實(shí)際商業(yè)圈必定會(huì)存在差異，而差異的大小也將是判定該成果是否有效的方式。

3.2 局部分布的聚類(lèi)算法

根據(jù)文獻(xiàn)[14]的局部分布聚類(lèi)算法的理論在獲取最優(yōu)聚類(lèi)成果之前需要對(duì)搜索半徑和最小聚類(lèi)數(shù)進(jìn)行浮動(dòng)設(shè)置，以找到研究數(shù)據(jù)最適宜的搜索半徑和最小聚類(lèi)數(shù)。以樂(lè)山市區(qū)的商鋪點(diǎn)空間數(shù)據(jù)為基礎(chǔ)對(duì)局部分布聚類(lèi)算法的理論進(jìn)行數(shù)據(jù)分析。數(shù)據(jù)統(tǒng)計(jì)如表1所示。

表1 不同聚類(lèi)參數(shù)體現(xiàn)的數(shù)據(jù)情況

表1中必然異常數(shù)表示在該參數(shù)設(shè)定下產(chǎn)生的聚類(lèi)點(diǎn)群中必然存在異?；蝈e(cuò)誤的點(diǎn)數(shù)；潛在異常數(shù)表示在該參數(shù)設(shè)定下產(chǎn)生的聚類(lèi)點(diǎn)群中可能存在異?；蝈e(cuò)誤的點(diǎn)數(shù)；異常點(diǎn)總數(shù)表示潛在異常數(shù)與必然異常數(shù)的總和；商鋪總數(shù)表示在該參數(shù)設(shè)定下聚類(lèi)點(diǎn)群的總數(shù)。

從表1可以看出，當(dāng)搜索半徑相同時(shí)隨著最小聚類(lèi)數(shù)以5為起始值5為浮動(dòng)值時(shí)，隨著最小聚類(lèi)數(shù)的不斷增大，必然異常數(shù)都呈現(xiàn)出先下降再上升的趨勢(shì)。以搜索半徑為100米為例，當(dāng)最小聚類(lèi)數(shù)為20時(shí)必然異常值到達(dá)最小值14，該參數(shù)表示當(dāng)搜索半徑為100米，最小聚類(lèi)數(shù)為20時(shí)必然異常值達(dá)到最低，因此可以視為在最小聚類(lèi)數(shù)20是搜索半徑100米的最佳參數(shù)。同理，半徑為150米和200米時(shí)其最佳的最小聚類(lèi)數(shù)為30。通過(guò)對(duì)不同的數(shù)據(jù)進(jìn)行試驗(yàn)對(duì)比發(fā)現(xiàn)，聚類(lèi)成果對(duì)搜索半徑和最小聚類(lèi)數(shù)的設(shè)定都十分敏感，而且不同的數(shù)據(jù)都需要進(jìn)行這樣的大量數(shù)據(jù)試驗(yàn)才能找到最佳的參數(shù)設(shè)定。由于該算法是局部分布的聚類(lèi)算法，對(duì)于整個(gè)城區(qū)的全局進(jìn)行聚類(lèi)分析時(shí)，出現(xiàn)的異常較多，而且在最優(yōu)值之后，異常數(shù)據(jù)又不斷上升。由此可知，局部聚類(lèi)算法應(yīng)用在全局分析中，效果并不理想。

3.3 本文聚類(lèi)算法

根據(jù)上文的相關(guān)論證將本文算法中聚類(lèi)判定閾值以參考閾值M為標(biāo)準(zhǔn)進(jìn)行浮動(dòng)設(shè)置，并得到不同閾值下的相關(guān)數(shù)據(jù)統(tǒng)計(jì)，表2為不同閾值下數(shù)據(jù)統(tǒng)計(jì)。

表2 不同閾值下數(shù)據(jù)情況

由表2可知，隨著聚類(lèi)判定標(biāo)準(zhǔn)的不斷“嚴(yán)苛”即閾值不斷增大，產(chǎn)生的聚類(lèi)結(jié)果中的必然異常數(shù)和潛在異常數(shù)都在急劇減小，當(dāng)閾值超過(guò)1.3倍M時(shí)二者都為0。產(chǎn)生這種與局部分布聚類(lèi)不同的變化趨勢(shì)的原因在于角度聚類(lèi)算法采用的是全局搜索的方式獲取判定閾值，每個(gè)要素的判定閾值都是建立在所有要素的基礎(chǔ)上的，即要素越靠近這個(gè)數(shù)據(jù)點(diǎn)群的中心其判定閾值就越大，越遠(yuǎn)離這個(gè)數(shù)據(jù)點(diǎn)群的中心的則越小。因此，隨著判定閾值的不斷增大，符合聚類(lèi)條件的點(diǎn)就越少，形成的商業(yè)圈也會(huì)不斷內(nèi)縮，而且這些點(diǎn)都是位于數(shù)據(jù)點(diǎn)群中心區(qū)域的。當(dāng)商業(yè)圈內(nèi)縮到一定程度的時(shí)候生成的商業(yè)圈就位于了實(shí)際城市中心的一個(gè)區(qū)域，而對(duì)這個(gè)區(qū)域進(jìn)行采樣則發(fā)現(xiàn)生成的商業(yè)圈所有區(qū)域都在實(shí)際的城市高價(jià)值商業(yè)區(qū)域內(nèi)，因此產(chǎn)生的必然異常數(shù)和潛在異常數(shù)都將趨于零。聚類(lèi)實(shí)現(xiàn)的效果如圖2和圖3所示。

圖2 閾值為0.8M的聚類(lèi)效果

圖3 閾值為1.3M的聚類(lèi)效果

當(dāng)閾值為0.8M時(shí)，從圖2中明顯存在著大量的異常點(diǎn)數(shù)據(jù)。當(dāng)閾值為1.3M時(shí)，從圖3中可以看出，異常點(diǎn)為0，從呈現(xiàn)的聚類(lèi)商業(yè)圈進(jìn)行分析發(fā)現(xiàn)，該商業(yè)圈位于城市中心地帶，商業(yè)圈的分布形態(tài)也符合城市整體的分布形態(tài)。該商業(yè)圈中商鋪商業(yè)價(jià)值普遍高于商業(yè)圈外的商鋪。通過(guò)對(duì)聚類(lèi)的商業(yè)圈所在區(qū)域進(jìn)行實(shí)際調(diào)查發(fā)現(xiàn)，該區(qū)域的確涵蓋了城市的高價(jià)值商業(yè)圈，從而證明了本文基于角度的全局聚類(lèi)算法的正確性。

4 結(jié) 語(yǔ)

本文提出了基于角度的全局聚類(lèi)算法，該算法在文獻(xiàn)[14]局部分布聚類(lèi)算法的基礎(chǔ)上進(jìn)行了研究，考慮了搜索半徑和設(shè)定最小實(shí)體數(shù)目的局限性，根據(jù)全局的特點(diǎn)對(duì)角度閾值改進(jìn)，并驗(yàn)算了改進(jìn)后全局聚類(lèi)算法的抗噪性?？朔宋墨I(xiàn)[14]聚類(lèi)算法中搜索半徑和設(shè)定最小實(shí)體數(shù)目的影響。在本文的算法中，通過(guò)對(duì)角度閾值的設(shè)定可以較好地實(shí)現(xiàn)全局的聚類(lèi)分析，簡(jiǎn)化了聚類(lèi)算法的復(fù)雜度。通過(guò)實(shí)例進(jìn)行了證明，本文的算法在全局范圍內(nèi)進(jìn)行聚類(lèi)分析，聚類(lèi)的效果穩(wěn)定性好，異常數(shù)據(jù)小，聚類(lèi)簇間區(qū)別明顯，能夠準(zhǔn)確甄別出核心區(qū)域。本算法能夠適應(yīng)空間分布不均勻的特點(diǎn)，并能得到任意形狀的聚類(lèi)。但是在執(zhí)行本文聚類(lèi)算法時(shí)，時(shí)間復(fù)雜度并沒(méi)有進(jìn)行改善，無(wú)法滿足海量數(shù)據(jù)的聚類(lèi)分析，因此，對(duì)算法角度閾值的進(jìn)一步研究或采用AHP層次分析替代復(fù)雜的角度閾值計(jì)算是下一步需要研究的工作。