基于改進(jìn)DBSCAN算法的高性能計(jì)算中心用戶分類的研究及應(yīng)用

徐海嘯, 麻 婧, 吳 旗

(吉林大學(xué) a. 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院； b. 高性能計(jì)算中心, 長春 130012)

0 引 言

數(shù)據(jù)挖掘是指從數(shù)據(jù)庫的大量數(shù)據(jù)中揭示出隱含的、 先前未知的并有潛在價(jià)值信息的非平凡過程。聚類分析則是數(shù)據(jù)挖掘中的一個(gè)研究方向。聚類的目標(biāo)是將數(shù)據(jù)分類到不同的類或簇, 使同一簇中對象有很大的相似性, 而不同簇間的對象有很大的相異性。聚類分析可應(yīng)用于各種用戶數(shù)據(jù)的分類中, 如民航客戶分類[1]以及電信客戶分類[2]。

DBSCAN(Density Based Spatial Clustering of Applications with Noise)算法[3]是基于密度的聚類分析算法, 對噪聲有抵抗性, 并且能發(fā)現(xiàn)任意形狀的類簇,但卻對初始參數(shù)E(鄰域半徑)和MPts(E鄰域最小點(diǎn)數(shù))非常敏感[4]。

針對這一缺點(diǎn), 近些年出現(xiàn)了一些改進(jìn)研究。文獻(xiàn)[5]提出了K-dist圖的思想, 主要解決了類之間包含和交叉關(guān)系。文獻(xiàn)[6]采用對象投影的方法, 考察對象的臨域平衡性, 使用平衡密度可達(dá)聚簇, 有效排除了邊界稀疏對象的噪聲。文獻(xiàn)[7]采用選取核心對象鄰域中的代表對象擴(kuò)展類, 相比文獻(xiàn)[5,6]算法, 提高了算法時(shí)間性能。其他聚類算法的改進(jìn)思路也可應(yīng)用到DBSCAN算法中, 如文獻(xiàn)[8]提出的加速k-means算法, 利用迭代調(diào)整簇閾值的方法將簇中心遷移, 這一思路與文獻(xiàn)[9]中通過構(gòu)建網(wǎng)格密度矩陣劃分密度閾值, 從而解決DBSCAN參數(shù)選取困難的方法相似。文獻(xiàn)[9]中提到的MDBSCAN算法相比于上述算法能有效發(fā)現(xiàn)密度相差較大的簇, 但由于其使用了從密到疏的分階段聚類方法, 對初始參數(shù)的依賴性依然很大。

為更大程度地降低初始參數(shù)的影響, 筆者提出了改進(jìn)算法, 即在MDBSCAN[9]的基礎(chǔ)上添加了簇排序隊(duì)列。改進(jìn)的算法相比于MDBSCAN更注重?cái)?shù)據(jù)的內(nèi)部簇結(jié)構(gòu)。在聚類的同時(shí)引入可表達(dá)簇信息的隊(duì)列, 根據(jù)隊(duì)列的信息尋找下一個(gè)擴(kuò)展點(diǎn), 因此, 降低了選點(diǎn)的隨機(jī)性。同時(shí), 變化的隊(duì)列相當(dāng)于可變參數(shù), 在每層次閾值的建簇中起到調(diào)整初始參數(shù)的作用, 因此, 降低了參數(shù)的依賴性。

將改進(jìn)的DBSCAN算法應(yīng)用到高性能計(jì)算中心用戶分類中, 可發(fā)現(xiàn)用戶群體行為的共性。通過進(jìn)一步分析不同用戶群體提交作業(yè)和申請資源的特點(diǎn), 可幫助不同用戶建立資源使用策略。這對提高集群整體資源的使用效率有很大意義。

1 DBSCAN算法的主要缺點(diǎn)

DBSCAN算法的思想是利用密度連通特性, 即要求聚類空間中一定區(qū)域內(nèi)對象的數(shù)目不小于某一給定閾值, 從而快速發(fā)現(xiàn)任意形狀的類。但是, 由于它使用了全局性表征密度的參數(shù), 因此在聚類密度不均勻或聚類間距離差距較大時(shí), 聚類質(zhì)量也較差[10,11]。

確定初始參數(shù)E的方法是用戶指定的, 因此很難具有確定性。當(dāng)數(shù)據(jù)密度和類間距離分布不均勻時(shí), 較大的E的初值選取導(dǎo)致將較稀的類的對象誤認(rèn)為是邊界對象, 而較小的E的初值選取會(huì)將不同的類合并為同一類, 從而降低聚類的精度。然而, 真實(shí)世界的數(shù)據(jù)集合往往分布不均。因此, 全局的密度參數(shù)不能刻畫數(shù)據(jù)集的內(nèi)在聚類結(jié)構(gòu)。

對DBSCAN算法的改進(jìn)比較著名的是OPTICS(Ordering Points to Identify the Clustering Strueture)算法, 其思想是對數(shù)據(jù)庫中所有對象進(jìn)行排序, 找出簇結(jié)構(gòu)的信息, 從而確定合適的E值。但由于其復(fù)雜的處理方法以及大量的I/O操作, 使其運(yùn)行速度遠(yuǎn)低于DBSCAN。

2 DBSCAN改進(jìn)算法

2.1 采用多密度閾值解決輸入?yún)?shù)E的全局性

當(dāng)密度不均勻分布時(shí), 需要用不同的鄰域半徑值作為聚類標(biāo)準(zhǔn)。所以, 只要將數(shù)據(jù)空間按照密度大小進(jìn)行劃分, 同一密度空間的數(shù)據(jù)按相同參數(shù)E進(jìn)行聚類即可[9]。

數(shù)據(jù)空間的密度劃分方案可采用網(wǎng)格劃分的方法。將數(shù)據(jù)空間表示為網(wǎng)格形式的密度分布圖, 統(tǒng)計(jì)不同密度的網(wǎng)格數(shù)量。將分布圖的峰值作為網(wǎng)格密度閾值, 按等效規(guī)則轉(zhuǎn)化為DBSCAN算法中的各個(gè)E值。最后將整個(gè)數(shù)據(jù)空間按網(wǎng)格密度從密到疏分階段進(jìn)行局部聚類。

等效規(guī)則的核心思想是： 相同容積內(nèi)的對象數(shù)目相同。在基于網(wǎng)格的CLIQUE(Clustering In Quest)算法中, 將n維空間劃分為長方形單元, 通過比較單元中數(shù)據(jù)點(diǎn)個(gè)數(shù)與輸入模型參數(shù)k, 判斷單元的密集程度。DBSCAN算法在思想上與CLIQUE相同, 只是用半徑為E的n維球形區(qū)域進(jìn)行度量, 因此可將兩者進(jìn)行等效[12]。即

(1)

2.2 采用簇排序序列減小輸入?yún)?shù)MPts對聚類結(jié)果的影響

DBSCAN算法在選取下一個(gè)核心點(diǎn)時(shí)具有隨機(jī)性, 并沒有考慮數(shù)據(jù)的內(nèi)部簇結(jié)構(gòu)。通過增加一個(gè)簇排序隊(duì)列可解決該問題。

簇排序隊(duì)列存儲(chǔ)核心對象及其直接密度可達(dá)對象, 并按可達(dá)距離升序排列。每次選取該隊(duì)列中距離最小的樣本點(diǎn)進(jìn)行拓展。簇排序隊(duì)列的更新是通過求出每次選取核心點(diǎn)直接密度可達(dá)點(diǎn)的可達(dá)距離, 對隊(duì)列進(jìn)行重新排序。簇排序信息相當(dāng)于一個(gè)可變的參數(shù), 使輸入?yún)?shù)的變化不會(huì)影響樣本點(diǎn)的相對輸出順序。

算法中的直接密度可達(dá)的定義如下： 給定一個(gè)對象集合D, 如果p在q的E鄰域內(nèi), 而q是一個(gè)核心對象, 則稱對象p從對象q出發(fā)時(shí)是直接密度可達(dá)的。

3 算法描述

3.1 算法基本流程

1) 將表示x軸和y軸的n維數(shù)據(jù)分別向一維映射, 數(shù)據(jù)做歸一化處理, 形成平面散點(diǎn)圖。

2) 對數(shù)據(jù)空間進(jìn)行網(wǎng)格劃分, 一般以值域的1/20～1/50進(jìn)行劃分, 網(wǎng)格寬度記為B。

3) 統(tǒng)計(jì)網(wǎng)格內(nèi)點(diǎn)數(shù)目, 統(tǒng)計(jì)各層次的數(shù)據(jù)密度占有的網(wǎng)格數(shù), 從而計(jì)算密度閾值的劃分層次。

4) 對每個(gè)層次的密度閾值根據(jù)等效規(guī)則計(jì)算參數(shù)E(MPts設(shè)定為4)。

5) 選取密度最高的網(wǎng)格單元,任選一個(gè)數(shù)據(jù)進(jìn)行類擴(kuò)展, 具體方法如下:

① 創(chuàng)建兩個(gè)隊(duì)列R1,R2。R1用于存儲(chǔ)核心對象及其直接可達(dá)對象, 并按可達(dá)距離升序排列。R2用于存儲(chǔ)已確定分類的樣本點(diǎn)。

② 若該密度的樣本集中所有點(diǎn)都處理完畢, 則進(jìn)入步驟④; 否則, 選一個(gè)不在R2且為核心對象的樣本點(diǎn), 并找到其直接密度可達(dá)點(diǎn), 存入R1中并排序。

③ 從R1中取出可達(dá)距離最小的樣本點(diǎn)進(jìn)行拓展, 并保存至R2中。若該點(diǎn)已經(jīng)存在于R2中, 且具有更小的可達(dá)距離, 則用此點(diǎn)取代舊點(diǎn), 并將R1重新排序。

④ 該密度閾值的簇聚類完畢, 進(jìn)入步驟6)。

6) 采用低一級的密度閾值, 重復(fù)步驟5), 直至完成最低一級密度閾值的聚類。

3.2 算法偽代碼

算法首先求出每個(gè)層次的密度閾值[9], 即先求得每個(gè)網(wǎng)格內(nèi)的點(diǎn)數(shù)目, 并繪制密度分布圖, 由分布圖的每個(gè)峰值作為密度閾值, 算法的偽代碼如下：

procedure threshold_value (U)

begin

if(pis inG(i,j))

thenG(i,j)=G(i,j)+1;//G(i,j)存儲(chǔ)每個(gè)網(wǎng)格內(nèi)的點(diǎn)數(shù)目

endif;

Create density spread graph according toG;//繪制密度分布圖

Store density valueskin threshold[];//確定密度閾值

return threshold;

end

其次, 對每個(gè)層次的閾值用等效規(guī)則計(jì)算不同的參數(shù)E[12], 偽代碼如下：

procedure calculate_E(D)

begin

E=sqrt(MPts*V/(D*π));

returnE;

end

再次, 對每層閾值下的點(diǎn)進(jìn)行聚類, 在原始DBSCAN基礎(chǔ)上增加簇排序隊(duì)列信息, 保證每次從隊(duì)列中取出可達(dá)距離最小的樣本點(diǎn)進(jìn)行拓展, 從而減小初始參數(shù)選取對聚類結(jié)果的影響。算法的偽代碼如下：

procedure queue_dbscan (U,D,MPts)

begin

for each unvisitedpinU

begin

Markpas visited;//將p標(biāo)記為已訪問

N=getNeighbours(p,E);

if sizeof(N)

then Markpas Noise;//將p標(biāo)記為噪聲

else

C=new cluster//建立新簇C

Addp(i) toR1//創(chuàng)建隊(duì)列R1

Sort(R1)//將R1重新排序

Choose(p,R1)//在R1中選擇距離最小的點(diǎn)

Save(p,R2)//將點(diǎn)保存至R2中

if(exists(p,R1)) then//若p已經(jīng)存在

Instead(p,R1)//用新點(diǎn)代替舊點(diǎn)

Sort(R1)//將R1重新排序

endif

endif

endfor

end

最后算法的主調(diào)程序如下：

procedure QDBSCAN(U,MPts)

begin

threshold[]=threshold_value(U);

for each density valuekin threshold[]

begin

E=calculate_E(k);

G=units inUwhose points>k;

Find max unitUmaxinG;

queue_dbscan(Umax,k,MPts);

end

end for

end

4 算法在高性能計(jì)算中心用戶數(shù)據(jù)的實(shí)例分析

該實(shí)驗(yàn)數(shù)據(jù)取自吉林大學(xué)高性能計(jì)算中心集群服務(wù)器的作業(yè)調(diào)度系統(tǒng)Platform LSF產(chǎn)生的日志lsb.events。日志信息由后臺(tái)程序操作存入數(shù)據(jù)庫中, 由應(yīng)用程序完成數(shù)據(jù)統(tǒng)計(jì)。用戶數(shù)據(jù)分析主要包括用戶組成, 用戶使用效果, 用戶操作成熟度和用戶占用資源分析等。相關(guān)數(shù)據(jù)包括作業(yè)成功率、 平均等待時(shí)間、 cpu利用率、 作業(yè)提交成功率、 使用天數(shù)、 作業(yè)規(guī)模和占用核心數(shù)等。

首先, 進(jìn)行數(shù)據(jù)采集, 建立的數(shù)據(jù)庫如圖1所示。

圖1 數(shù)據(jù)庫E-R模型

其次, 對用戶數(shù)據(jù)進(jìn)行統(tǒng)計(jì), 其統(tǒng)計(jì)項(xiàng)目如表1所示。

表1 用戶數(shù)據(jù)統(tǒng)計(jì)表

再次, 將上一步所述數(shù)據(jù)進(jìn)行歸約和整理。即計(jì)算用戶平均作業(yè)規(guī)模和用戶滿意度。平均作業(yè)規(guī)模使用平均消耗cpu時(shí)間進(jìn)行度量

(3)

用戶滿意度使用作業(yè)成功率的正比例函數(shù)與平均隊(duì)列等待時(shí)間的反比例函數(shù)的乘積表示

(4)

因此作業(yè)成功率越高, 平均等待時(shí)間越低, 則滿意度越高。將式(3)、 式(4)結(jié)果歸一化到[0,1], 并作為聚類分析的X和Y坐標(biāo)。最終得到的數(shù)據(jù)集如表2所示。

表2 數(shù)據(jù)采集表

圖2 數(shù)據(jù)網(wǎng)格劃分 圖3 密度分布圖

然后, 對數(shù)據(jù)空間進(jìn)行網(wǎng)格劃分, 結(jié)果如圖2所示。做出密度分布圖, 結(jié)果如圖3所示(B=0.025)。

可得到密度閾值分別為4和6, 根據(jù)等效原則[12]求出鄰域半徑

圖4 聚類結(jié)果

最后, 依次使用閾值4和6, 根據(jù)改進(jìn)聚類算法得出聚類結(jié)果如圖4所示。

從聚類結(jié)果可看出, 用戶分為3類。簇1代表的用戶屬于初級用戶, 占用較少的集群資源, 有較好的滿意度。簇2代表的用戶屬于中級用戶, 該類用戶占用一定集群資源, 但提交作業(yè)的效果并不理想。簇3屬于高級用戶, 該類用戶相對于前兩者占用較多的資源, 且在操作上較為成熟, 有較高的滿意度。

算法分析的數(shù)據(jù)采集自中心試運(yùn)行階段, 用戶數(shù)46, 作業(yè)樣本數(shù)76 582。由于各位老師習(xí)慣于分享賬號給自己課題組的學(xué)生用, 因此賬號數(shù)較少, 實(shí)際使用人數(shù)在220人左右。從數(shù)據(jù)分析結(jié)果看, 簇1用戶整體作業(yè)規(guī)模偏小, 平均等待時(shí)間較短, 提交作業(yè)成功率高, 運(yùn)行成功率高, 具有較高滿意度； 簇2用戶作業(yè)規(guī)模中等, 處于常規(guī)調(diào)度排隊(duì)中, 由于作業(yè)編寫失誤率偏高, 滿意度偏低； 簇3用戶屬于集群大用戶, 在調(diào)度策略中處于較高優(yōu)先級, 通常該類用戶在作業(yè)編寫和運(yùn)行方面較為謹(jǐn)慎, 所以有較高滿意度。通過以上分析說明, 該實(shí)驗(yàn)的結(jié)果符合中心調(diào)度策略的調(diào)整, 具有準(zhǔn)確性和可靠性。

實(shí)際對照用戶信息, 簇1用戶群體分為兩部分： 一部分用戶屬于較成熟的用戶, 以前使用過并行計(jì)算, 作業(yè)數(shù)據(jù)較簡單, 傾向于做對比性測試, 在中心以試用資源為主, 實(shí)際提交的作業(yè)規(guī)模都偏小, 是中心的潛在客戶群; 另一部分是在中心提交大量的單核作業(yè), 計(jì)算時(shí)間較短, 但數(shù)量較大, 如生物類的基因比對等。這部分用戶成熟度較高, 計(jì)算目的明確, 數(shù)據(jù)成熟, 是中心的重要用戶群。簇2用戶較多沒接觸過并行計(jì)算, 用戶中初學(xué)者較多, 提交作業(yè)規(guī)模大且多, 作業(yè)數(shù)據(jù)不合理的偏多, 作業(yè)失敗率偏高, 同時(shí)由于對用戶控制了最大使用資源上限, 導(dǎo)致平均排隊(duì)時(shí)間較長。根據(jù)反饋, 該類用戶的意見較大, 需要進(jìn)行針對性的技術(shù)培訓(xùn), 加深對并行計(jì)算應(yīng)用程序的了解, 以發(fā)展成簇3或簇1類的用戶。簇3用戶大都在校外租用過上海超算的計(jì)算資源, 有成熟的應(yīng)用背景, 計(jì)算有明確的目的性, 是中心要優(yōu)先保障和支持的客戶群體。

改進(jìn)后的算法與同類算法相比, 具有屏蔽輸入?yún)?shù)變化的優(yōu)點(diǎn)。在尋找下一個(gè)擴(kuò)展點(diǎn)時(shí), 其他同類算法采用隨機(jī)選取, 忽略了已形成的簇本身帶來的信息, 因此, 當(dāng)輸入?yún)?shù)產(chǎn)生細(xì)微變化時(shí), 有可能導(dǎo)致輸出點(diǎn)順序上的很大改變。而本算法中利用了簇內(nèi)部的信息, 因此降低了對參數(shù)的依賴, 使算法具有更高的可靠性。

5 結(jié) 語

筆者提出的DBSCAN改進(jìn)算法, 在使用多密度閾值確定參數(shù)的基礎(chǔ)上, 添加一個(gè)簇排序隊(duì)列作為輔助工具, 更進(jìn)一步減小初始參數(shù)選取對聚類結(jié)果的影響。實(shí)驗(yàn)結(jié)果表明, 改進(jìn)的DBSCAN算法能較全面地對高性能計(jì)算中心的用戶進(jìn)行分類, 對調(diào)整調(diào)度策略, 提高集群使用效率等具有現(xiàn)實(shí)意義。

該實(shí)驗(yàn)的研究結(jié)果應(yīng)用在集群作業(yè)調(diào)度方案調(diào)整中, 對不同類用戶針對性地展開相關(guān)的技術(shù)培訓(xùn), 提升用戶體驗(yàn)； 關(guān)注簇2中用戶作業(yè)提交失敗原因并幫助其改善, 提高集群的有效資源使用效率, 從而從整體上提高集群的資源利用率。

參考文獻(xiàn)：

[1]潘玲玲, 張育平, 徐濤. 核DBSCAN算法在民航客戶細(xì)分中的應(yīng)用 [J]. 計(jì)算機(jī)工程, 2012, 38(10): 70-73.

PAN Ling-ling, ZHANG Yu-ping, XU Tao. Nuclear DBSCAN Algorithm in the Application of Civil Aviation Customer Segmentation [J]. Computer Engineering, 2012, 38(10): 70-73.

[2]任鴻, 鄭巖, 吳燁蓉. Clustering Analysis of Telecommunication Customers [J]. 中國郵電高校學(xué)報(bào): 英文版, 2009, 16(2): 114-116.

REN Hong, ZHENG Yan, WU Hua-rong. Clustering Analysis of Telecommumication Customers [J]. China Post and Telecommunications University Journals: English Version, 2009, 16(2): 114-116.

[3]ESTER M, KRIEGEL H, SANDER J, et al. A Density-Based Algorithm for Discovering Cluster S in Large Spatial Databases with Noise [C]∥Proc of the 1996 2nd Int l Conf on Knowledge Discovery and Data Mining. Portland: AAAI Press, 1996: 226-231.

[4]蔡穎琨, 謝昆青, 馬修軍. 屏蔽了輸入?yún)?shù)敏感性的DBSCAN改進(jìn)算法 [J]. 北京大學(xué)學(xué)報(bào), 2004, 40(3): 480-486.

CAI Ying-kun, XIE Kun-qing, MA Xiu-jun. Shielding the Input Parameter Sensitivity of the Improved Algorithm DBSCAN [J]. Journal of Peking University, 2004, 40(3): 480-486.

[5]于亞飛, 周愛武. 一種改進(jìn)的DBSCAN密度算法 [J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2011, 21(2): 30-38.

YU Ya-fei, ZHOU Ai-wu. An Improved DBSCAN Algorithm Density [J]. Computer Technology and Development, 2011, 21(2): 30-38.

[6]武佳薇, 李雄飛, 孫濤, 等. 鄰域平衡密度聚類算法 [J]. 計(jì)算機(jī)研究與發(fā)展, 2010, 47(6)： 1044-1052.

WU Jia-wei, LI Xiong-fei, SUN Tao, et al. Neighborhood Equilibrium Density Clustering Algorithm [J]. Journal of Computer Research and Development, 2010, 47(6): 1044-1052.

[7]王桂芝, 王廣亮. 改進(jìn)的快速DBSCAN算法 [J]. 計(jì)算機(jī)應(yīng)用, 2009, 29(9): 2505-2508.

WANG Gui-zhi, WANG Guang-liang. Improved DBSCAN Algorithm Quickly [J]. Computer Application, 2009, 29(9): 2505-2508.

[8]高迪駒, 王天真, 劉洋, 等. 一種調(diào)整簇閾值的加速聚類分析算法及其應(yīng)用 [J]. 數(shù)據(jù)采集與處理, 2012, 27(3): 278-293.

GAO Di-ju, WANG Tian-zhen, LIU Yang, et al. An Adjust Cluster Threshold Acceleration Clustering Analysis Algorithm and Its Application [J]. Data Acquisition and Processing, 2012, 27(3): 278-293.

[9]譚穎, 胡瑞飛, 殷國富. 多密度閾值的DBSCAN改進(jìn)算法 [J]. 計(jì)算機(jī)應(yīng)用, 2008, 28(3): 745-749.

TAN Ying, HU Rui-fei, YIN Guo-fu. Density Threshold Algorithm DBSCAN [J]. Computer Applications, 2008, 28(3): 745-749.

[10]馬帥, 王滕蛟, 唐世渭, 等. 一種基于參考點(diǎn)和密度的快速聚類算法 [J]. 軟件學(xué)報(bào), 2003, 14(6):1089-1095.

MA Shuai,WANG Teng-jiao, TANG Shi-wei, et al. Based on a Reference Point and Density of Fast Clustering Algorithm [J]. Journal of Software, 2003, 14(6): 1089-1095.

[11]周水庚, 周傲英, 曹晶. 基于數(shù)據(jù)分區(qū)的DBSCAN算法 [J]. 計(jì)算機(jī)研究與發(fā)展, 2000, 37(10): 1154-1159.

ZHOU Shui-geng, ZHOU Ao-ying, CAO Jing. Based on Data Partition of DBSCAN Algorighm [J]. Computer Research and Development, 2000, 37(10): 1154-1159.

[12]HU Rui-fei, YIN Guo-fu, TAN Yin, et al. Cooperative Clustering Based on Grid and Density [J]. Chinese Journal of Mechanical Engineering, 2006, 19(4): 544-547.