段明秀，唐超琳

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

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

隨著計算機(jī)、網(wǎng)絡(luò)和通訊技術(shù)的快速發(fā)展，大量的數(shù)據(jù)被收集并保存在數(shù)據(jù)庫中，迫切需要一種有效的分析方法從海量的數(shù)據(jù)中收集并提取有用的信息.基于密度的聚類算法OPTICS(Ordering Points to I dentify the Clustering Structure，通過點(diǎn)排序識別聚類結(jié)構(gòu))是一種自動交互式的聚類分析方法，它通過擴(kuò)展DBSCAN來同時處理一組距離參數(shù)，沒有產(chǎn)生顯式的數(shù)據(jù)集聚類，只是用簇次序來代表基于密度的聚類結(jié)構(gòu)，該結(jié)構(gòu)包含了從一個寬廣的參數(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è)置很難確定，特別是對于現(xiàn)實(shí)世界中的高維數(shù)據(jù)集.此外，真實(shí)的高維數(shù)據(jù)集常常具有傾斜的分布，全局的密度參數(shù)并不能刻畫其內(nèi)在的聚類結(jié)構(gòu).OPTICS算法就是為了克服這一困難而提出的，它并不顯式地產(chǎn)生數(shù)據(jù)集簇類，只是計算一個基于密度的簇排序，從這個簇排序中可以提取基本的聚類信息.

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

2 OPTICS算法的基本思想

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

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

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

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

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

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

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

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

4 結(jié)語

OPTICS是一種常見的基于密度的聚類算法.在分析OPTICS算法原理的基礎(chǔ)上，采用C++語言實(shí)現(xiàn)該算法.經(jīng)數(shù)據(jù)測試表明，OPTICS算法并沒有產(chǎn)生顯式的數(shù)據(jù)集聚類，它只是產(chǎn)生一個基于密度的簇排序結(jié)構(gòu)，從這個結(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］.北京:中國水利水電出版社，2003:236-245.

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

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

(責(zé)任編輯 向陽潔)

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ù)挖掘、人工智能研究.