蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 摘要 聚類分析作為數據挖掘的一個重要任務 具有廣泛的應用領域 這些不同的 應用都對聚類分析算法提出了新的要求 本文提出了基于網格的并行聚類分析算法p g m c l u 該算法的創新點主要 包括 定義了網格緊湊度 網格密度連通 網格特征值 簇密度以及簇相似度的 概念 提出了基于網格單元劃分的數據分區方法 基于網格密度連通概念的局部 聚類方法 以及基于簇相似度度量的局部聚類合并方法 實現了對網格密度閾值 參數m i n p t s 的自適應設置 該算法可以較好地處理高維和海量數據集 并具有識 別不同形狀和密度簇的能力 數據流是指潛在無限的 持續而快速到達的具有時間順序的數據對象的集合 數據流的實時性和潛在無限性 決定了數據流聚類分析算法與傳統的基于靜態數 據的聚類分析算法相比 具有一些新的特性 本文提出了基于網格的數據流聚類分析算法g c s t r e a m 該算法的創新點主 要包括 提出了描述網格單元概要信息的特征向量結構 對s p t r e e 做了改進 提出了基于l i s t 結構的l s p t r e e 空間索引結構 提出了對網格單元信息的指數 衰減策略 以及對噪聲網格單元和過時網格單元的剪枝策略 該算法較好地滿足 了數據流聚類分析的實時性要求 并對內存空間具有動態的適應性 詳細而全面的實驗證明了p g m c l u 和g c s t r e a m 算法的正確性和有效性 因此 這些研究成果具有重要的理論價值和實際意義 關鍵詞 網格 并行 聚類分析 多密度簇 數據流聚類 l s p t r e e 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 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 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 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 原創性聲明 本人鄭重聲明 本人所呈交的學位論文 是在導師的指導下獨立 進行研究所取得的成果 學位論文中凡引用他人已經發表或未發表的 成果 數據 觀點等 均已明確注明出處 除文中已經注明引用的內 容外 不包含任何其他個人或集體已經發表或撰寫過的科研成果 對 本文的研究成果做出重要貢獻的個人和集體 均己在文中以明確方式 標明 本聲明的法律責任由本人承擔 論文作者簽名 犟顯豸塾 日期 關于學位論文使用授權的聲明 本人在導師指導下所完成的論文及相關的職務作品 知識產權歸 屬蘭州大學 本人完全了解蘭州大學有關保存 使用學位論文的規定 同意學校保存或向國家有關部門或機構送交論文的紙質版和電子版 允許論文被查閱和借閱 本人授權蘭州大學可以將本學位論文的全部 或部分內容編入有關數據庫進行檢索 可以采用任何復制手段保存和 匯編本學位論文 本人離校后發表 使用學位論文或與該論文直接相 關的學術論文或成果時 第一署名單位仍然為蘭州大學 保密論文在解密后應遵守此規定 論文作者簽名 甾熟 導師簽名 圜 日期 型 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 1 1 研究背景及意義 第一章緒論 數據挖掘 d a t am i m n g 是指發現數據中蘊含的潛在有用的知識的過程 知 識包括規則 模式及結構等 數據挖掘涉及到多個學科 包括數據庫和數據倉庫 統計學 信息檢索 人工智能 神經網絡 模糊集 粗糙集 信號處理 高性能 計算等 數據挖掘理論的應用領域廣泛 包括圖像處理 生物信息學 氣象信息 分析 社會網絡分析 圖挖掘 入侵檢測 數據流挖掘 時問序列預測等 基本 的數據挖掘技術包括頻繁模式挖掘 分類和預測以及聚類分析 聚類分析 c l u s t e r i n ga n a l y s i s 是一項基本的數據挖掘任務 聚類分析是將 數據對象集合根據對象之間的相似度度量劃分為簇 c l u s t e r 的過程 聚類分析 的基本方法包括 基于劃分的方法 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 基于網 格的方法 鰣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 等 基于網格的方法包括 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 等 除了這些基本的聚類分析方 法之外 目前 聚類分析的熱點研究領域包括基于約束的聚類 數據流聚類 子 空間聚類 增量聚類 基于遺傳算法的聚類 基于蟻群算法的聚類等 基于網格的聚類分析算法是聚類分析中一種非常重要的方法 在聚類高維和 海量數據集時具有明顯的優勢 基于網格的聚類算法將數據空間量化為有窮數目 的網格單元 然后將數據對象投影到這些網格單元中 并保存網格單元的摘要信 息 s u m m a r i z a t i o ni n f o r m a t i o n 所有的聚類操作都在這些網格單元上面進行 不同的基于網格的聚類分析算法在如下方面存在差異 包括網格劃分策略 常見 的包括靜態劃分和動態劃分兩種 網格摘要信息結構 網格單元集合索引結構 噪聲數據的處理和簇的識別機制等 目前 最新的基于網格的聚類分析算法包括 l 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 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 節中詳細分析 基本的基于網格的聚類分析算法的聚類過程的時間復雜 度主要依賴于數據空間中包含的網格單元的數目 具有近似線性的時間復雜度 此外 其還能夠較好地處理高維和海量數據集 在增量聚類和子空間聚類等方面 也體現出優勢 因此 它在聚類分析中得到了廣泛的研究和應用 集群系統 2 7 2 8 1 1 2 9 p c sc l u s t e rs y s t e m 在近年來得到廣泛的應用 集群 系統是將一組高性能的計算機通過特定的網絡結構聯接起來 在操作系統和并行 環境的支撐下 實現對系統資源的統一管理和協調調度 它通過消息傳遞的機制 為程序設計人員提供了一個整體的并行編程環境 基于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 的并行編程技術提高了集群系統環境下并行程序開發的效率 由于集 群系統具有高性能 h i i g hp e r f o r m a n c e 可擴展性 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 等典型特 征 因此 集群系統在大規模數據處理 圖像處理 工程計算等領域得到越來越 廣泛的應用 數據的海量性和高維性都給聚類分析算法帶來了挑戰 而集群系統的這些特 征給研究集群系統下的并行的聚類分析算法帶來了機遇 此外 實際的數據集中 經常包含密度不同的簇 傳統的基于密度的聚類分析算法 如d b s c a n 往往 不能得到準確的聚類結果 而針對多密度數據集的聚類分析算法 如s n n 3 0 3 1 又存在算法時間復雜度高以及聚類結果精度差 主要體現在對噪聲數據的處理方 面 等問題 因此 研究適合于多密度數據集的聚類分析算法也是一個熱門的研 究方向 數據流是指連續且具有時間順序的數據構成的集合 數據流是伴隨著人們對 實時數據的處理而產生的 如電信通話數據 銀行交易數據 證券交易數據 網 絡流量監測數據 網絡操作日志數據 氣象監測數據 傳感器數據等 3 2 3 3 3 4 3 5 數據流具有連續性 按時間順序的 潛在無限的 快速變化的 等特性 這些特性給數據流聚類分析算法帶來了挑戰 與傳統的基于靜態數據的 聚類分析算法相比 數據流聚類分析算法具有三個明顯的特性 1 它強調時間 性 數據流聚類分析算法必須能夠發現數據流的演變規律或任意時問段內的數據 流聚類結果 2 單遍掃描 由于受到內存空i 日j 的限制和數據流聚類分析算法實 2 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 時性的要求 數據流聚類分析算法必須實現對數據對象的單遍掃描 3 強調對 摘要數據結構 s u m m a r yd a t as t r u c t u r e 的設計 數據流聚類分析算法必須將數 據對象的信息以摘要數據結構的形式保存起來 以方便聚類算法對摘要結構的分 析 目前 典型的數據流聚類分析算法包括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 等 針對數據流聚類分析算法的這 些新的特性 數據流聚類分析算法已經變成數據挖掘中的一個研究熱點 1 2 研究內容 本文針對當前聚類分析算法存在的問題 結合最新的研究成果 主要開展了 對基于網格的并行的聚類分析算法和基于網格的數據流聚類分析算法的研究 具 體的研究內容包括 1 維災難 d i m e n s i o nc u r s e 問題已經成為聚類分析算法處理高維數據 集時的一個主要問題 同時 許多聚類分析算法 如d b s c a n s n n 等 在處 理海量數據集時也面臨高的時問復雜度 如o n 2 其中 是數據對象的數目 的困擾 此外 針對多密度數據集的聚類分析算法存在時間復雜度高及聚類結果 精確度不高 主要表現在對噪聲數據的處理方面 等問題 本文針對這些問題 提出了基于網格的并行的聚類分析算法 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 簡稱p g m c l u p g m c l u 算法基于數據并 行 d a t ap a r a l l e l i s m 的思想 這是一種典型的分而治之的方法 通過各個節點 對數據的獨立聚類和最終聚類結果的合并實現了對整個數據集的聚類 p g m c l u 算法提出了網格緊湊度 網格密度直接可達 網格密度可達 網格密 度連通等概念 其中網格緊湊度 g r i dc o m p a c t n e s s 度量較好地反映了網格中數 據點之間的緊密程度 提出了新的網格劃分方法 以及基于參考維的數據分區策 略 實現了根據數據的分布特征自動確定m i n p t s 參數的值 為了更好地適應分而 治之的策略 提出了利用網格特征向量來描述網格的摘要信息結構 并建立了 s p t r e e 提高鄰居網格的查找效率 提出了基于網格密度連通概念的聚類方法 以及識別邊界網格中邊界數據點的方法 提出了簇密度和簇相似性的概念 并且 基于它們提出了簇合并算法 最后 對該算法進行了性能分析和實驗驗證 2 針對如何設計有效的能夠對連續的數據流進行快速處理 并能發現數 蘭州大學碩士學位論文 基于網格的并行聚類算法及數據流聚類算法研究 據流的演變規律的要求 本文提出了基于網格的數據流聚類分析算法 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 簡稱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 來發現數據流的演變規律 g c s t r e a m 算法提出了新的聚類模型l s p t r e e 提出了聚類模型維護策略以及聚 類模型的剪枝策略 較好地實現了模型對數據對象的快速處理 以及適應了數據 流聚類分析算法對內存空間的限制要求 最后 通過實驗驗證和評價了算法的正 確性和性能 1 3 論文組織結構 本文圍繞著基于網格的聚類分析算法的研究與實現 從并行化基于網格的聚 類分析算法和設計基于網格的數據流聚類分析算法兩個方面 開展了研究工作 論文內容按照以下結構組織 第一章 緒論 主要介紹了課題研究的背景 意義 內容及論文組織結構 引出了論文的主要研究內容為基于網格的并行的聚類分析算法以及基于網格的 數據流聚類分析算法 第二章 基于網格的聚類分析算法概述 首先 介紹了聚類分析的概念及過 程 對聚類分析過程的每個步驟中涉及到的關鍵技術進行了詳細的闡釋 其次 分析了不同的應用對聚類分析算法提出的特定要求 并給出了聚類分析算法面臨 的挑戰 最后 闡釋了基于網格的聚類分析算法的基本原理及特點 并詳細分析 了四種典型的基于網格的聚類分析算法的原理及特性 包括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 算法 第三章 并行的基于網格的聚類分析算法 p g m c l u 首先 描述了p g m c l u 算法的總體框架 對算法中涉及到的幾個重要的過程進行了闡釋 其次 介紹了 算法中涉及到的基本概念 然后 詳細描述了算法的實現過程 包括數據分區 構建s p t r e e 局部聚類和局部聚類合并這四個關鍵的步驟 對步驟中涉及到的 關鍵技術進行了具體闡釋 接下來 從時i 日j 復雜度和加速比方面分析了算法的性 能 最后 從聚類準確性 相對加速比以及效率三個方面對算法進行了實驗驗證 和性能評價 第四章 基于網格的數據流聚類分析算法g c s t r e a m 首先 介紹了數據流 4 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 的概念 以及數據流聚類分析的特性 窗口模型及典型算法 其次 描述了算法 的總體框架 然后 從聚類模型 模型維護 更新和剪枝策略方面對算法進行了 詳細的描述 最后 分析算法性能并給出實驗驗證和性能評價 第五章 總結與展望 總結本文的研究工作 并展望未來的研究方向 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 第二章基于網格的聚類分析算法概述 2 1 聚類分析概念及過程 聚類分析 c l u s t e r i n ga n a l y s i s 是數據挖掘 d a t am i n i n g 技術的重要一種 相對于分類算法而言 聚類分析算法事先不知道類的標號 因此 其也被稱為無 監督的學習 u n s u p e r v i s e dl e a r n i n g 聚類分析指的是將對象集合根據對象之間 的相似度度量劃分為不同的簇 c l u s t e r 的過程 對象之間的相似度通常通過計 算它們之問的距離來度量 距離的計算方式因聚類分析處理的數據類型的不同而 異 聚類分析源于統計學 數據挖掘 生物學以及機器學習等多個領域 目前 聚類分析已被廣泛地應用于信息檢索 圖像處理 模式識別 w e b 信息處理 市 場調研 地理學 醫學 生物信息學 空間數據分析等多個方面 一個有實際價 值的聚類分析算法通常包括5 個關鍵的處理步驟 數據預處理 相似度定義 聚 類 聚類結果輸出 聚類結果解釋 2 1 1 數據預處理 數據預處理主要包括數據清理 數據變換和數據規約功能 數據清理包括補 充缺失值 光滑數據 剔除噪聲數據等 數據變換將數據轉換成適合于聚類分析 的形式 數據變換通常包括光滑 聚集 數據泛化 規范化和屬性構造 數據規 約是在保持原數據集的完整性的同時得到數據集的規約表示 聚類分析中經常用 到的規約方法是屬性子集選擇 或特征子集選擇 尤其是聚類分析算法在處理 高維數據集時 屬性子集選擇方法通常需要從給定的屬性集中選取與聚類分析最 相關的屬性子集 這是由于隨著維度的增加 數據的分布日趨稀疏 而只有少數 的維會影響最終簇的形成 但是其它不相關的維的數據可能會以噪聲數據的形式 影響真實的簇 數據預處理不必是聚類分析過程的必需步驟 但是數據預處理有 助于提高聚類分析的結果質量 6 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 2 1 2 定義相似度度量 相似度定義過程主要是定義數據對象之間的相似度度量指標 常見的度量數 據對象之間相似度的方法是計算數據對象之間的距離 距離越短 數據對象越相 似 目前 出現了一些新的度量對象之間相似度的指標 具體介紹如下 1 隨著圖在復雜結構建模中的廣泛應用 圖挖掘已經變為數據挖掘中一 個重要和活躍的課題 其包括頻繁子圖挖掘 頻繁結構模式 圖分類 圖聚類等 在基于圖的聚類中 結點是對象 結點之間的邊表示對象之間的聯系 簇被定義 為連通分支 c o n n e c t e dc o m p o n e n t 即簇中的對象互相連通 而不同簇中的對 象之間不連通 2 在基于網格的聚類算法中 鰣d b a s e dc l u s t e r i n g 我們將數據空間量 化為有窮數目的網格 所有的聚類分析操作都在網格集合上進行 網格信息中通 常保存了網格的密度值 即網格中包含的數據點的數目 網格c 和網格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 算法中 針對基于密度的聚類分析 算法對不同密度簇的識別能力差的問題 提出了s n n 相似度度量 該度量首先 計算每個數據對象的k 個最近鄰居 然后將對象之間的相似度定義為共享近鄰數 目 對于數據點 和工 它們之間相似度s f 施腸h 鈔 薯 x j 的計算公式如式2 2 所 示 如果誓和x 相互在對方的k 近鄰中 貝 1 s i m i l a r i t y x i x 之間的相似度被定義 為它們共享近鄰的數目 否則 相似度被定義為0 s n n 相似度較好考慮了對象 周圍區域數據的分布情況 提高了聚類分析算法對不同密度簇的識別能力 共享 最近鄰聚類算法為了計算每個數據對象的k 個最近鄰居 其必須計算任意兩個數 據對象的距離 因此 在一般情況下 該聚類算法的時間復雜度是o n 2 在特 殊情況下 例如在處理低維數據時 如果使用索引技術 如基于區域劃分的r 樹 可以將查找k 最近鄰的時間復雜度降低到o n l o g 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 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 通常情況下 數據對象之間的相似度可以通過相似度矩陣 s i m i l a r i t ym a t r i x 給出 如式2 3 所示 該結構是一個 x t 矩陣 矗 表示對象i 和對象 之間的相 似度 d r o 對象f 和對象 j 越相似 以的取值越大 2 1 3 聚類 0 吐 d 2 10 d 2 以 以 0 2 3 在數據預處理和定義相似度度量之后 就可以進入聚類處理階段 典型的聚 類分析算法可以劃分為三種常見類型 1 以目標函數最優化為原則 將數據對象進行分組 如基于劃分的方法 和基于模型的方法 大部分都以優化目標函數為準則 將數據對象劃分到不同的 簇中 2 根據簇的特性將對象分組 如在基于密度的簇中 簇被定義為最大的 密度相連 d e n s i t y c o n n e c t e d 對象的集合 在基于網格的聚類分析算法中 簇 被定義為最大的密度連通網格形成的集合 在s n n 算法中 基于對象的k 最近 鄰計算 如果對象置和z 相互在對方的k 最近鄰中 并且共享近鄰數目大于閾 值力 則將它們劃分在同一個簇中 3 依據簇之間的相似性將對象分組 如在凝聚層次聚類算法中 初始時 將每個數據對象都視為一個子簇 然后根據簇之間的相似度合并這些子簇 直到 用戶指定的條件滿足 例如簇的數目達到了用戶規定的簇數目 2 1 4 聚類結果輸出 聚類結果輸出是將代表最終簇的對象以某種方式輸出 常見的輸出方式包括 輸出簇中包含的數據點對象 輸出能夠反映簇特征的代表性數據點 以簇特征的 8 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 形式輸出簇結果 如式2 4 所示 利用x 和 的取值范圍來描述簇e 輸出簇 中包含的網格集合 如式2 5 所示 簇e 由網格q o l 2 露 構成 輸出簇的 中心點 如在處理城市規劃的選址問題時 通常將該問題抽象為一個基于約束的 聚類問題來解決 此種聚類問題最終的輸出結果是簇的中心點 這代表了最佳的 選擇地點 c 薯 x x j y y 以 2 4 e g 1 g 2 g g 2 5 2 1 5 聚類結果解釋 在獲得聚類分析形成的簇結果后 對聚類結果的解釋也是聚類分析的一個重 要步驟 通過對結果的解釋 可以發現實際問題中隱藏的潛在有用的模式 例如 對超市購物人群的特征進行聚類分析 可以將顧客分為若干個目標顧客群 通過 對各個群體的特征進行分析 可以為他們制定適當的營銷策略 針對高維數據集 的處理 部分聚類分析算法采用了屬性子集選擇和維度規約方法 這些方法一方 面降低了數據集的維數 為聚類分析算法得到高質量的聚類結果提供了保證 另 一方面也給聚類結果的解釋帶來了挑戰 針對海量數據集的處理 某些聚類分析 算法利用統計學中的抽樣 s a m p l i n g 技術選取了數據集中的部分樣本數據 這 樣極大地減少了要處理的數據集的規模 此種方法在提高算法效率的同時也為結 果的解釋帶來了困難 當數據集的維數較高時 d 3 聚類結果的可視化顯示 也是一個問題 目前 常見的可視化顯示技術是空間變換技術 該技術利用降維 的方法將高維空問中的數據變換到低維空間中顯示 但要達到無損變換也是一個 難點 2 2 聚類分析算法的要求及挑戰 隨著聚類分析算法理論的廣泛研究 其應用領域也越來越廣泛 各種應用都 對聚類分析算法提出了特定的要求 本節將從聚類分析算法處理的數據所擁有的 數據特性 簇特性以及聚類本身的限制條件三個方面束討論聚類分析算法所面臨 的一些要求 從數據特性的角度分析 聚類分析算法的要求包括處理不同類型的 9 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 數據 剔除噪聲 支持對高維數據集的聚類 從簇特性的角度來看 聚類分析算 法的要求主要是能夠處理任意形狀的簇 從聚類分析算法本身的限制條件來看 聚類分析算法的要求包括輸入參數少 可伸縮性 增量聚類 支持基于約束的聚 類 1 能夠處理不同類型的數據 聚類分析算法必須具有處理不同數據類型 的能力 許多聚類分析算法只能夠處理數值類型的數據 一個好的聚類分析算法 應該能夠處理多種類型的數據 如分類變量 二元變量 序數變量以及比例標度 的變量等 2 剔除噪聲 許多數據集中常常包含噪聲數據 如果不能合理地處理這 些噪聲數據 將會嚴重影響聚類算法的效率及聚類結果質量 如基于劃分的 k m e a n s 算法 1 對噪聲或孤立點數據就比較敏感 它們將減緩簇均值的收斂速 度 增加了算法的時間復雜度 而對于基于密度的d b s c a n 8 算法 其需要兩 個輸入參數占和m i n p t s s 表示鄰域半徑 m i n p t s 表示s 半徑內包含的最小數據 點數目 在聚類的過程中 為了確定核心對象 c o r eo b j e c t 其需要計算每個 對象的s 鄰域內包含的數據點的數目t o t a lp t s 如果t o t a lp t s 小于m i n p t s 則 將該對象視為噪聲數據點進行處理 形式化的描述如式2 6 所示 在基于網格的 聚類分析算法c l i q u e 1 1 q b 需要計算網格中包含的數據點的數目c o u n t s 如 果c o u n t s 的值小于輸入參數m i n p t s m i n p t s 表示網格中包含的數據點的最少數 目 則將該網格定義為稀疏網格 這樣也很好地剔除了噪聲的影響 形式化的 描述如式2 7 所示 其中c i 表示尹網格 l j j l 2 d 表示網格c f 在 琺維的 索引 t 表示k 曲個數據點 幻勉 一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 支持對高維數據集的聚類 在高維數據集中 通過傳統的歐幾旱得距 離來度量對象之間的相似度變得不再可行 這是因為 隨著數據集維度的迅速增 長 數據點的分布越來越稀疏 對象之i 習j 的歐幾里得距離趨于一致 面對這種困 難 可以采取兩種方法來解決這些問題 一種方法是采用屬性子集選擇或維規約 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 技術 降低數據集的維度 另一種方法是定義新的相似度度量指標 如s n n 算 法中的共享k 最近鄰等 4 能夠處理任意形狀的簇 簇的形狀可以是球形的 矩形的 橢圓形的 甚至是任意形狀的 一個好的聚類分析算法應該能夠處理任意形狀的簇 基于劃 分的k m e a n s 算法和基于層次的b i r c h 算法都只能處理球形的簇 真正能夠處 理任意形狀簇的算法是基于密度的d b s c a n 算法 該算法不再考慮使某個目標 函數達到最優值 而是將簇定義為由密度連通數據點構成的最大集合 簇的形成 是基于數據點之間的密度可達性來定義的 由于較好地考慮了數據點之間的關系 因此 d b s c a n 可以發現數據集中包含的最自然的簇 其它的能夠處理任意形 狀的簇的算法包括c h a m e l e o n 和c u r e 5 輸入參數少 聚類分析算法通常要求用戶輸入聚類參數 如k m e a n s 算法需要用戶輸入期望的簇的個數k d b s c a n 算法需要輸入占和m i n p t s s 表 示鄰域半徑 m i n p t s 表示g 半徑內包含的最少數據點數目 c l i q u e 算法需要 輸入網格的間隔長度 以及網格中包含的最少數據點的個數m i n p t s 這些參數的 確定對用戶來說是困難的 此外 聚類分析算法易受參數影響 參數的差異將影 響聚類效率及聚類結果質量 例如對于d b s c a n 算法而言 當數據集中包含的 簇的密度不同時 使用全局的閾值參數占和m i n p t s 在低密度區域 對象的占鄰 域內包含的數據點將可能小于m i n p t s 此時 d b s c a n 算法將會將這些數據點 誤判為噪聲 從而不能得到理想的聚類結果 因此 為了將參數對聚類算法的影 響程度降到最低 理想的方法應該是根據數據的分布特征自適應地設置關鍵參數 6 可伸縮性 聚類分析經常要處理大型的數據集 而許多聚類分析算法 僅僅適合處理中小規模的數據集 如對d b s c a n 算法而言 為了確定對象x i 的占 鄰域內包含的數據點數目 必須首先計算出對象x i 到任意數據對象 x 歹 l 2 刀 之i 日j 的距離 因此 d b s c a n 算法的時間復雜度和空間復雜度都 為o n 2 特殊地 當建立了基于區域查詢的r 樹索引時 其時間復雜度將降低 到o nl o g 而對基于網格的聚類算法而言 其將數據空間量化為有窮數目的網 格 所有的聚類分析操作都在網格上進行 將數據對象指派到指定的網格并計算 網格的密度所需的時間復雜度是o m m 是數據集中數據點的數目 如果為鄰 居網格的查找建立了空間索引結構 如s p t r e e 樹 則算法總的復雜度是 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 o m l o g 在聚類分析算法處理大型數據集時 算法時間復雜度為o 1 0 9 是合 適的 而o n 2 的時間復雜度就顯的不合實際 解決聚類分析算法可伸縮性的重 要方法包括數據抽樣和劃分等 但是這些方法可能對最終聚類結果的精確性產生 一定的影響 在保證聚類結果質量的前提下 可以考慮設計并行的聚類分析算法 這將是提高聚類分析算法可伸縮性的一個重要途徑 7 增量聚類 i n c r e m e n t a lc l u s t e r i n g 增量聚類是指當有新的數據點到達 時 聚類分析方法能夠即時更新已有的聚類結構 而無需重新運行聚類分析算法 對于數據流聚類分析算法而言 增量聚類這一特性顯的異常重要 數據流聚類分 析算法必須對潛在無限的數據做出即時的處理 基于網格的聚類分析算法很好地 支持了增量聚類的功能 當有新的數據點薯到來時 只需確定五所屬的網格單元 并更新網格單元的密度c o u n t s c o u n t s 1 即可 這樣實現了對新的數據點的 快速處理 針對經常有新的數據生成的數據集而言 在實際應用中 大部分數據 集都是這種情況 如電信數據 網絡流量數據 銀行交易數據等 支持增量聚 類功能的聚類分析算法是必需的 因此 研究增量聚類算法也是聚類分析的重要 研究課題 8 基于約束的聚類 在實際應用中 可能需要處理基于約束的聚類分析 根據約束條件約束的對象不同 可以將約束條件大體上分為三類 包括特征級 或 屬性級 約束 數據對象級約束和簇級約束 特征級約束是對數據集中的屬性施 加的約束條件 如顧客信息構成的數據集中 規定顧客的年齡范圍或收入范圍等 數據對象級約束是指對數據對象本身或數據對象之間的關系施加的約束 數據對 象之間的約束常見的有兩種 包括m u s t l i n k 關系和c a n n o t l i n k 關系 這些約束 關系可能來自于用戶對最終簇的期望 也可能是通過一些背景知識轉換而來的 簇級約束是對最終簇的特性施加的約束條件 如規定每個簇中包含的數據對象的 數目等 針對約束條件的類型不同 對約束條件的處理方式也不相同 例如在基 于障礙物的聚類分析中 當采用基于網格的方法處理此類問題時 針對數據對象 級的約束 基于網格的方法經常是將障礙物這種實際的數據對象首先抽象為抽象 的空問對象 如點 線 面等 然后將障礙物形成的網格視為稀疏的網格 從 而達到處理障礙物的f 1 的 當采用基于密度的方法時 而對于數據對象之i 日j 的關 系施加的約束條件 可以在根據密度可達概念形成簇的過程中考慮到約束條件 蘭州大學碩士學位論文基于網格的并行聚類算法及數據流聚類算法研究 從而達到處理數據對象之間約束條件的目的 如何在考慮約束條件的情況下得到 高質量的聚類結果也是聚類分析算法面臨的挑戰 上面具體分析了實際的應用領域對聚類分析算法提出的一些特定要求 而這 些要求也就為聚類分析算法的設計提出了新的挑戰 聚類分析算法面臨的挑戰包 括可伸縮性 包括數據規模的可伸縮性和數據維度的可伸縮性 對多種數據類 型的聚類 確定聚類輸入參數 對多密度數據集的聚類 發現任意形狀的簇 增 量聚類 基于約束的聚類等 目前 聚類分析的研究領域日益廣泛 如數據流聚 類分析 文本聚類分析 多媒體數據的聚類分析 生物數據的聚類分析 時序數 據的聚類分析 對圖的聚類分析等 這些研究領域給聚類分析技術提出了更多的 挑戰 如相似度的度量 距離的計算 在線聚類 數據的單次掃描 數據對象索 引結構 數據對象的存儲 結果的解釋等 2 3 基于網格的聚類分析算法 基于網格的聚類分析算法 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 的基本思 想是對數據集的每一個維進行劃分 這樣便可將數據空間量化為有窮數目的互不 重疊的網格 所有的聚類分析操作都在這些網格上進行 基于網格的聚類算法的 優點是聚類分析算法的時間復雜度獨立于數據對象的數目 只與網格的數目有關 極大地提高了聚類效率 另外 由于使用摘要數據結構來描述網格單元信息 因 此 其也適合增量聚類 基于網格的聚類分析算法的缺點是粗略地將稀疏網格 e c o u n t s r 中的數據點處理為噪聲 降低了聚類結果的精確度 此外 基 于網格的聚類分析算法的聚類結果過分地依賴于輸入參數f f 值的選擇對用戶 來說是困難的 f 值過小 則可能導致將不同密度的簇合并在一起 f 值過大 則可能將低密度區域的數據點識別為噪聲 因此 可行的方法是根據數據的分布 特征自動地確定f 在f 值的討4 算方面 可以通過最大密度網格的密度來計算f 也可以在聚類的過程中采用密度閾值遞減技術選擇多個密度閾值f 這種方法將 提高基于網格的聚類分析算法處理多密度數據集的能力 通常情況下 基于網 格的聚類分析算法包含3 個基本的處理步驟 1 劃分網格單元 即對數據空間 的每一維進行劃分 形成網格結構 維的劃分策略常見的包括將每一個維劃分為 等寬的問隔 這樣如果每個維被劃分為m 個間隔 則整個數據空間將被劃為為m d 蘭州大學碩士學位論文 基于網格的并行聚類算法及數據流聚類算法研究 個互不重疊