（計(jì)算機(jī)軟件與理論專業(yè)論文）基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究.pdf

蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 摘要 聚類分析作為數(shù)據(jù)挖掘的一個(gè)重要任務(wù) 具有廣泛的應(yīng)用領(lǐng)域 這些不同的 應(yīng)用都對(duì)聚類分析算法提出了新的要求 本文提出了基于網(wǎng)格的并行聚類分析算法p g m c l u 該算法的創(chuàng)新點(diǎn)主要 包括 定義了網(wǎng)格緊湊度 網(wǎng)格密度連通 網(wǎng)格特征值 簇密度以及簇相似度的 概念 提出了基于網(wǎng)格單元?jiǎng)澐值臄?shù)據(jù)分區(qū)方法 基于網(wǎng)格密度連通概念的局部 聚類方法 以及基于簇相似度度量的局部聚類合并方法 實(shí)現(xiàn)了對(duì)網(wǎng)格密度閾值 參數(shù)m i n p t s 的自適應(yīng)設(shè)置 該算法可以較好地處理高維和海量數(shù)據(jù)集 并具有識(shí) 別不同形狀和密度簇的能力 數(shù)據(jù)流是指潛在無(wú)限的 持續(xù)而快速到達(dá)的具有時(shí)間順序的數(shù)據(jù)對(duì)象的集合 數(shù)據(jù)流的實(shí)時(shí)性和潛在無(wú)限性 決定了數(shù)據(jù)流聚類分析算法與傳統(tǒng)的基于靜態(tài)數(shù) 據(jù)的聚類分析算法相比 具有一些新的特性 本文提出了基于網(wǎng)格的數(shù)據(jù)流聚類分析算法g c s t r e a m 該算法的創(chuàng)新點(diǎn)主 要包括 提出了描述網(wǎng)格單元概要信息的特征向量結(jié)構(gòu) 對(duì)s p t r e e 做了改進(jìn) 提出了基于l i s t 結(jié)構(gòu)的l s p t r e e 空間索引結(jié)構(gòu) 提出了對(duì)網(wǎng)格單元信息的指數(shù) 衰減策略 以及對(duì)噪聲網(wǎng)格單元和過(guò)時(shí)網(wǎng)格單元的剪枝策略 該算法較好地滿足 了數(shù)據(jù)流聚類分析的實(shí)時(shí)性要求 并對(duì)內(nèi)存空間具有動(dòng)態(tài)的適應(yīng)性 詳細(xì)而全面的實(shí)驗(yàn)證明了p g m c l u 和g c s t r e a m 算法的正確性和有效性 因此 這些研究成果具有重要的理論價(jià)值和實(shí)際意義 關(guān)鍵詞 網(wǎng)格 并行 聚類分析 多密度簇 數(shù)據(jù)流聚類 l s p t r e e 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 a b s t r a c t c l u s t e r i n ga n a l y s i s a sa ni m p o r t a n tt a s ko fd a t am i m n g h a sw i d ea p p l i c a t i o n f i e l d s t h e s ed i f f e r e n ta p p l i c a t i o n sr a i s es o m en o v e lr e q u i r e m e n t sf o rc l u s t e r i n g a n a l y s i sa l g o r i t h m t h i st h e s i s p r o p o s e s an o v e lg r i d b a s e dp a r a l l e l c l u s t e r i n ga l g o r i t h m f o r m u l t i d e n s i t yd a t a s e t s c a l l e dp g m c l u t h ei n n o v a t i v ew o r k so fi ta r ea sf o l l o w s d e f i n et h ec o n c e p t s i n c l u d i n gg r dc o m p a c t n e s s g r i dd e n s i t y c o n n e c t e d g r i df e a t u r e c l u s t e rd e n s i t ya n dc l u s t e rs i m i l a r i t y p r o p o s et h em e t h o df o rd a t ap a r t i t i o nb a s e do n g r dp a r t i t i o n t h em e t h o df o rl o c a lc l u s t e r i n gb a s e do ng r i dd e n s i t y c o n n e c t e dc o n c e p t a n dt h em e t h o df o rm e r g i n gl o c a lc l u s t e r sb a s e do nc l u s t e rs i m i l a r i t ym e a s u r e r e a l i z e t h ea d a p t i v es e tf o rp a r a m e t e rm i n p t s p g m c l ua l g o r i t h mc a nb e t t e rh a n d l e h i g h d i m e n s i o n a la n dm a s s i v ed a t a s e t s a n dc a nb ec a p a b l eo fi d e n t i f y i n gc l u s t e r s w i t hd i s t i n g u i s h e ds h a p ea n dd e n s i t y d a t as t r e a mi sas e q u e n c ec o m p o s e do fas e r i e so fi n f i n i t e s u c c e s s i v e h i g h s p e e d a n dt i m e o r d e r e dd a t ao b j e c t s d a t as t r e a mh a st h ec h a r a c t e r i s t i c so f r e a l t i m ea n di n f i n i t y w h i c hd e t e r m i n e st h a tc l u s t e r i n ga l g o r i t h mf o rd a t as t r e a m c o m p a r e d w i t ht r a d i t i o n a l c l u s t e r i n ga l g o r i t h m f o rs t a t i cd a t a s e th a ss o m e d i s t i n g u i s h e dp r o p e r t i e s t h i st h e s i sp r o p o s e st h eg r i d b a s e dc l u s t e r i n ga l g o r i t h mf o rd a t as t r e a m s h o r t e n f o rg c s t r e a m t h ei n n o v a t i v ew o r k so fi ta r ea sf o l l o w s p r o p o s et h ec o n c e p to fg r i d f e a t u r ev e c t o rf o rd e s c r i b i n gt h eg r i ds u m m a r yi n f o r m a t i o n i m p r o v et h es p t r e e s t r u c t u r e a n dp r o p o s et h en o v e ls p a t i a li n d e xs t r u c t u r el s p t r e eb a s e do nl i s td a t a s t r u c t u r e p r o p o s et h ee x p o n e n t i a ld a m p e ds t r a t e g yf o rg r i di n f o r m a t i o n a n dt h e p r u n i n gs t r a t e g yf o rn o i s yg r i da n do u t d a t e dg r i d g c s t r e a ma l g o r i t h mc o nb e t t e r s a t i s f yt h er e a l t i m er e q u i r e m e n to fd a t as t r e a mc l u s t e r i n g a n dc a nb ea d a p t i v ef o r m e m o r ys i z e d e t a i l e da n dc o m p l e t e e x p e r i m e n t s h a v e p r o v e d t h ec o r r e c t n e s sa n d e f f e c t i v e n e s so fp g m c l ua n dg c s t r e a ma l g o r i t h m t h e r e f o r e t h e s en o v e l a l g o r i t h m sw i l lh a v es i g n i f i c a n tt h e o r e t i cv a l u ea n dp r a c t i c a lr o l e k e y w o r d s g r i d p a r a l l e l i s m c l u s t e r i n ga n a l y s i s m u l t i d e n s i t yc l u s t e r c l u s t e r i n g 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 a n a l y s i sf o rd a t as t r e a m s p a t i a lp a r t i t i o nt r e eb a s e do nl i s td a t as t r u c t u r e 原創(chuàng)性聲明 本人鄭重聲明 本人所呈交的學(xué)位論文 是在導(dǎo)師的指導(dǎo)下獨(dú)立 進(jìn)行研究所取得的成果 學(xué)位論文中凡引用他人已經(jīng)發(fā)表或未發(fā)表的 成果 數(shù)據(jù) 觀點(diǎn)等 均已明確注明出處 除文中已經(jīng)注明引用的內(nèi) 容外 不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫過(guò)的科研成果 對(duì) 本文的研究成果做出重要貢獻(xiàn)的個(gè)人和集體 均己在文中以明確方式 標(biāo)明 本聲明的法律責(zé)任由本人承擔(dān) 論文作者簽名 犟顯豸塾 日期 關(guān)于學(xué)位論文使用授權(quán)的聲明 本人在導(dǎo)師指導(dǎo)下所完成的論文及相關(guān)的職務(wù)作品 知識(shí)產(chǎn)權(quán)歸 屬蘭州大學(xué) 本人完全了解蘭州大學(xué)有關(guān)保存 使用學(xué)位論文的規(guī)定 同意學(xué)校保存或向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的紙質(zhì)版和電子版 允許論文被查閱和借閱 本人授權(quán)蘭州大學(xué)可以將本學(xué)位論文的全部 或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索 可以采用任何復(fù)制手段保存和 匯編本學(xué)位論文 本人離校后發(fā)表 使用學(xué)位論文或與該論文直接相 關(guān)的學(xué)術(shù)論文或成果時(shí) 第一署名單位仍然為蘭州大學(xué) 保密論文在解密后應(yīng)遵守此規(guī)定 論文作者簽名 甾熟 導(dǎo)師簽名 圜 日期 型 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 1 1 研究背景及意義 第一章緒論 數(shù)據(jù)挖掘 d a t am i m n g 是指發(fā)現(xiàn)數(shù)據(jù)中蘊(yùn)含的潛在有用的知識(shí)的過(guò)程 知 識(shí)包括規(guī)則 模式及結(jié)構(gòu)等 數(shù)據(jù)挖掘涉及到多個(gè)學(xué)科 包括數(shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù) 統(tǒng)計(jì)學(xué) 信息檢索 人工智能 神經(jīng)網(wǎng)絡(luò) 模糊集 粗糙集 信號(hào)處理 高性能 計(jì)算等 數(shù)據(jù)挖掘理論的應(yīng)用領(lǐng)域廣泛 包括圖像處理 生物信息學(xué) 氣象信息 分析 社會(huì)網(wǎng)絡(luò)分析 圖挖掘 入侵檢測(cè) 數(shù)據(jù)流挖掘 時(shí)問(wèn)序列預(yù)測(cè)等 基本 的數(shù)據(jù)挖掘技術(shù)包括頻繁模式挖掘 分類和預(yù)測(cè)以及聚類分析 聚類分析 c l u s t e r i n ga n a l y s i s 是一項(xiàng)基本的數(shù)據(jù)挖掘任務(wù) 聚類分析是將 數(shù)據(jù)對(duì)象集合根據(jù)對(duì)象之間的相似度度量劃分為簇 c l u s t e r 的過(guò)程 聚類分析 的基本方法包括 基于劃分的方法 p a r t i t i o n b a s e dm e t h o d s 基于層次的方法 h i e r a r c h y b a s e dm e t h o d s 基于密度的方法 d e n s i t y b a s e dm e t h o d s 基于網(wǎng) 格的方法 鰣d b a s e dm e t h o d s 和基于模型的方法 m o d e l b a s e dm e t h o d s 基于 劃分的方法包括k m e a n s 1 p a m 2 c l a r a 2 和c l a r a n s 3 等 基于層 次的方法包括b i r c h 4 r o c k 5 c u r e 6 c h a m e l e o n 7 等 基于密度的方 法包括d b s c a n 8 o p t i c s 9 d e n c l u e 1 0 等 基于網(wǎng)格的方法包括 c l i q u e 1 1 s t i n g 1 2 w a v e c l u s t e r 1 3 d c l u s t 1 4 p r o c l u s 1 5 等 基于模型的方法包括s o m 1 6 和c o b w e b 1 7 等 除了這些基本的聚類分析方 法之外 目前 聚類分析的熱點(diǎn)研究領(lǐng)域包括基于約束的聚類 數(shù)據(jù)流聚類 子 空間聚類 增量聚類 基于遺傳算法的聚類 基于蟻群算法的聚類等 基于網(wǎng)格的聚類分析算法是聚類分析中一種非常重要的方法 在聚類高維和 海量數(shù)據(jù)集時(shí)具有明顯的優(yōu)勢(shì) 基于網(wǎng)格的聚類算法將數(shù)據(jù)空間量化為有窮數(shù)目 的網(wǎng)格單元 然后將數(shù)據(jù)對(duì)象投影到這些網(wǎng)格單元中 并保存網(wǎng)格單元的摘要信 息 s u m m a r i z a t i o ni n f o r m a t i o n 所有的聚類操作都在這些網(wǎng)格單元上面進(jìn)行 不同的基于網(wǎng)格的聚類分析算法在如下方面存在差異 包括網(wǎng)格劃分策略 常見(jiàn) 的包括靜態(tài)劃分和動(dòng)態(tài)劃分兩種 網(wǎng)格摘要信息結(jié)構(gòu) 網(wǎng)格單元集合索引結(jié)構(gòu) 噪聲數(shù)據(jù)的處理和簇的識(shí)別機(jī)制等 目前 最新的基于網(wǎng)格的聚類分析算法包括 l 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 g r i d b s c a n 18 1 g m d b s c a n 19 e d a c l u s t e r 2 0 g r i d b s c a n 21 g n n 2 2 s c i 2 3 m m n g 2 4 g d i l c 2 5 i g d c a 2 6 算法等 這些算法中的部分算法 將在2 3 節(jié)中詳細(xì)分析 基本的基于網(wǎng)格的聚類分析算法的聚類過(guò)程的時(shí)間復(fù)雜 度主要依賴于數(shù)據(jù)空間中包含的網(wǎng)格單元的數(shù)目 具有近似線性的時(shí)間復(fù)雜度 此外 其還能夠較好地處理高維和海量數(shù)據(jù)集 在增量聚類和子空間聚類等方面 也體現(xiàn)出優(yōu)勢(shì) 因此 它在聚類分析中得到了廣泛的研究和應(yīng)用 集群系統(tǒng) 2 7 2 8 1 1 2 9 p c sc l u s t e rs y s t e m 在近年來(lái)得到廣泛的應(yīng)用 集群 系統(tǒng)是將一組高性能的計(jì)算機(jī)通過(guò)特定的網(wǎng)絡(luò)結(jié)構(gòu)聯(lián)接起來(lái) 在操作系統(tǒng)和并行 環(huán)境的支撐下 實(shí)現(xiàn)對(duì)系統(tǒng)資源的統(tǒng)一管理和協(xié)調(diào)調(diào)度 它通過(guò)消息傳遞的機(jī)制 為程序設(shè)計(jì)人員提供了一個(gè)整體的并行編程環(huán)境 基于m p i m e s s a g ep a s s i n g i n t e r f a c e 的并行編程技術(shù)提高了集群系統(tǒng)環(huán)境下并行程序開發(fā)的效率 由于集 群系統(tǒng)具有高性能 h i i g hp e r f o r m a n c e 可擴(kuò)展性 s c a l a b i l i t y 高可用性 a v a i l a b i l i t y 透明性 t r a n s p a r e n c y 可編程性 p r o g r a m m a b i l i t y 等典型特 征 因此 集群系統(tǒng)在大規(guī)模數(shù)據(jù)處理 圖像處理 工程計(jì)算等領(lǐng)域得到越來(lái)越 廣泛的應(yīng)用 數(shù)據(jù)的海量性和高維性都給聚類分析算法帶來(lái)了挑戰(zhàn) 而集群系統(tǒng)的這些特 征給研究集群系統(tǒng)下的并行的聚類分析算法帶來(lái)了機(jī)遇 此外 實(shí)際的數(shù)據(jù)集中 經(jīng)常包含密度不同的簇 傳統(tǒng)的基于密度的聚類分析算法 如d b s c a n 往往 不能得到準(zhǔn)確的聚類結(jié)果 而針對(duì)多密度數(shù)據(jù)集的聚類分析算法 如s n n 3 0 3 1 又存在算法時(shí)間復(fù)雜度高以及聚類結(jié)果精度差 主要體現(xiàn)在對(duì)噪聲數(shù)據(jù)的處理方 面 等問(wèn)題 因此 研究適合于多密度數(shù)據(jù)集的聚類分析算法也是一個(gè)熱門的研 究方向 數(shù)據(jù)流是指連續(xù)且具有時(shí)間順序的數(shù)據(jù)構(gòu)成的集合 數(shù)據(jù)流是伴隨著人們對(duì) 實(shí)時(shí)數(shù)據(jù)的處理而產(chǎn)生的 如電信通話數(shù)據(jù) 銀行交易數(shù)據(jù) 證券交易數(shù)據(jù) 網(wǎng) 絡(luò)流量監(jiān)測(cè)數(shù)據(jù) 網(wǎng)絡(luò)操作日志數(shù)據(jù) 氣象監(jiān)測(cè)數(shù)據(jù) 傳感器數(shù)據(jù)等 3 2 3 3 3 4 3 5 數(shù)據(jù)流具有連續(xù)性 按時(shí)間順序的 潛在無(wú)限的 快速變化的 等特性 這些特性給數(shù)據(jù)流聚類分析算法帶來(lái)了挑戰(zhàn) 與傳統(tǒng)的基于靜態(tài)數(shù)據(jù)的 聚類分析算法相比 數(shù)據(jù)流聚類分析算法具有三個(gè)明顯的特性 1 它強(qiáng)調(diào)時(shí)間 性 數(shù)據(jù)流聚類分析算法必須能夠發(fā)現(xiàn)數(shù)據(jù)流的演變規(guī)律或任意時(shí)問(wèn)段內(nèi)的數(shù)據(jù) 流聚類結(jié)果 2 單遍掃描 由于受到內(nèi)存空i 日j 的限制和數(shù)據(jù)流聚類分析算法實(shí) 2 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 時(shí)性的要求 數(shù)據(jù)流聚類分析算法必須實(shí)現(xiàn)對(duì)數(shù)據(jù)對(duì)象的單遍掃描 3 強(qiáng)調(diào)對(duì) 摘要數(shù)據(jù)結(jié)構(gòu) s u m m a r yd a t as t r u c t u r e 的設(shè)計(jì) 數(shù)據(jù)流聚類分析算法必須將數(shù) 據(jù)對(duì)象的信息以摘要數(shù)據(jù)結(jié)構(gòu)的形式保存起來(lái) 以方便聚類算法對(duì)摘要結(jié)構(gòu)的分 析 目前 典型的數(shù)據(jù)流聚類分析算法包括s t r e a m 3 6 c l u s t r e a m 3 7 h p s t r e a m 3 8 a i n s t r e a m 3 9 c e l lt r e e s 4 0 等 針對(duì)數(shù)據(jù)流聚類分析算法的這 些新的特性 數(shù)據(jù)流聚類分析算法已經(jīng)變成數(shù)據(jù)挖掘中的一個(gè)研究熱點(diǎn) 1 2 研究?jī)?nèi)容 本文針對(duì)當(dāng)前聚類分析算法存在的問(wèn)題 結(jié)合最新的研究成果 主要開展了 對(duì)基于網(wǎng)格的并行的聚類分析算法和基于網(wǎng)格的數(shù)據(jù)流聚類分析算法的研究 具 體的研究?jī)?nèi)容包括 1 維災(zāi)難 d i m e n s i o nc u r s e 問(wèn)題已經(jīng)成為聚類分析算法處理高維數(shù)據(jù) 集時(shí)的一個(gè)主要問(wèn)題 同時(shí) 許多聚類分析算法 如d b s c a n s n n 等 在處 理海量數(shù)據(jù)集時(shí)也面臨高的時(shí)問(wèn)復(fù)雜度 如o n 2 其中 是數(shù)據(jù)對(duì)象的數(shù)目 的困擾 此外 針對(duì)多密度數(shù)據(jù)集的聚類分析算法存在時(shí)間復(fù)雜度高及聚類結(jié)果 精確度不高 主要表現(xiàn)在對(duì)噪聲數(shù)據(jù)的處理方面 等問(wèn)題 本文針對(duì)這些問(wèn)題 提出了基于網(wǎng)格的并行的聚類分析算法 g r i d b a s e dp a r a l l e lc l u s t e r i n ga n a l y s i s a l g o r i t h mf o rm u l t i d e n s i t yd a t a s e t s 簡(jiǎn)稱p g m c l u p g m c l u 算法基于數(shù)據(jù)并 行 d a t ap a r a l l e l i s m 的思想 這是一種典型的分而治之的方法 通過(guò)各個(gè)節(jié)點(diǎn) 對(duì)數(shù)據(jù)的獨(dú)立聚類和最終聚類結(jié)果的合并實(shí)現(xiàn)了對(duì)整個(gè)數(shù)據(jù)集的聚類 p g m c l u 算法提出了網(wǎng)格緊湊度 網(wǎng)格密度直接可達(dá) 網(wǎng)格密度可達(dá) 網(wǎng)格密 度連通等概念 其中網(wǎng)格緊湊度 g r i dc o m p a c t n e s s 度量較好地反映了網(wǎng)格中數(shù) 據(jù)點(diǎn)之間的緊密程度 提出了新的網(wǎng)格劃分方法 以及基于參考維的數(shù)據(jù)分區(qū)策 略 實(shí)現(xiàn)了根據(jù)數(shù)據(jù)的分布特征自動(dòng)確定m i n p t s 參數(shù)的值 為了更好地適應(yīng)分而 治之的策略 提出了利用網(wǎng)格特征向量來(lái)描述網(wǎng)格的摘要信息結(jié)構(gòu) 并建立了 s p t r e e 提高鄰居網(wǎng)格的查找效率 提出了基于網(wǎng)格密度連通概念的聚類方法 以及識(shí)別邊界網(wǎng)格中邊界數(shù)據(jù)點(diǎn)的方法 提出了簇密度和簇相似性的概念 并且 基于它們提出了簇合并算法 最后 對(duì)該算法進(jìn)行了性能分析和實(shí)驗(yàn)驗(yàn)證 2 針對(duì)如何設(shè)計(jì)有效的能夠?qū)B續(xù)的數(shù)據(jù)流進(jìn)行快速處理 并能發(fā)現(xiàn)數(shù) 蘭州大學(xué)碩士學(xué)位論文 基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 據(jù)流的演變規(guī)律的要求 本文提出了基于網(wǎng)格的數(shù)據(jù)流聚類分析算法 g r i d b a s e d c l u s t e r i n ga n a l y s i sa l g o r i t h mf o rd a t as t r e a m 簡(jiǎn)稱g c s t r e a m g c s t r e a m 算法 采用了衰減窗h 模型 d a m p e dw i n d o wm o d e l 來(lái)發(fā)現(xiàn)數(shù)據(jù)流的演變規(guī)律 g c s t r e a m 算法提出了新的聚類模型l s p t r e e 提出了聚類模型維護(hù)策略以及聚 類模型的剪枝策略 較好地實(shí)現(xiàn)了模型對(duì)數(shù)據(jù)對(duì)象的快速處理 以及適應(yīng)了數(shù)據(jù) 流聚類分析算法對(duì)內(nèi)存空間的限制要求 最后 通過(guò)實(shí)驗(yàn)驗(yàn)證和評(píng)價(jià)了算法的正 確性和性能 1 3 論文組織結(jié)構(gòu) 本文圍繞著基于網(wǎng)格的聚類分析算法的研究與實(shí)現(xiàn) 從并行化基于網(wǎng)格的聚 類分析算法和設(shè)計(jì)基于網(wǎng)格的數(shù)據(jù)流聚類分析算法兩個(gè)方面 開展了研究工作 論文內(nèi)容按照以下結(jié)構(gòu)組織 第一章 緒論 主要介紹了課題研究的背景 意義 內(nèi)容及論文組織結(jié)構(gòu) 引出了論文的主要研究?jī)?nèi)容為基于網(wǎng)格的并行的聚類分析算法以及基于網(wǎng)格的 數(shù)據(jù)流聚類分析算法 第二章 基于網(wǎng)格的聚類分析算法概述 首先 介紹了聚類分析的概念及過(guò) 程 對(duì)聚類分析過(guò)程的每個(gè)步驟中涉及到的關(guān)鍵技術(shù)進(jìn)行了詳細(xì)的闡釋 其次 分析了不同的應(yīng)用對(duì)聚類分析算法提出的特定要求 并給出了聚類分析算法面臨 的挑戰(zhàn) 最后 闡釋了基于網(wǎng)格的聚類分析算法的基本原理及特點(diǎn) 并詳細(xì)分析 了四種典型的基于網(wǎng)格的聚類分析算法的原理及特性 包括c l i q u e g r i d b s c a n g m d b s c a n 和g n n 算法 第三章 并行的基于網(wǎng)格的聚類分析算法 p g m c l u 首先 描述了p g m c l u 算法的總體框架 對(duì)算法中涉及到的幾個(gè)重要的過(guò)程進(jìn)行了闡釋 其次 介紹了 算法中涉及到的基本概念 然后 詳細(xì)描述了算法的實(shí)現(xiàn)過(guò)程 包括數(shù)據(jù)分區(qū) 構(gòu)建s p t r e e 局部聚類和局部聚類合并這四個(gè)關(guān)鍵的步驟 對(duì)步驟中涉及到的 關(guān)鍵技術(shù)進(jìn)行了具體闡釋 接下來(lái) 從時(shí)i 日j 復(fù)雜度和加速比方面分析了算法的性 能 最后 從聚類準(zhǔn)確性 相對(duì)加速比以及效率三個(gè)方面對(duì)算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證 和性能評(píng)價(jià) 第四章 基于網(wǎng)格的數(shù)據(jù)流聚類分析算法g c s t r e a m 首先 介紹了數(shù)據(jù)流 4 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 的概念 以及數(shù)據(jù)流聚類分析的特性 窗口模型及典型算法 其次 描述了算法 的總體框架 然后 從聚類模型 模型維護(hù) 更新和剪枝策略方面對(duì)算法進(jìn)行了 詳細(xì)的描述 最后 分析算法性能并給出實(shí)驗(yàn)驗(yàn)證和性能評(píng)價(jià) 第五章 總結(jié)與展望 總結(jié)本文的研究工作 并展望未來(lái)的研究方向 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 第二章基于網(wǎng)格的聚類分析算法概述 2 1 聚類分析概念及過(guò)程 聚類分析 c l u s t e r i n ga n a l y s i s 是數(shù)據(jù)挖掘 d a t am i n i n g 技術(shù)的重要一種 相對(duì)于分類算法而言 聚類分析算法事先不知道類的標(biāo)號(hào) 因此 其也被稱為無(wú) 監(jiān)督的學(xué)習(xí) u n s u p e r v i s e dl e a r n i n g 聚類分析指的是將對(duì)象集合根據(jù)對(duì)象之間 的相似度度量劃分為不同的簇 c l u s t e r 的過(guò)程 對(duì)象之間的相似度通常通過(guò)計(jì) 算它們之問(wèn)的距離來(lái)度量 距離的計(jì)算方式因聚類分析處理的數(shù)據(jù)類型的不同而 異 聚類分析源于統(tǒng)計(jì)學(xué) 數(shù)據(jù)挖掘 生物學(xué)以及機(jī)器學(xué)習(xí)等多個(gè)領(lǐng)域 目前 聚類分析已被廣泛地應(yīng)用于信息檢索 圖像處理 模式識(shí)別 w e b 信息處理 市 場(chǎng)調(diào)研 地理學(xué) 醫(yī)學(xué) 生物信息學(xué) 空間數(shù)據(jù)分析等多個(gè)方面 一個(gè)有實(shí)際價(jià) 值的聚類分析算法通常包括5 個(gè)關(guān)鍵的處理步驟 數(shù)據(jù)預(yù)處理 相似度定義 聚 類 聚類結(jié)果輸出 聚類結(jié)果解釋 2 1 1 數(shù)據(jù)預(yù)處理 數(shù)據(jù)預(yù)處理主要包括數(shù)據(jù)清理 數(shù)據(jù)變換和數(shù)據(jù)規(guī)約功能 數(shù)據(jù)清理包括補(bǔ) 充缺失值 光滑數(shù)據(jù) 剔除噪聲數(shù)據(jù)等 數(shù)據(jù)變換將數(shù)據(jù)轉(zhuǎn)換成適合于聚類分析 的形式 數(shù)據(jù)變換通常包括光滑 聚集 數(shù)據(jù)泛化 規(guī)范化和屬性構(gòu)造 數(shù)據(jù)規(guī) 約是在保持原數(shù)據(jù)集的完整性的同時(shí)得到數(shù)據(jù)集的規(guī)約表示 聚類分析中經(jīng)常用 到的規(guī)約方法是屬性子集選擇 或特征子集選擇 尤其是聚類分析算法在處理 高維數(shù)據(jù)集時(shí) 屬性子集選擇方法通常需要從給定的屬性集中選取與聚類分析最 相關(guān)的屬性子集 這是由于隨著維度的增加 數(shù)據(jù)的分布日趨稀疏 而只有少數(shù) 的維會(huì)影響最終簇的形成 但是其它不相關(guān)的維的數(shù)據(jù)可能會(huì)以噪聲數(shù)據(jù)的形式 影響真實(shí)的簇 數(shù)據(jù)預(yù)處理不必是聚類分析過(guò)程的必需步驟 但是數(shù)據(jù)預(yù)處理有 助于提高聚類分析的結(jié)果質(zhì)量 6 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 2 1 2 定義相似度度量 相似度定義過(guò)程主要是定義數(shù)據(jù)對(duì)象之間的相似度度量指標(biāo) 常見(jiàn)的度量數(shù) 據(jù)對(duì)象之間相似度的方法是計(jì)算數(shù)據(jù)對(duì)象之間的距離 距離越短 數(shù)據(jù)對(duì)象越相 似 目前 出現(xiàn)了一些新的度量對(duì)象之間相似度的指標(biāo) 具體介紹如下 1 隨著圖在復(fù)雜結(jié)構(gòu)建模中的廣泛應(yīng)用 圖挖掘已經(jīng)變?yōu)閿?shù)據(jù)挖掘中一 個(gè)重要和活躍的課題 其包括頻繁子圖挖掘 頻繁結(jié)構(gòu)模式 圖分類 圖聚類等 在基于圖的聚類中 結(jié)點(diǎn)是對(duì)象 結(jié)點(diǎn)之間的邊表示對(duì)象之間的聯(lián)系 簇被定義 為連通分支 c o n n e c t e dc o m p o n e n t 即簇中的對(duì)象互相連通 而不同簇中的對(duì) 象之間不連通 2 在基于網(wǎng)格的聚類算法中 鰣d b a s e dc l u s t e r i n g 我們將數(shù)據(jù)空間量 化為有窮數(shù)目的網(wǎng)格 所有的聚類分析操作都在網(wǎng)格集合上進(jìn)行 網(wǎng)格信息中通 常保存了網(wǎng)格的密度值 即網(wǎng)格中包含的數(shù)據(jù)點(diǎn)的數(shù)目 網(wǎng)格c 和網(wǎng)格c 是相 似的 記作s i m i l a r c i c 則它們滿足式2 1 所示的條件 型絲墮嬲 卿d q n e i g h b o u f s e 2 n e l 2 h o o u r s 1 l 一 夠 a n qcj l m a x c f d e n s i t y c d e n s i t y 一7 3 在s n n s h a r e dn e a r e s tn e i g h b o r s 算法中 針對(duì)基于密度的聚類分析 算法對(duì)不同密度簇的識(shí)別能力差的問(wèn)題 提出了s n n 相似度度量 該度量首先 計(jì)算每個(gè)數(shù)據(jù)對(duì)象的k 個(gè)最近鄰居 然后將對(duì)象之間的相似度定義為共享近鄰數(shù) 目 對(duì)于數(shù)據(jù)點(diǎn) 和工 它們之間相似度s f 施腸h 鈔 薯 x j 的計(jì)算公式如式2 2 所 示 如果誓和x 相互在對(duì)方的k 近鄰中 貝 1 s i m i l a r i t y x i x 之間的相似度被定義 為它們共享近鄰的數(shù)目 否則 相似度被定義為0 s n n 相似度較好考慮了對(duì)象 周圍區(qū)域數(shù)據(jù)的分布情況 提高了聚類分析算法對(duì)不同密度簇的識(shí)別能力 共享 最近鄰聚類算法為了計(jì)算每個(gè)數(shù)據(jù)對(duì)象的k 個(gè)最近鄰居 其必須計(jì)算任意兩個(gè)數(shù) 據(jù)對(duì)象的距離 因此 在一般情況下 該聚類算法的時(shí)間復(fù)雜度是o n 2 在特 殊情況下 例如在處理低維數(shù)據(jù)時(shí) 如果使用索引技術(shù) 如基于區(qū)域劃分的r 樹 可以將查找k 最近鄰的時(shí)間復(fù)雜度降低到o n l o g 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 t f x k n e a r e s t n e i g h b o r x j a n dx j k n e a r e s t n e i g h b o r x i t h e ns i m i l a r i t y x i x f k n e a r e s t n e i g h b o r x j nk n e a r e s t n e i g h b o r x i 2 2 e l s es i m i l a r i g y x i x 0 通常情況下 數(shù)據(jù)對(duì)象之間的相似度可以通過(guò)相似度矩陣 s i m i l a r i t ym a t r i x 給出 如式2 3 所示 該結(jié)構(gòu)是一個(gè) x t 矩陣 矗 表示對(duì)象i 和對(duì)象 之間的相 似度 d r o 對(duì)象f 和對(duì)象 j 越相似 以的取值越大 2 1 3 聚類 0 吐 d 2 10 d 2 以 以 0 2 3 在數(shù)據(jù)預(yù)處理和定義相似度度量之后 就可以進(jìn)入聚類處理階段 典型的聚 類分析算法可以劃分為三種常見(jiàn)類型 1 以目標(biāo)函數(shù)最優(yōu)化為原則 將數(shù)據(jù)對(duì)象進(jìn)行分組 如基于劃分的方法 和基于模型的方法 大部分都以優(yōu)化目標(biāo)函數(shù)為準(zhǔn)則 將數(shù)據(jù)對(duì)象劃分到不同的 簇中 2 根據(jù)簇的特性將對(duì)象分組 如在基于密度的簇中 簇被定義為最大的 密度相連 d e n s i t y c o n n e c t e d 對(duì)象的集合 在基于網(wǎng)格的聚類分析算法中 簇 被定義為最大的密度連通網(wǎng)格形成的集合 在s n n 算法中 基于對(duì)象的k 最近 鄰計(jì)算 如果對(duì)象置和z 相互在對(duì)方的k 最近鄰中 并且共享近鄰數(shù)目大于閾 值力 則將它們劃分在同一個(gè)簇中 3 依據(jù)簇之間的相似性將對(duì)象分組 如在凝聚層次聚類算法中 初始時(shí) 將每個(gè)數(shù)據(jù)對(duì)象都視為一個(gè)子簇 然后根據(jù)簇之間的相似度合并這些子簇 直到 用戶指定的條件滿足 例如簇的數(shù)目達(dá)到了用戶規(guī)定的簇?cái)?shù)目 2 1 4 聚類結(jié)果輸出 聚類結(jié)果輸出是將代表最終簇的對(duì)象以某種方式輸出 常見(jiàn)的輸出方式包括 輸出簇中包含的數(shù)據(jù)點(diǎn)對(duì)象 輸出能夠反映簇特征的代表性數(shù)據(jù)點(diǎn) 以簇特征的 8 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 形式輸出簇結(jié)果 如式2 4 所示 利用x 和 的取值范圍來(lái)描述簇e 輸出簇 中包含的網(wǎng)格集合 如式2 5 所示 簇e 由網(wǎng)格q o l 2 露 構(gòu)成 輸出簇的 中心點(diǎn) 如在處理城市規(guī)劃的選址問(wèn)題時(shí) 通常將該問(wèn)題抽象為一個(gè)基于約束的 聚類問(wèn)題來(lái)解決 此種聚類問(wèn)題最終的輸出結(jié)果是簇的中心點(diǎn) 這代表了最佳的 選擇地點(diǎn) c 薯 x x j y y 以 2 4 e g 1 g 2 g g 2 5 2 1 5 聚類結(jié)果解釋 在獲得聚類分析形成的簇結(jié)果后 對(duì)聚類結(jié)果的解釋也是聚類分析的一個(gè)重 要步驟 通過(guò)對(duì)結(jié)果的解釋 可以發(fā)現(xiàn)實(shí)際問(wèn)題中隱藏的潛在有用的模式 例如 對(duì)超市購(gòu)物人群的特征進(jìn)行聚類分析 可以將顧客分為若干個(gè)目標(biāo)顧客群 通過(guò) 對(duì)各個(gè)群體的特征進(jìn)行分析 可以為他們制定適當(dāng)?shù)臓I(yíng)銷策略 針對(duì)高維數(shù)據(jù)集 的處理 部分聚類分析算法采用了屬性子集選擇和維度規(guī)約方法 這些方法一方 面降低了數(shù)據(jù)集的維數(shù) 為聚類分析算法得到高質(zhì)量的聚類結(jié)果提供了保證 另 一方面也給聚類結(jié)果的解釋帶來(lái)了挑戰(zhàn) 針對(duì)海量數(shù)據(jù)集的處理 某些聚類分析 算法利用統(tǒng)計(jì)學(xué)中的抽樣 s a m p l i n g 技術(shù)選取了數(shù)據(jù)集中的部分樣本數(shù)據(jù) 這 樣極大地減少了要處理的數(shù)據(jù)集的規(guī)模 此種方法在提高算法效率的同時(shí)也為結(jié) 果的解釋帶來(lái)了困難 當(dāng)數(shù)據(jù)集的維數(shù)較高時(shí) d 3 聚類結(jié)果的可視化顯示 也是一個(gè)問(wèn)題 目前 常見(jiàn)的可視化顯示技術(shù)是空間變換技術(shù) 該技術(shù)利用降維 的方法將高維空問(wèn)中的數(shù)據(jù)變換到低維空間中顯示 但要達(dá)到無(wú)損變換也是一個(gè) 難點(diǎn) 2 2 聚類分析算法的要求及挑戰(zhàn) 隨著聚類分析算法理論的廣泛研究 其應(yīng)用領(lǐng)域也越來(lái)越廣泛 各種應(yīng)用都 對(duì)聚類分析算法提出了特定的要求 本節(jié)將從聚類分析算法處理的數(shù)據(jù)所擁有的 數(shù)據(jù)特性 簇特性以及聚類本身的限制條件三個(gè)方面束討論聚類分析算法所面臨 的一些要求 從數(shù)據(jù)特性的角度分析 聚類分析算法的要求包括處理不同類型的 9 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 數(shù)據(jù) 剔除噪聲 支持對(duì)高維數(shù)據(jù)集的聚類 從簇特性的角度來(lái)看 聚類分析算 法的要求主要是能夠處理任意形狀的簇 從聚類分析算法本身的限制條件來(lái)看 聚類分析算法的要求包括輸入?yún)?shù)少 可伸縮性 增量聚類 支持基于約束的聚 類 1 能夠處理不同類型的數(shù)據(jù) 聚類分析算法必須具有處理不同數(shù)據(jù)類型 的能力 許多聚類分析算法只能夠處理數(shù)值類型的數(shù)據(jù) 一個(gè)好的聚類分析算法 應(yīng)該能夠處理多種類型的數(shù)據(jù) 如分類變量 二元變量 序數(shù)變量以及比例標(biāo)度 的變量等 2 剔除噪聲 許多數(shù)據(jù)集中常常包含噪聲數(shù)據(jù) 如果不能合理地處理這 些噪聲數(shù)據(jù) 將會(huì)嚴(yán)重影響聚類算法的效率及聚類結(jié)果質(zhì)量 如基于劃分的 k m e a n s 算法 1 對(duì)噪聲或孤立點(diǎn)數(shù)據(jù)就比較敏感 它們將減緩簇均值的收斂速 度 增加了算法的時(shí)間復(fù)雜度 而對(duì)于基于密度的d b s c a n 8 算法 其需要兩 個(gè)輸入?yún)?shù)占和m i n p t s s 表示鄰域半徑 m i n p t s 表示s 半徑內(nèi)包含的最小數(shù)據(jù) 點(diǎn)數(shù)目 在聚類的過(guò)程中 為了確定核心對(duì)象 c o r eo b j e c t 其需要計(jì)算每個(gè) 對(duì)象的s 鄰域內(nèi)包含的數(shù)據(jù)點(diǎn)的數(shù)目t o t a lp t s 如果t o t a lp t s 小于m i n p t s 則 將該對(duì)象視為噪聲數(shù)據(jù)點(diǎn)進(jìn)行處理 形式化的描述如式2 6 所示 在基于網(wǎng)格的 聚類分析算法c l i q u e 1 1 q b 需要計(jì)算網(wǎng)格中包含的數(shù)據(jù)點(diǎn)的數(shù)目c o u n t s 如 果c o u n t s 的值小于輸入?yún)?shù)m i n p t s m i n p t s 表示網(wǎng)格中包含的數(shù)據(jù)點(diǎn)的最少數(shù) 目 則將該網(wǎng)格定義為稀疏網(wǎng)格 這樣也很好地剔除了噪聲的影響 形式化的 描述如式2 7 所示 其中c i 表示尹網(wǎng)格 l j j l 2 d 表示網(wǎng)格c f 在 琺維的 索引 t 表示k 曲個(gè)數(shù)據(jù)點(diǎn) 幻勉 一p t s x j 2l 誓i 蕾 占一r a d i u s i 2 6 i ft o t a l p t s x j m i n p t s t h e n x j i sn o i s e o ro u t l i e r s u p p o s ec 厶 厶 c o u n t s c i l 吒i x k i x k 2 厶 l i 2 7 i fc o u n t s c i m i n p t s t h e nci ss p a r s e 鰣d 3 支持對(duì)高維數(shù)據(jù)集的聚類 在高維數(shù)據(jù)集中 通過(guò)傳統(tǒng)的歐幾旱得距 離來(lái)度量對(duì)象之間的相似度變得不再可行 這是因?yàn)?隨著數(shù)據(jù)集維度的迅速增 長(zhǎng) 數(shù)據(jù)點(diǎn)的分布越來(lái)越稀疏 對(duì)象之i 習(xí)j 的歐幾里得距離趨于一致 面對(duì)這種困 難 可以采取兩種方法來(lái)解決這些問(wèn)題 一種方法是采用屬性子集選擇或維規(guī)約 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 技術(shù) 降低數(shù)據(jù)集的維度 另一種方法是定義新的相似度度量指標(biāo) 如s n n 算 法中的共享k 最近鄰等 4 能夠處理任意形狀的簇 簇的形狀可以是球形的 矩形的 橢圓形的 甚至是任意形狀的 一個(gè)好的聚類分析算法應(yīng)該能夠處理任意形狀的簇 基于劃 分的k m e a n s 算法和基于層次的b i r c h 算法都只能處理球形的簇 真正能夠處 理任意形狀簇的算法是基于密度的d b s c a n 算法 該算法不再考慮使某個(gè)目標(biāo) 函數(shù)達(dá)到最優(yōu)值 而是將簇定義為由密度連通數(shù)據(jù)點(diǎn)構(gòu)成的最大集合 簇的形成 是基于數(shù)據(jù)點(diǎn)之間的密度可達(dá)性來(lái)定義的 由于較好地考慮了數(shù)據(jù)點(diǎn)之間的關(guān)系 因此 d b s c a n 可以發(fā)現(xiàn)數(shù)據(jù)集中包含的最自然的簇 其它的能夠處理任意形 狀的簇的算法包括c h a m e l e o n 和c u r e 5 輸入?yún)?shù)少 聚類分析算法通常要求用戶輸入聚類參數(shù) 如k m e a n s 算法需要用戶輸入期望的簇的個(gè)數(shù)k d b s c a n 算法需要輸入占和m i n p t s s 表 示鄰域半徑 m i n p t s 表示g 半徑內(nèi)包含的最少數(shù)據(jù)點(diǎn)數(shù)目 c l i q u e 算法需要 輸入網(wǎng)格的間隔長(zhǎng)度 以及網(wǎng)格中包含的最少數(shù)據(jù)點(diǎn)的個(gè)數(shù)m i n p t s 這些參數(shù)的 確定對(duì)用戶來(lái)說(shuō)是困難的 此外 聚類分析算法易受參數(shù)影響 參數(shù)的差異將影 響聚類效率及聚類結(jié)果質(zhì)量 例如對(duì)于d b s c a n 算法而言 當(dāng)數(shù)據(jù)集中包含的 簇的密度不同時(shí) 使用全局的閾值參數(shù)占和m i n p t s 在低密度區(qū)域 對(duì)象的占鄰 域內(nèi)包含的數(shù)據(jù)點(diǎn)將可能小于m i n p t s 此時(shí) d b s c a n 算法將會(huì)將這些數(shù)據(jù)點(diǎn) 誤判為噪聲 從而不能得到理想的聚類結(jié)果 因此 為了將參數(shù)對(duì)聚類算法的影 響程度降到最低 理想的方法應(yīng)該是根據(jù)數(shù)據(jù)的分布特征自適應(yīng)地設(shè)置關(guān)鍵參數(shù) 6 可伸縮性 聚類分析經(jīng)常要處理大型的數(shù)據(jù)集 而許多聚類分析算法 僅僅適合處理中小規(guī)模的數(shù)據(jù)集 如對(duì)d b s c a n 算法而言 為了確定對(duì)象x i 的占 鄰域內(nèi)包含的數(shù)據(jù)點(diǎn)數(shù)目 必須首先計(jì)算出對(duì)象x i 到任意數(shù)據(jù)對(duì)象 x 歹 l 2 刀 之i 日j 的距離 因此 d b s c a n 算法的時(shí)間復(fù)雜度和空間復(fù)雜度都 為o n 2 特殊地 當(dāng)建立了基于區(qū)域查詢的r 樹索引時(shí) 其時(shí)間復(fù)雜度將降低 到o nl o g 而對(duì)基于網(wǎng)格的聚類算法而言 其將數(shù)據(jù)空間量化為有窮數(shù)目的網(wǎng) 格 所有的聚類分析操作都在網(wǎng)格上進(jìn)行 將數(shù)據(jù)對(duì)象指派到指定的網(wǎng)格并計(jì)算 網(wǎng)格的密度所需的時(shí)間復(fù)雜度是o m m 是數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的數(shù)目 如果為鄰 居網(wǎng)格的查找建立了空間索引結(jié)構(gòu) 如s p t r e e 樹 則算法總的復(fù)雜度是 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 o m l o g 在聚類分析算法處理大型數(shù)據(jù)集時(shí) 算法時(shí)間復(fù)雜度為o 1 0 9 是合 適的 而o n 2 的時(shí)間復(fù)雜度就顯的不合實(shí)際 解決聚類分析算法可伸縮性的重 要方法包括數(shù)據(jù)抽樣和劃分等 但是這些方法可能對(duì)最終聚類結(jié)果的精確性產(chǎn)生 一定的影響 在保證聚類結(jié)果質(zhì)量的前提下 可以考慮設(shè)計(jì)并行的聚類分析算法 這將是提高聚類分析算法可伸縮性的一個(gè)重要途徑 7 增量聚類 i n c r e m e n t a lc l u s t e r i n g 增量聚類是指當(dāng)有新的數(shù)據(jù)點(diǎn)到達(dá) 時(shí) 聚類分析方法能夠即時(shí)更新已有的聚類結(jié)構(gòu) 而無(wú)需重新運(yùn)行聚類分析算法 對(duì)于數(shù)據(jù)流聚類分析算法而言 增量聚類這一特性顯的異常重要 數(shù)據(jù)流聚類分 析算法必須對(duì)潛在無(wú)限的數(shù)據(jù)做出即時(shí)的處理 基于網(wǎng)格的聚類分析算法很好地 支持了增量聚類的功能 當(dāng)有新的數(shù)據(jù)點(diǎn)薯到來(lái)時(shí) 只需確定五所屬的網(wǎng)格單元 并更新網(wǎng)格單元的密度c o u n t s c o u n t s 1 即可 這樣實(shí)現(xiàn)了對(duì)新的數(shù)據(jù)點(diǎn)的 快速處理 針對(duì)經(jīng)常有新的數(shù)據(jù)生成的數(shù)據(jù)集而言 在實(shí)際應(yīng)用中 大部分?jǐn)?shù)據(jù) 集都是這種情況 如電信數(shù)據(jù) 網(wǎng)絡(luò)流量數(shù)據(jù) 銀行交易數(shù)據(jù)等 支持增量聚 類功能的聚類分析算法是必需的 因此 研究增量聚類算法也是聚類分析的重要 研究課題 8 基于約束的聚類 在實(shí)際應(yīng)用中 可能需要處理基于約束的聚類分析 根據(jù)約束條件約束的對(duì)象不同 可以將約束條件大體上分為三類 包括特征級(jí) 或 屬性級(jí) 約束 數(shù)據(jù)對(duì)象級(jí)約束和簇級(jí)約束 特征級(jí)約束是對(duì)數(shù)據(jù)集中的屬性施 加的約束條件 如顧客信息構(gòu)成的數(shù)據(jù)集中 規(guī)定顧客的年齡范圍或收入范圍等 數(shù)據(jù)對(duì)象級(jí)約束是指對(duì)數(shù)據(jù)對(duì)象本身或數(shù)據(jù)對(duì)象之間的關(guān)系施加的約束 數(shù)據(jù)對(duì) 象之間的約束常見(jiàn)的有兩種 包括m u s t l i n k 關(guān)系和c a n n o t l i n k 關(guān)系 這些約束 關(guān)系可能來(lái)自于用戶對(duì)最終簇的期望 也可能是通過(guò)一些背景知識(shí)轉(zhuǎn)換而來(lái)的 簇級(jí)約束是對(duì)最終簇的特性施加的約束條件 如規(guī)定每個(gè)簇中包含的數(shù)據(jù)對(duì)象的 數(shù)目等 針對(duì)約束條件的類型不同 對(duì)約束條件的處理方式也不相同 例如在基 于障礙物的聚類分析中 當(dāng)采用基于網(wǎng)格的方法處理此類問(wèn)題時(shí) 針對(duì)數(shù)據(jù)對(duì)象 級(jí)的約束 基于網(wǎng)格的方法經(jīng)常是將障礙物這種實(shí)際的數(shù)據(jù)對(duì)象首先抽象為抽象 的空問(wèn)對(duì)象 如點(diǎn) 線 面等 然后將障礙物形成的網(wǎng)格視為稀疏的網(wǎng)格 從 而達(dá)到處理障礙物的f 1 的 當(dāng)采用基于密度的方法時(shí) 而對(duì)于數(shù)據(jù)對(duì)象之i 日j 的關(guān) 系施加的約束條件 可以在根據(jù)密度可達(dá)概念形成簇的過(guò)程中考慮到約束條件 蘭州大學(xué)碩士學(xué)位論文基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 從而達(dá)到處理數(shù)據(jù)對(duì)象之間約束條件的目的 如何在考慮約束條件的情況下得到 高質(zhì)量的聚類結(jié)果也是聚類分析算法面臨的挑戰(zhàn) 上面具體分析了實(shí)際的應(yīng)用領(lǐng)域?qū)垲惙治鏊惴ㄌ岢龅囊恍┨囟ㄒ?而這 些要求也就為聚類分析算法的設(shè)計(jì)提出了新的挑戰(zhàn) 聚類分析算法面臨的挑戰(zhàn)包 括可伸縮性 包括數(shù)據(jù)規(guī)模的可伸縮性和數(shù)據(jù)維度的可伸縮性 對(duì)多種數(shù)據(jù)類 型的聚類 確定聚類輸入?yún)?shù) 對(duì)多密度數(shù)據(jù)集的聚類 發(fā)現(xiàn)任意形狀的簇 增 量聚類 基于約束的聚類等 目前 聚類分析的研究領(lǐng)域日益廣泛 如數(shù)據(jù)流聚 類分析 文本聚類分析 多媒體數(shù)據(jù)的聚類分析 生物數(shù)據(jù)的聚類分析 時(shí)序數(shù) 據(jù)的聚類分析 對(duì)圖的聚類分析等 這些研究領(lǐng)域給聚類分析技術(shù)提出了更多的 挑戰(zhàn) 如相似度的度量 距離的計(jì)算 在線聚類 數(shù)據(jù)的單次掃描 數(shù)據(jù)對(duì)象索 引結(jié)構(gòu) 數(shù)據(jù)對(duì)象的存儲(chǔ) 結(jié)果的解釋等 2 3 基于網(wǎng)格的聚類分析算法 基于網(wǎng)格的聚類分析算法 g r i d b a s e dc l u s t e r i n ga n a l y s i sa l g o r i t h m 的基本思 想是對(duì)數(shù)據(jù)集的每一個(gè)維進(jìn)行劃分 這樣便可將數(shù)據(jù)空間量化為有窮數(shù)目的互不 重疊的網(wǎng)格 所有的聚類分析操作都在這些網(wǎng)格上進(jìn)行 基于網(wǎng)格的聚類算法的 優(yōu)點(diǎn)是聚類分析算法的時(shí)間復(fù)雜度獨(dú)立于數(shù)據(jù)對(duì)象的數(shù)目 只與網(wǎng)格的數(shù)目有關(guān) 極大地提高了聚類效率 另外 由于使用摘要數(shù)據(jù)結(jié)構(gòu)來(lái)描述網(wǎng)格單元信息 因 此 其也適合增量聚類 基于網(wǎng)格的聚類分析算法的缺點(diǎn)是粗略地將稀疏網(wǎng)格 e c o u n t s r 中的數(shù)據(jù)點(diǎn)處理為噪聲 降低了聚類結(jié)果的精確度 此外 基 于網(wǎng)格的聚類分析算法的聚類結(jié)果過(guò)分地依賴于輸入?yún)?shù)f f 值的選擇對(duì)用戶 來(lái)說(shuō)是困難的 f 值過(guò)小 則可能導(dǎo)致將不同密度的簇合并在一起 f 值過(guò)大 則可能將低密度區(qū)域的數(shù)據(jù)點(diǎn)識(shí)別為噪聲 因此 可行的方法是根據(jù)數(shù)據(jù)的分布 特征自動(dòng)地確定f 在f 值的討4 算方面 可以通過(guò)最大密度網(wǎng)格的密度來(lái)計(jì)算f 也可以在聚類的過(guò)程中采用密度閾值遞減技術(shù)選擇多個(gè)密度閾值f 這種方法將 提高基于網(wǎng)格的聚類分析算法處理多密度數(shù)據(jù)集的能力 通常情況下 基于網(wǎng) 格的聚類分析算法包含3 個(gè)基本的處理步驟 1 劃分網(wǎng)格單元 即對(duì)數(shù)據(jù)空間 的每一維進(jìn)行劃分 形成網(wǎng)格結(jié)構(gòu) 維的劃分策略常見(jiàn)的包括將每一個(gè)維劃分為 等寬的問(wèn)隔 這樣如果每個(gè)維被劃分為m 個(gè)間隔 則整個(gè)數(shù)據(jù)空間將被劃為為m d 蘭州大學(xué)碩士學(xué)位論文 基于網(wǎng)格的并行聚類算法及數(shù)據(jù)流聚類算法研究 個(gè)互不重疊