一種基于密度的聚類算法實(shí)現(xiàn)*

段明秀，唐超琳

(1.吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南吉首 416000;2.吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南吉首 416000)

一種基于密度的聚類算法實(shí)現(xiàn)*

段明秀1，唐超琳2

(1.吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南吉首 416000;2.吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南吉首 416000)

基于密度的聚類算法OPTICS是一種大規(guī)模數(shù)據(jù)庫(kù)的聚類算法，它是基于核心對(duì)象和可達(dá)距離來(lái)實(shí)現(xiàn)的.對(duì)于每一個(gè)核心對(duì)象將其鄰域內(nèi)的所有對(duì)象按到該核心對(duì)象的可達(dá)距離進(jìn)行排序，每次都選擇1個(gè)到該核心對(duì)象具有最小的可達(dá)距離的對(duì)象進(jìn)行信息更新.算法實(shí)現(xiàn)采用優(yōu)先隊(duì)列保存候選對(duì)象以加快處理速度，最后用UCI數(shù)據(jù)集對(duì)算法進(jìn)行聚類效果測(cè)試，結(jié)果表明OPTICS算法對(duì)數(shù)據(jù)集產(chǎn)生一個(gè)基于密度的簇排序結(jié)構(gòu).

數(shù)據(jù)挖掘;聚類算法;OPTICS;聚類;密度

隨著計(jì)算機(jī)、網(wǎng)絡(luò)和通訊技術(shù)的快速發(fā)展，大量的數(shù)據(jù)被收集并保存在數(shù)據(jù)庫(kù)中，迫切需要一種有效的分析方法從海量的數(shù)據(jù)中收集并提取有用的信息.基于密度的聚類算法OPTICS(Ordering Points to I dentify the Clustering Structure，通過(guò)點(diǎn)排序識(shí)別聚類結(jié)構(gòu))是一種自動(dòng)交互式的聚類分析方法，它通過(guò)擴(kuò)展DBSCAN來(lái)同時(shí)處理一組距離參數(shù)，沒(méi)有產(chǎn)生顯式的數(shù)據(jù)集聚類，只是用簇次序來(lái)代表基于密度的聚類結(jié)構(gòu)，該結(jié)構(gòu)包含了從一個(gè)寬廣的參數(shù)設(shè)置范圍進(jìn)行基于密度聚類所需的信息［1］.在許多的數(shù)據(jù)挖掘軟件如Weka和ELKI中都實(shí)現(xiàn)了該算法，所以研究和實(shí)現(xiàn)該算法具有一定的實(shí)際意義.

1 OPTICS算法概述

OPTICS［1］是DBSCAN算法的擴(kuò)展.盡管DBSCAN算法能根據(jù)用戶輸入的參數(shù)產(chǎn)生聚類結(jié)果，但是它將產(chǎn)生可接受的聚類結(jié)果的責(zé)任交給用戶，參數(shù)的設(shè)置很難確定，特別是對(duì)于現(xiàn)實(shí)世界中的高維數(shù)據(jù)集.此外，真實(shí)的高維數(shù)據(jù)集常常具有傾斜的分布，全局的密度參數(shù)并不能刻畫其內(nèi)在的聚類結(jié)構(gòu).OPTICS算法就是為了克服這一困難而提出的，它并不顯式地產(chǎn)生數(shù)據(jù)集簇類，只是計(jì)算一個(gè)基于密度的簇排序，從這個(gè)簇排序中可以提取基本的聚類信息.

基于密度的聚類算法中需要用到的相關(guān)定義(如ε鄰域、密度閥值MinPts、核心對(duì)象、直接密度可達(dá)、密度可達(dá)、密度相連、噪聲等)、OPTICS算法中2個(gè)重要的定義(核心距離(core-distance)、可達(dá)距離(reachability-distance))，可參見(jiàn)文獻(xiàn)［2-4］.

2 OPTICS算法的基本思想

假設(shè)對(duì)一個(gè)給定的數(shù)據(jù)對(duì)象集合D［5］，作以下操作:

(i)首先初始化D中每個(gè)對(duì)象的可達(dá)距離和核心距離為未定義狀態(tài)，同時(shí)標(biāo)記為未處理狀態(tài).

(ii)設(shè)有優(yōu)先隊(duì)列seed，從D中取出一個(gè)對(duì)象p，若p是被處理的對(duì)象，則取得p的ε鄰域，設(shè)置p為已被處理，將p加入到結(jié)果隊(duì)列中.若p是一個(gè)核心對(duì)象，則更新p的ε鄰域中所有未被處理的對(duì)象的可達(dá)距離，同時(shí)將那些已經(jīng)更新但不在seed中的對(duì)象加入到seed中.seed這個(gè)優(yōu)先隊(duì)列中所保存的對(duì)象是按對(duì)象的可達(dá)距離從小到大排列的.因?yàn)槊看芜x擇的候選擴(kuò)展對(duì)象都是到當(dāng)前核心對(duì)象具有最小的可達(dá)距離，所以采用優(yōu)先隊(duì)列來(lái)保存候選對(duì)象.

(iii)對(duì)于(ii)中得到的優(yōu)先隊(duì)列seed，當(dāng)這個(gè)隊(duì)列不為空時(shí)取出該隊(duì)列的第1個(gè)對(duì)象q，取得q的ε鄰域，標(biāo)記q為已被處理，將q加入到結(jié)果隊(duì)列中.若q是核心對(duì)象，那么更新q的ε鄰域中所有未被處理的對(duì)象.若這個(gè)需要更新的對(duì)象不在seed中，則更新后將這個(gè)對(duì)象加入到seed中.重復(fù)上述步驟直到seed為空結(jié)束.

(iv)重復(fù)步驟(ii)和(iii)，當(dāng)D中所有的對(duì)象都是被處理的狀態(tài)時(shí)算法結(jié)束.

3 OPTICS算法實(shí)驗(yàn)驗(yàn)證

文中的測(cè)試數(shù)據(jù)來(lái)自UCI中的Iris和Glass，Iris中有150個(gè)數(shù)據(jù)對(duì)象，每個(gè)對(duì)象代表一種鳶尾花，150個(gè)對(duì)象分別來(lái)自3類花種.Glass中有214個(gè)數(shù)據(jù)對(duì)象，每個(gè)對(duì)象代表一種類型的玻璃，214個(gè)對(duì)象分別來(lái)自7類玻璃.為了方便現(xiàn)實(shí)聚類效果，將那些可達(dá)距離為未定義的對(duì)象的可達(dá)距離置為1.8倍的ε.

測(cè)試數(shù)據(jù)Iris聚類效果(ε=0.9，minPts=6，屬性數(shù)5，無(wú)噪聲數(shù)據(jù))如圖1所示.

4 結(jié)語(yǔ)

OPTICS是一種常見(jiàn)的基于密度的聚類算法.在分析OPTICS算法原理的基礎(chǔ)上，采用C++語(yǔ)言實(shí)現(xiàn)該算法.經(jīng)數(shù)據(jù)測(cè)試表明，OPTICS算法并沒(méi)有產(chǎn)生顯式的數(shù)據(jù)集聚類，它只是產(chǎn)生一個(gè)基于密度的簇排序結(jié)構(gòu)，從這個(gè)結(jié)構(gòu)可以提取出基于密度聚類所需的其他信息.

［1］ MIHAEL ANKERST，MARKUS M BREUNIG，HANS-PETER KRIEGEL，et al.OPTICS:Ordering Points to Identify the Clustering Structure［M］.Germany:Institute for Computer Science，University of Munich Oettingenstr，1999:49-60.

［2］ HAN Jia-wei，MICHELINE KAMBER.數(shù)據(jù)挖掘概念與技術(shù)［M］.北京:機(jī)械工業(yè)出版社，2007:212-235.

［3］ 邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法［M］.北京:中國(guó)水利水電出版社，2003:236-245.

［4］ TAN Pang-ning，MICHAEL STEINBACH VIPIN KUNMAR.數(shù)據(jù)挖掘?qū)д摚跰］.北京:人民郵電出版社，2006:226-228.

［5］ 陳燕俐，洪 龍，金達(dá)文，等.一種簡(jiǎn)單有效的基于密度的聚類分析算法［J］.南京郵電學(xué)院學(xué)報(bào)，2005，25(4):24-28.

(責(zé)任編輯 向陽(yáng)潔)

Realization of Clustering Algorithm Based on Density

DUAN Ming-xiu1，TANG Chao-lin2
(1.College of Mathematics and Statistics，Jishou University，Jishou 416000，Hunan China;2.College of Informtion Science and Engineering，Jishou University，Jishou 416000，Hunan China)

The OPTICS clustering algorithms is an large database，density-based clustering algorithm.This algorithm is realized based on the core object and reachability-distance.For every core object，all objects in its neighbourhood will be sorted by the reachability-distance from this core object，and the one with the minimum reachability-distance is always chosen to update information.The realization of OPTICS algorithm adopts priority queue to accelerate the speed.The clustering performance is tested by UCI datasets.The results show that the OPTICS algorithm achieves a clustering structure based on density.

data mining;clustering algorithm;OPTICS;clustering;density

TP311.1

A

10.3969/j.issn.1007-2985.2013.01.007

1007-2985(2013)01-0026-02

2012-12-07

湖南省教育廳科學(xué)研究項(xiàng)目(11C1025);吉首大學(xué)學(xué)生科研項(xiàng)目(11JDX052)

段明秀(1975-)，女，湖南茶陵人，吉首大學(xué)信息科學(xué)與工程學(xué)院講師，碩士，主要從事數(shù)據(jù)挖掘、人工智能研究.