（計算機軟件與理論專業(yè)論文）基于位運算的閉頻繁項集挖掘算法的研究.pdf

原創(chuàng)性聲明 i i i i i iim i i i i i i i i i i i i i i i i h i 、l18 3 3 6 6 9 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨立進行研 究所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不包含任何其他個人 或集體已經(jīng)發(fā)表或撰寫過的科研成果。對本文的研究作出重要貢獻的個人和集 體，均已在文中以明確方式標(biāo)明。本聲明的法律責(zé)任由本人承擔(dān)。 學(xué)位論文作者：吲寥斌 日期：扣年多月弓日 學(xué)位論文使用授權(quán)聲明 本人在導(dǎo)師指導(dǎo)下完成的論文及相關(guān)的職務(wù)作品，知識產(chǎn)權(quán)歸屬鄭州大學(xué)。 根據(jù)鄭州大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留或向國家有關(guān)部 門或機構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱；本人授權(quán)鄭州 大學(xué)可以將本學(xué)位論文的全部或部分編入有關(guān)數(shù)據(jù)庫進行檢索，可以采用影印、 縮印或者其他復(fù)制手段保存論文和匯編本學(xué)位論文。本人離校后發(fā)表、使用學(xué) 位論文或與該學(xué)位論文直接相關(guān)的學(xué)術(shù)論文或成果時，第一署名單位仍然為鄭 州大學(xué)。保密論文在解密后應(yīng)遵守此規(guī)定。 學(xué)位論文懈锨 嗍卯年籮月；日 摘要 摘要 在信息技術(shù)高度發(fā)達的今天，現(xiàn)實生活和商業(yè)應(yīng)用中積累了大量歷史數(shù)據(jù)， 而且這些數(shù)據(jù)正呈爆炸式增長。海量的歷史數(shù)據(jù)既蘊含著大量寶貴資源，同時 也把我們淹沒在數(shù)據(jù)和信息的汪洋大海里。為了從中找到潛在的、有價值的信 息，數(shù)據(jù)挖掘技術(shù)應(yīng)運而生，并顯示出強大的生命力和巨大的發(fā)展?jié)摿Αｎl繁 模式挖掘在數(shù)據(jù)挖掘任務(wù)中一直充當(dāng)著重要的角色，頻繁模式挖掘是一個相對 耗時的過程，而且可能會產(chǎn)生大量的頻繁模式項，挖掘頻繁閉模式比頻繁模式 數(shù)量上要少，但是卻能表達相同的信息。 頻繁項集挖掘做為關(guān)聯(lián)規(guī)則產(chǎn)生的首要步驟，其挖掘效率的高低直接關(guān)系 著關(guān)聯(lián)規(guī)則產(chǎn)生的總體效率。本文將位處理技術(shù)運用n - - 維閉頻繁項集挖掘和 三維閉頻繁項集挖掘過程中，對數(shù)據(jù)集和項集按位存儲，通過充分利用計算機 每次處理3 2 位數(shù)據(jù)的特性，最大限度的提高每次運算處理數(shù)據(jù)集的數(shù)據(jù)量，從 而提高閉頻繁項集挖掘的效率。 本文在對現(xiàn)有的各種二維頻繁項集挖掘算法和三維頻繁項集挖掘算法優(yōu)缺 點進行分析比較的基礎(chǔ)上，對枚舉策略和剪枝策略進行優(yōu)化，設(shè)計出更加高效 的基于位運算的二維閉頻繁項集挖掘算法b d - m i n e r 和基于位運算的三維閉頻 繁項集挖掘算法b d p e e l e r ，使得算法既繼承了現(xiàn)有算法的優(yōu)點，又能更高效 的完成挖掘任務(wù)。 本文使用v c + + 6 0 實現(xiàn)了算法b d m i n e r 和b d - p e e l e r ，在多個數(shù)據(jù)集上 做了大量實驗，并與現(xiàn)有算法進行了比較，實驗結(jié)果表明：在相同數(shù)據(jù)集上完 成相同約束條件的閉頻繁項集的挖掘任務(wù)，二維數(shù)據(jù)集上b d - m i n e r 算法能提升 挖掘效率6 7 倍，三維數(shù)據(jù)集上b d p e e l e r 算法能提升挖掘效率3 倍。 關(guān)鍵詞：數(shù)據(jù)挖掘閉頻繁項集位運算約束二維三維 a b s t r a c t a b s t r a c t n o w a d a y s ，w i t hh i g h l yd e v e l o p e di n f o r m a t i o nt e c h n o l o g yi ns o c i e t y , al a r g e a r n o u n to fh i s t o r i c a ld a t ah a sa c c u m u l a t e di nt h er e a l 1 i f ea n dc o m m e r c i a l a p p l i c a t i o n s ，a n dt h e s ed a t aa r ei nh i g h l y e x p l o s i v eg r o w t h v a s ta m o u n t so f h i s t o r i c a ld a t ad on o to n l yc o n t a i nal a r g en u m b e ro fv a l u a b l er e s o u r c e s ，b u ta l s o m a k eu ss u b m e r g e di nt h eh u g ew a v eo fd a t aa n di n f o r m a t i o n i no r d e rt of i n do u t p o t e n t i a la n du s e f u lk n o w l e d g ef r o mt h em a s s i v ea m o u n t so fd a t a ，d a t am i n i n g t e c h n o l o g yh a se m e r g e da n ds h o w ss t r o n gv i t a l i t ya n dh u g ep o t e n t i a l i t y f r e q u e n t p a r e r nm i n i n gh a sa l w a y sb e e np l a y i n ga l li m p o r t a n tr o l ei n d a t am i n i n gt a s k s f r e q u e n tp a t t e r nm i n i n gi s at i m e c o n s b m i n gp r o c e s s ，a n dm a yp r o d u c eal a r g e n u m b e ro ff r e q u e n tp a t t e r n s t h e r ei saf r e q u e n tc l o s e dp a t t e r nw h i c hc o n t a i n st h e s a m ei n f o r m a t i o nw i t l ll e s sq u a n t i t yi no u t c o m et h a nf r e q u e n tp a t t e r n f r e q u e n ti t e ms e t sm i n i n gi st h ef i r s ts t e pi nt h eg e n e r a t i o no ft h ea s s o c i a t i o n r u l e s ，s oi t sm i n i n ge f f i c i e n c yi sd i r e c t l yr e l a t e dt ot h ee f f i c i e n c yo fg e n e r a t i o no f a s s o c i a t i o nr u l e s t h i sp a p e rw i l ls t u d yt h et w o - d i m e n s i o n a la n dt h r e e d i m e n s i o n a l c l o s e df r e q u e n ti t e ms e t sw i t hab i t w i s ep r o c e s s i n gt e c h n o l o g y i no r d e rt om a k et h e b e s to ft h ec o m p u t e rp r o c e s s i n g3 2 - b i td a t ae a c ht i m e ，t h ed a t as e t sa n dt h ei t e ms e t s w i l lb es t o r e db yb i t s ，s ot h a ti tc a ni n c r e a s et h ec o m p u t a t i o nf o re a c ht i m ea n d e n h a n c et h ee f f i c i e n c yo ff r e q u e n ti t e ms e t sm i n i n g i nt h i sp a p e r , t h ea u t h o rw i l lf o c u so no p t i m i z i n ge n u m e r a t i o ns t r a t e g ya n d p r u n i n gs t r a t e g yt h r o u g h t h ea n a l y s i sa n dc o m p a r i s o no ft h ea d v a n t a g e sa n d d i s a d v a n t a g e s o ft h e e x i s t i n gf r e q u e n t i t e ms e t s m i n i n ga l g o r i t h m s i n t w o d i m e n s i o n a la n dt h r e e - d i m e n s i o n a la s p e c t s t h ea u t h o rt r i e st o i m p r o v et h e b i t w i s e - b a s e dc l o s e dp a t t e r nm i n i n ga l g o r i t h mb d m i n e ri nt w o - d i m e n s i o n a l d a t a s e t sa n dt h eb i t w i s e - b a s e dc l o s e d p a t t e r nm i n i n ga l g o r i t h m b d - p e e l e ri n t h r e e - d i m e n s i o n a ld a t a s e t s b o t ho ft h ea l g o r i t h m sd on o to n l yi n h e r i tt h ea d v a n t a g e s o fe x i s t i n ga l g o r i t h m s ，b u ta l s of i n i s hd a t am i n i n gt a s k sm o r ee f f i c i e n t l y t h eb d - m i n e ra n db d - p e e l e ri sa c c o m p l i s h e dt h r o u g ht h eu s a g eo fv c + + 6 0 a b s t r a c t 一一一 i nt h i sp a p e r an u m b e ro fe x p e r i m e n t sh a v eb e e nc a r r i e do u ts e r i o u s l y , a n dt h e r e s u l t sh a v eb e e nc o m p a r e dw i t he x i s t i n ga l g o r i t h m si n t h em u l t i p l ed a t a s e t s c a r e 如l l v t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t ，t h ee f f i c i e n c yo fs a m ed a t am i n i n g t a s _ k si i lt h es 鋤ed a t a s e t sa n dt h es a m ec o n s t r a i n t sc a nb ei m p r o v e d6 - 7t i m e si n t w o d i m e n s i o n a ld a t a s e t sw i t ht h eu s eo fb d m i n e ra l g o r i t h m ；w h i l e3t i m e s i n t h r e e d i m e n s i o n a ld a t a s e t sw i t ht h eb d - p e e l e rm i n i n ga l g o r i t h m k e y w o r d s ：d a t am i n i n g ；c l o s e df r e q u e n t i t e m s e t s ；b i t w i s e ；c o n s t r a i n t s ； t w o d i m e n s i o n a l ；t h r e e d i m e n s i o n a l 目錄 目錄 摘要i a b s t r a c t i i 目錄 1 緒論一1 1 1 研究背景及意義1 1 2 研究內(nèi)容0 2 1 3 論文組織結(jié)構(gòu)2 2 數(shù)據(jù)挖掘概述4 2 1 數(shù)據(jù)挖掘的概念4 2 2 數(shù)據(jù)挖掘的功能4 2 3 頻繁項集挖掘概述6 2 3 1 頻繁項集一6 2 3 2 最大頻繁項集一7 2 3 3 閉頻繁項集一7 2 4 經(jīng)典頻繁項集挖掘方法7 2 4 1 a p r i o r i 算法7 2 4 2 f p - g r o w t h 算法8 2 5 本章小結(jié)9 3 位運算10 3 1 集合與二進制的關(guān)系1 0 3 2 集合二進制表示的運算一11 目錄 3 2 i 集合交集1 2 3 2 2 集合并集1 2 3 2 3 集合子集判斷1 3 3 2 4 集合第i 個域值元素包含判斷1 4 3 2 5 集合加入第i 個域值元素1 4 3 2 6 集合移除第i 個域值元素1 5 3 2 7 集合移除第1 個集合元素16 3 2 8 集合元素個數(shù)l6 3 3 本章小結(jié)18 4 基于位運算的二維閉頻繁項集挖掘算法一1 9 4 1 二維頻繁項集挖掘現(xiàn)狀1 9 4 2 相關(guān)定義2 2 4 3 數(shù)據(jù)集存儲結(jié)構(gòu)一2 3 4 4 b d m i n e r 算法2 4 4 4 1 二元枚舉策略2 4 4 4 2 剪枝左結(jié)點2 5 4 4 3 封閉性剪枝2 6 4 5 實驗結(jié)果及分析。2 7 4 5 1 算法有效性驗證2 8 4 5 2 算法效率2 9 4 6 本章小結(jié)3 0 5 基于位運算的三維閉頻繁項集挖掘算法。31 5 1 三維頻繁項集挖掘現(xiàn)狀3l 5 2 相關(guān)定義3 5 5 3 b d p e e l e r 算法3 6 5 3 1 二元枚舉策略3 6 5 3 2 剪枝左結(jié)點3 6 v 目錄 5 3 3 封閉性優(yōu)化策略3 7 5 4 空間復(fù)雜性3 9 5 4 1 數(shù)據(jù)集存儲結(jié)構(gòu)3 9 5 4 2 枚舉樹結(jié)點存儲結(jié)構(gòu)4 0 5 5 實驗結(jié)果及分析一4 1 5 5 1 算法有效性驗證4 1 5 6 本章小結(jié)一4 4 6 總結(jié)及進一步工作展望：4 5 6 1 論文總結(jié)4 5 6 2 工作展望4 5 參考文獻4 7 個人簡歷5 0 攻讀碩士學(xué)位期間的研究成果5 0 致謝51 v l 1 緒論 1 緒論 1 1 研究背景及意義 在信息技術(shù)高度發(fā)達的今天，現(xiàn)實生活和商業(yè)應(yīng)用中積累了大量歷史數(shù)據(jù)， 而且這些數(shù)據(jù)正呈幾何爆炸式增長。面對如此海量的數(shù)據(jù)，如果沒有一種強有 力的知識發(fā)現(xiàn)工具來挖掘知識，那就等于是在浪費龐大的數(shù)據(jù)資源，好比地下 蘊藏著大量的寶藏，卻沒有先進的挖掘設(shè)備將其挖出。簡單的存取和查詢等操 作已經(jīng)遠遠無法滿足人們的需求，這些操作只能從數(shù)據(jù)庫中提取很少一部分知 識信息，而且所提取的信息還要依賴于人們的經(jīng)驗積累，而大部分潛在的重要 信息和知識卻無法提取出來，這些潛在信息對于市場分析、商業(yè)決策、疾病診 斷、科學(xué)研究、欺詐檢測等都具有很重要的參考價值。海量的歷史數(shù)據(jù)既蘊含 著大量寶貴資源，同時也把我們淹沒在數(shù)據(jù)和信息的汪洋大海里。如何有效的 從海量數(shù)據(jù)中快速提取有用信息和知識，以應(yīng)對社會挑戰(zhàn)以及對未來發(fā)展提供 指導(dǎo)，成為一個需求與技術(shù)的瓶頸。在這種情況下，數(shù)據(jù)挖掘?qū)W科應(yīng)運而生， 并顯示出強大的生命力和巨大的發(fā)展?jié)摿Α?數(shù)據(jù)挖掘又稱數(shù)據(jù)庫中的知識發(fā)現(xiàn)( 1 d ) ，是從大量的、不完全的、有 噪聲的、模糊的、隨機的實際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、人們事先不知 道的、但又是潛在有用的信息和知識的過程【】。數(shù)據(jù)挖掘研究是一個跨學(xué)科的 交叉領(lǐng)域，它從多個學(xué)科中汲取養(yǎng)料，融合了數(shù)據(jù)庫、人工智能、機器學(xué)習(xí)、 神經(jīng)網(wǎng)絡(luò)、信息檢索、統(tǒng)計學(xué)、集合論等學(xué)科的最新研究技術(shù)成果。數(shù)據(jù)挖掘 技術(shù)的發(fā)展，使得從海量數(shù)據(jù)中快速提取有用信息和知識的需求成為現(xiàn)實。 關(guān)聯(lián)規(guī)則挖掘是從大量數(shù)據(jù)中發(fā)現(xiàn)項集之間的相關(guān)聯(lián)系，它是數(shù)據(jù)挖掘一 個重要的研究方向。隨著數(shù)據(jù)庫中的數(shù)據(jù)積累導(dǎo)致數(shù)據(jù)規(guī)模越來越大，人們對 從這些數(shù)據(jù)中挖掘集合的相應(yīng)關(guān)聯(lián)知識越來越感興趣。最經(jīng)典的例子莫過于從 購物籃信息數(shù)據(jù)分析中發(fā)現(xiàn)啤酒與尿布的關(guān)聯(lián)。而頻繁項集挖掘做為關(guān)聯(lián)規(guī)則 挖掘過程的第一步，成為關(guān)聯(lián)規(guī)則挖掘有效性的關(guān)鍵。 從1 9 9 3 年關(guān)聯(lián)規(guī)則概念1 2 1 提出以來，頻繁項集挖掘受到數(shù)據(jù)挖掘?qū)＜覀兊?廣泛關(guān)注，并成為數(shù)據(jù)挖掘界里一個最活躍的領(lǐng)域，并提出了有效的頻繁項集 挖掘算法，如經(jīng)典的a 研o r i 算澍3 】及f p t r e e 算法【4 1 。近些年對這些算法存在 1 緒論 的一些問題學(xué)者們也一直在優(yōu)化，提出了很多有效的改進算法1 5 1 6 。 隨著數(shù)據(jù)庫中數(shù)據(jù)的不斷積累以及人們對知識發(fā)現(xiàn)的需要更加全方位化， 越來越多的數(shù)據(jù)挖掘需求要在三維甚至多維數(shù)據(jù)集中進行處理，這就要求提出 對應(yīng)的有效頻繁項集挖掘算法以適應(yīng)多維數(shù)據(jù)集的特點。國內(nèi)外學(xué)者在二維技 術(shù)的基礎(chǔ)上提出了很多算法【_ 7 1 ，如將二維a p r i o r i 算法引申到三維數(shù)據(jù)上，提出 了類a p r i o r i 算法【8 】【9 】、基于切片的r s m 算法【1 0 1 、基于枚舉的算法等。 1 2 研究內(nèi)容 集合與二進制存在著完美的對應(yīng)關(guān)系，用二進制形式存儲和處理集合數(shù)據(jù)， 能大大提高集合的操作效率。頻繁項集的挖掘核心是集合運算，因此如果在頻 繁項集挖掘過程中引入位處理技術(shù)，將會大大提高頻繁項集挖掘的效率。 本文主要研究在布爾型數(shù)據(jù)裂1 2 】上，將位處理技術(shù)運用n - 維頻繁項集挖 掘和三維頻繁項集挖掘過程，并對現(xiàn)有的多種二維頻繁項集挖掘算法和三維頻 繁項集挖掘算法優(yōu)缺點進行分析比較，設(shè)計出更加高效的二維頻繁項集挖掘算 法和三維頻繁項集挖掘算法，使得算法既繼承了現(xiàn)有算法的優(yōu)點，又能更有效 的完成挖掘任務(wù)。 本文的主要研究內(nèi)容包括以下幾個方面： 1 ) 在分析多種二維閉頻繁項集挖掘算法優(yōu)缺點的基礎(chǔ)上，提出一種在二 個維元素集合上同時進行枚舉元素產(chǎn)生的枚舉策略。實驗證明，該枚 舉策略大大減少生成頻繁項集的平均處理次數(shù)。 2 ) 在分析多種三維閉頻繁項集挖掘算法優(yōu)缺點的基礎(chǔ)上，對算法 d a t a p e e l e r j 進行兩個優(yōu)化策略處理。實驗證明了兩種優(yōu)化策略的有效 性。 3 ) 結(jié)合集合與二進制的關(guān)系，將位運算引入n - 維和三維頻繁項集挖掘 算法中，對集合的運算能同時在3 2 個集合元素之間進行。實驗結(jié)果表 明，這樣大大提高了算法的效率。 1 3 論文組織結(jié)構(gòu) 本文共分六章，各章節(jié)主要內(nèi)容安排如下： 第一章為緒論部分，主要介紹了本課題研究的背景與意義，同時簡要地說 2 1 緒論 明了研究內(nèi)容及論文的組織結(jié)構(gòu)。 第二章主要介紹了數(shù)據(jù)挖掘相關(guān)的概念、定義，詳述了數(shù)據(jù)挖掘的經(jīng)典算 法原理。 第三章對位運算技術(shù)進行詳細介紹。從集合與二進制關(guān)系入手，然后列舉 了集合二進制表示的部分操作以及具體實現(xiàn)。 第四章在現(xiàn)有二維數(shù)據(jù)挖掘算法的基礎(chǔ)上，引入二元枚舉策略以及位處理 技術(shù)，提出了基于位運算的二維閉頻繁項集挖掘算法。該算法不僅大大減少了 頻繁項集產(chǎn)生的平均處理次數(shù)，而且通過位處理運算大大提高了算法的效率。 通過大量的實驗對比驗證了算法枚舉策略以及位運算引入的有效性。 第五章在現(xiàn)有三維數(shù)據(jù)挖掘算法的基礎(chǔ)上，提出兩個優(yōu)化策略，并引入位 處理技術(shù)，產(chǎn)生了基于位運算的二維閉頻繁項集挖掘算法。該算法不僅大大減 少復(fù)雜封閉性定義驗證次數(shù)，而且通過位處理運算大大提高了算法的效率。通 過大量的實驗對比驗證了算法優(yōu)化策略以及位運算引入的有效性。 第六章對前面的研究進行了總結(jié)并對下一步工作進行了展望。 2 數(shù)據(jù)挖掘概述 2 數(shù)據(jù)挖掘概述 2 1 數(shù)據(jù)挖掘的概念 簡單地說，數(shù)據(jù)挖掘是指從大量數(shù)據(jù)中提取或“挖掘知識 。挖掘一詞形象 的描述了從大量未加工數(shù)據(jù)中提取少量有價值信息這個過程特點【1 】o 數(shù)據(jù)挖掘的定義在學(xué)術(shù)界一直存在一定的爭議，而且一般情況下數(shù)據(jù)挖掘 與知識發(fā)現(xiàn)( k d d ) 不加區(qū)分。數(shù)據(jù)挖掘一個全面的定義是從大量的、不完全 的、有噪聲的、模糊的、隨機的實際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、人們事 先不知道的、但又是潛在有用的信息和知識的過程。 數(shù)據(jù)挖掘研究是一個跨學(xué)科的交叉領(lǐng)域，它從多個學(xué)科中汲取養(yǎng)料，融合 了數(shù)據(jù)庫、人工智能、機器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、信息檢索、統(tǒng)計學(xué)、集合論等學(xué) 科的最新研究技術(shù)成果。數(shù)據(jù)挖掘技術(shù)的發(fā)展，使得從海量數(shù)據(jù)中快速提取有 用信息和知識的需求成為現(xiàn)實。 2 2 數(shù)據(jù)挖掘的功能 通過數(shù)據(jù)挖掘的定義知，數(shù)據(jù)挖掘的目標(biāo)是提取未知的、有用的信息，這 就需要數(shù)據(jù)挖掘的任務(wù)有預(yù)測性和描述性。數(shù)據(jù)挖掘的功能【l 】大致有以下幾種 類型： 1 ) 概念類描述 概念描述就是使用匯總的、簡潔的和精確的方式描述數(shù)據(jù)特征，即對目標(biāo) 類數(shù)據(jù)的一般特征進行匯總概括。類描述屬于區(qū)別性描述。如果說概念描述是 找類數(shù)據(jù)的共同特性，類描述則是對比不同類數(shù)據(jù)的區(qū)別。 數(shù)據(jù)描述可以從數(shù)據(jù)的不同層次進行抽象概括。例如中國移動的客戶業(yè)務(wù) 消費信息，經(jīng)理也許對每個客戶的時實業(yè)務(wù)消費情況不感興趣，他對客戶群體 ( 如工薪階層) 的整體消費( 如共同使用業(yè)務(wù)) 更感興趣。 2 ) 頻繁模式與關(guān)聯(lián)分析 頻繁模式是指數(shù)據(jù)中頻繁出現(xiàn)的模式。頻繁模式有多種類型，包括項集、 子序列和子結(jié)構(gòu)。頻繁項集是指頻繁地在事務(wù)數(shù)據(jù)集中一起出現(xiàn)的項的集合， 如牛奶和面包，啤酒和尿布。本文主要研究頻繁項集的挖掘。頻繁項集挖掘是 4 2 數(shù)據(jù)挖掘概述 頻繁模式挖掘的最簡單形式，是關(guān)聯(lián)分析的基礎(chǔ)，對數(shù)據(jù)分類、聚類和其它數(shù) 據(jù)挖掘任務(wù)有也幫助。 3 ) 分類和預(yù)測 分類和預(yù)測就是依據(jù)所分析對象的特征，找出描述和區(qū)分?jǐn)?shù)據(jù)的模型，然后 使用模型預(yù)測類標(biāo)號未來的對象類。此任務(wù)關(guān)鍵是確定對數(shù)據(jù)按照什么標(biāo)準(zhǔn)或 什么規(guī)則進行分類。 比如對于企業(yè)客戶群體，我們根據(jù)其收入水平進行分類，有高、中、低三 類。當(dāng)有新客戶加入時，我們就可以按其收入水平，確定其屬于哪個類，然后 對其進行設(shè)計相應(yīng)的營銷策略。 4 ) 聚類分析 聚類分析是一種重要的人類行為，人類就是通過不斷地改進下意識中的聚 類模式來學(xué)會如何區(qū)分各種自然界的生物對象的，如：大猩猩和猴子，動物和 植物等。聚類就是將數(shù)據(jù)對象分組成多個類或簇，使得同一個類中的對象盡可 能相似，不同類中的對象盡可能相異。聚類分析內(nèi)容非常豐富，如系統(tǒng)聚類法、 有序樣品聚類法、動態(tài)聚類法、模糊聚類法、圖論聚類法、聚類預(yù)報法等。聚 類分析在現(xiàn)實中也有很多用途，在商業(yè)上，聚類可以幫助市場分析人員從客戶 數(shù)據(jù)庫中識別出不同的客戶群體來，并且概括出每一類客戶的購買模式或者說 習(xí)慣，從而使企業(yè)按客戶的不同需求來提供相應(yīng)的產(chǎn)品和服務(wù)。在生物學(xué)上， 聚類可以被用來對基因進行分類，幫助人們認(rèn)識不同種群的固有結(jié)構(gòu)和特征。 在保險行業(yè)上，聚類分析能夠用來對汽車保險單持有者進行分組，同時根據(jù)住 宅類型，價值，地理位置來鑒定一個城市的房產(chǎn)分組。聚類分析還可以用在電 子商務(wù)網(wǎng)站的建設(shè)上，通過分組聚類出具有相似瀏覽行為的客戶，并分析他們 的共同特征，從而幫助電子商務(wù)的用戶更加了解不同的客戶群，向客戶提供更 加細致入微的服務(wù)。 5 ) 孤立點分析 在數(shù)據(jù)庫中包括這樣一部分?jǐn)?shù)據(jù)對象，它們與數(shù)據(jù)的一般行為或模型不一 致，我們把這些數(shù)據(jù)對象叫做孤立點。一般的分析手段，特別是基于統(tǒng)計學(xué)的 統(tǒng)計方法，都把這些孤立點當(dāng)成噪聲或異常數(shù)據(jù)而丟棄。但是，在某些應(yīng)用分 析中，如欺騙檢測，對這些點的分析比對一般數(shù)據(jù)的分析更有價值。 2 數(shù)據(jù)挖掘概述 2 3 頻繁項集挖掘概述 關(guān)聯(lián)規(guī)則的概念由a g r a w a l ，i m i d i n s k i 和s w a m i 在1 9 9 3 年首次提出【2 l ，對 商品購物籃信息進行分析，為了發(fā)現(xiàn)交易數(shù)據(jù)庫中不同商品之間的聯(lián)系。關(guān)聯(lián) 規(guī)則的研究總體分為挖掘頻繁項集和產(chǎn)生關(guān)聯(lián)規(guī)則兩個階段，挖掘頻繁項集是 產(chǎn)生關(guān)聯(lián)規(guī)則的核心部分。 定義2 1 設(shè)i = 1 1 ，1 2 ，i m 是項的集合，d = t 1 ，t 2 ，t n 是事務(wù)數(shù)據(jù)庫中 的事務(wù)集合。其中每一個事務(wù)t 是項的集合，使得t c i ，每個事務(wù)有一個標(biāo)識 符，稱作t i d 。設(shè)a 是一個項集，如果a c t 則稱事務(wù)t 包含項集a 。 定義2 2 項集的出現(xiàn)頻率是包含項集的事務(wù)數(shù)，簡稱為項集的支持度計數(shù)。 2 3 1頻繁項集 給定一個支持度閾值，如果項集a 的支持度大于支持度閾值，則稱項集a 。是頻繁項集。 頻繁項集挖掘的a p r i o r i 算法由a g r a w a l 和s r i k a n t 提出。其核心理論是頻 繁項集的一個重要的性質(zhì)：a p n o r i 性質(zhì)，即如果一個項集是頻繁的，則該項集的 所有非空子集也是頻繁削1 1 。 表2 1 某超市的事務(wù)數(shù)據(jù) t i d 商品列表 t l t 2 t 3 a , b ，c b ，c ，d a , b ，c ，d 在表2 1 的超市事務(wù)數(shù)據(jù)中，如果我們假定支持度閾值為2 ，則頻繁項集共 有1 2 個： a ) ， b ) ， c ) ， d ) ， a ，b ) ， a ，c ) ， a ，d ) ， b ，c ) ， b ，d ) ， c ，d ) ， a ，b ，c ) ， b ，c ，d ) 。 如上例可知，即使在只有3 條事務(wù)的數(shù)據(jù)中，頻繁項集個數(shù)就有1 2 個之多。 這也正是因為a p n 嘶性質(zhì)決定的。特別是對于長項集，將會有組合個數(shù)個較短 的頻繁子項集。例如對于一個長為2 0 的頻繁項集 a 1 ，a 2 ，a 2 0 ) ，將包含d 。個 頻繁1 項集a 1 ，a 2 ，a 2 0 ，c 三個頻繁2 項集 a l ，a 2 ， a l ，a 3 ) ， a 1 9 ，a 2 0 等。 該項集包含的總的項集個數(shù)為c ；n + c 磊+ + c 囂= 2 2 0 1 。當(dāng)項集長度達到 1 0 0 時子集個數(shù)將更是一個天文數(shù)字。 為了解決這種組合爆炸問題，提出了極大頻繁項集和閉頻繁項集的概念。 6 2 數(shù)據(jù)挖掘概述 2 3 2 最大頻繁項集 定義2 3 最大頻繁項集是指不存在直接超項集也是頻繁項集的頻繁項集。 在表2 1 的超市事務(wù)數(shù)據(jù)中，如果我們假定支持度閾值為2 ，則最大頻繁項 集只有2 個： a ，b ，c ) ， b ，c ，d ) 。 最大頻繁項集概念的提出，使挖掘出的頻繁項集數(shù)量大大減小，有效解決 了挖掘完全頻繁項集所出現(xiàn)的子集組合爆炸問題。 由最大頻繁項集雖然可以導(dǎo)出所有的頻繁項集，但是卻丟失了支持度信息。 比如對項集 b 的支持度信息，我們只知道大于2 ，但不知道確切值，如果進行 比較深入分析使用到該值時，該操作將無法完成，因此出現(xiàn)了閉頻繁項集或閉 頻繁項集的概念。 2 3 3 閉頻繁項集 定義2 4 閉頻繁項集是指不存在有直接超項集的支持度與該項集支持度相 等的頻繁項集。 在表2 1 的超市事務(wù)數(shù)據(jù)中，如果我們假定支持度閾值為2 ，則閉頻繁項集 和支持度為： b ，c ) ：3 ) ， a ，b ，c ) ：2 ) ， b ，c ，d ) ：2 ) ，閉頻繁項集集個數(shù)為3 。 閉頻繁項集概念的提出，既有效解決了挖掘完全頻繁項集所出現(xiàn)的子集組 合爆炸問題，又保存了完整了支持度信息。閉頻繁項集的集合中包含了頻繁項 集的完整信息，因為不是閉頻繁項集的頻繁項集的支持度一定等于其所有超集 中有最大支持度的那個頻繁項集的支持度。因此在頻繁項集的現(xiàn)實應(yīng)用中，人 們更希望挖掘的是閉頻繁項集【1 3 】。 2 4 經(jīng)典頻繁項集挖掘方法 對于頻繁項集的挖掘，已經(jīng)有了許多比較有效的算法。經(jīng)典的算法有： a p r i o r i 算法及其變種算法即類a p r i o r i 算法、f p g r o w t h 算法。 2 4 1 a p r i o r i 算法 19 9 4 年，a p r i o r i 算法 3 由a g r a w a l 和s r i k a n t 提出，該算法是挖掘頻繁項 集是原創(chuàng)性算法。a p r i o r i 性質(zhì)，即如果一個項集是頻繁的，則該項集的所有非 空子集也是頻繁的，換句話說，即如果一個項集不是頻繁的，則他的所有超集 7 2 數(shù)據(jù)挖掘概述 也是不頻繁的。a p r i o r i 算法利用該先驗原理，使用逐層搜索迭代方式的廣度優(yōu) 先策略，利用k 項集產(chǎn)生l 針1 項集。算法描述如下： 通過掃描數(shù)據(jù)庫的事務(wù)，收集所有1 項集的計數(shù)，找出滿足支持度閾值的 頻繁l 項集，記做l l 。 利用l l 組合產(chǎn)生2 項集做為候選2 項集，記做c 2 。 再次掃描事務(wù)數(shù)據(jù)庫，驗證c 2 中的項集是否是頻繁的，如果候選2 項集是 頻繁的則加入頻繁2 項集l 2 中，否則繼續(xù)驗證，直到把c 2 所有項集驗證完。 利用l 卜l 2 組合產(chǎn)生3 項集做為修行3 項集，記做c 3 驗證c 3 生成k 重復(fù)利用l l 、k 、l k 生成c k + l ，然后驗證c k + l 生成l k + 1 。直到不能繼 續(xù)生成再更長的頻繁項集為止。 a p r i o r i 算法高效的關(guān)鍵在于只生成較小的候選項目集，也就是盡可能不讓 候選項目集中出現(xiàn)一定不頻繁的項集。算法利用了a p r i o r i 原理和反單調(diào)性實現(xiàn) 這一點，即：如果一個項集是頻繁的，則該項集的所有非空子集也是頻繁的； 如果一個項集不是頻繁的，則他的所有超集也是不頻繁的。 該算法缺點在于要組合產(chǎn)生候選項集，這個在數(shù)量上是可能是呈指數(shù)增長 的，而且在驗證候選項集的時候要多次掃描數(shù)據(jù)庫。雖然該算法后來被很多人 優(yōu)化，但算法的核心思想所固有的特性：必須由k 項集產(chǎn)生k + 1 項集，使得基 于a p r i o r i 算法在處理數(shù)據(jù)庫密度比較稠密、頻繁模式項比較長、支持度閾值比 較低時的效率性不高。 2 4 2 f p - g r o w t h 算法 為了解決產(chǎn)生候選項集而帶來的組合爆炸問題，h a nj i a w e i 等人在2 0 0 0 年 提出了一種新的頻繁項集挖掘算法f p g r o w t h 算法【4 】。該算法使用了基于 f p t r e e 結(jié)構(gòu)的不產(chǎn)生候選項集的思想，徹底擺脫了a 研o r i 算法必須產(chǎn)生大量 候選項集的傳統(tǒng)挖掘方式的弊端，開辟了關(guān)聯(lián)規(guī)則挖掘的新思路。 h a n 等人設(shè)計了一種新的數(shù)據(jù)結(jié)構(gòu)一壓縮的數(shù)據(jù)結(jié)構(gòu)( f p t r e e ) ，f p 樹中存儲 關(guān)聯(lián)規(guī)則挖掘所需要的全部數(shù)據(jù)信息。只需要對事務(wù)數(shù)據(jù)庫進行兩次掃描，即 可完成數(shù)據(jù)挖掘任務(wù)。第一次掃描與a p r i o r i 算法一樣，收集所有的頻繁1 項集 及其支持度信息。第二次掃描構(gòu)建f p 樹，把數(shù)據(jù)庫的頻繁項集的信息壓縮到頻 繁項目樹，同時保留項集之間的關(guān)聯(lián)。這樣就有效的避開了產(chǎn)生候選項集的方 2 數(shù)據(jù)挖掘概述 式，大大的減少了花費在數(shù)據(jù)交換和頻繁匹配的開銷。由于f p 樹中存儲關(guān)聯(lián)規(guī) 則挖掘所需要的全部數(shù)據(jù)信息，因此后面的工作只需要在f p 樹上進行，這樣將 數(shù)據(jù)庫頻繁模式的挖掘問題轉(zhuǎn)變成為挖掘f p 樹的問題，既不需要產(chǎn)生候選項 集，也大大減少數(shù)據(jù)庫掃描的次數(shù)。 實驗證明，在挖掘效率上f p g r o w t h 算法明顯優(yōu)于a p r i o r i 算法，特別是在 稠密數(shù)據(jù)庫中，頻繁項集的長度很大的情況下，f p g r o w t h 算法的優(yōu)勢越明顯。 f p g r o w t h 算法的缺點是需要遞歸生成條件f p 樹，在面對大型數(shù)據(jù)集時，遞歸 產(chǎn)生的開銷很大，甚至一棵頻繁模式樹可能不能放入主存中，因此內(nèi)存開銷大， 而且它也只能挖掘二維的布爾型事務(wù)數(shù)據(jù)。 2 5 本章小結(jié) 本章首先通過介紹數(shù)據(jù)挖掘的一些基本理論引出關(guān)聯(lián)規(guī)則挖掘，然后有針 對性的對關(guān)聯(lián)規(guī)則挖掘的中頻繁項集挖掘進行分析，描述了頻繁項集挖掘的經(jīng) 典算法。 9 3 位運算 3 位運算 二進制理論是現(xiàn)代計算機的核心基礎(chǔ)理論之一。雖然數(shù)據(jù)值域只用0 和1 表示，但是由相對簡單的組合可以表達任何意義上的數(shù)據(jù)。正是由于二進制表 示形式的簡易性、可靠性、邏輯性、可行性，使其求和運算法則只有三種，數(shù) 據(jù)存儲、傳輸和處理的可靠性得以保障，1 和0 在邏輯代數(shù)中分別對應(yīng)真與假， 在物理上對應(yīng)高電平( 高電壓) 和低電平( 低電壓) ，這樣才使現(xiàn)代計算機設(shè) 計與運算的簡單性成為現(xiàn)實。計算機內(nèi)部的所有信息都用二進制( 0 、1 ) 來表 示，因此在外部條件和技術(shù)同等的條件下，如何最大限度的利用二進制運算是 提高數(shù)據(jù)處理效率的王牌手段。 3 1 集合與二進制的關(guān)系 集合與二進制的關(guān)系在文獻【1 4 】【1 5 】中已詳細描述，這里僅做簡要介紹并舉 例說明。 如果集合的域值中有n 個元素，則該域值空間能表示的集合數(shù)為2 n 個。假 如對于集合域值為 a , b ，c ) ，則該域值空間能表示是所有集合為 1 2 i ) ， a ) ， b ) ， a ，b ) ， c ) ， a ，c ， b , c ) ， a ，b ，e ) ) ，共8 個集合。 長度為n 的二進制位串可以表示的不同數(shù)據(jù)個數(shù)為2 n 個。例如對于長度為 3 的位串，所有表示的數(shù)據(jù)為0 0 0 ，0 0 1 ，0 1 0 ，0 1 1 ，1 0 0 ，1 0 1 ，1 1 0 ，1 1 1 ，共8 個不同數(shù)據(jù)。 對比發(fā)現(xiàn)，集合的域值中有n 個元素的域值空間所能表示的集合數(shù)與長度 為n 的二進制位串可以表示的不同數(shù)據(jù)個數(shù)相等，而且形式上相似。因此，猜 想可能存在某種映射關(guān)系，使一個長度為n 的二進制位串與域值中有n 個元素 的域值空間所能表示的集合存在一一以應(yīng)的關(guān)系。 假設(shè)對于集合域值空間x = ，用一個二進制位串 p - p n p n 1 p 2 p l 的位串來表示。其中二進制位串p 中的第1 位p l 對應(yīng)集合中的 第1 個元素x l ，二進制位串p 中的第i 位p i 對應(yīng)集合中的第i 個元素x i ，二進 制位串p 中的第n 位p n 對應(yīng)集合中的第n 個元素x 。 例如假設(shè)集合域值為 a , b ，c ) ，則用一個三位的二進制串與域值空間的集合 1 0 3 位運算 對應(yīng)。其中二進制位串的第1 位與元素a 對應(yīng)，第2 位與元素b 對應(yīng)，第3 位 與元素c 對應(yīng)。其對應(yīng)關(guān)系如表3 1 所示。 表3 1 集合域值 a ，b ，c ) 與二進制的對應(yīng)關(guān)系 通過對比發(fā)現(xiàn)，如果我們使用表3 1 的方式對集合與二進制一一對應(yīng)，則 集合域值空間第i 個元素與位串中的第i 位串的關(guān)系：如果子集中包含第i 個元 素，則位串中第i 位值為1 ，如果子集中不包含第i 個元素，則位串中第i 位值 為0 。例如對于編號為3 的子集 a ，b ) ，由于a 和b 元素包含在集合中，所以二 進制位串的第1 位和第2 位值為1 ，而元素c 不包含在集合中，所以二進制位 串的第3 位值為0 ，所以對應(yīng)位串為0 1 1 。 因此可用一個長度為n 的二進制位串來表示集合，二進制位串中的每一位 對應(yīng)集合中的一個元素，當(dāng)集合中某一元素包含在集合中，則對應(yīng)二進制位串 中該位的值為1 ，當(dāng)集合中某一元素不包含在集合中，則對應(yīng)二進制位串中該 位的值為0 。 算法中的具體存儲實現(xiàn)如3 1 圖所示，對二進制位串每3 2 位一組編碼，用 一個無符號整數(shù)來存儲。 4 個字節(jié)3 2 位 4 個字節(jié)3 2 位 圖3 1 二進制位串的存儲格式 3 2 集合二進制表示的運算 由于集合我們用二進制來存儲，即可用一個長度為n 的二進制位串來表示 1 1 3 位運算 集合，二進制位串中的每一位對應(yīng)集合中的一個元素，因此在這里我們討論的 集合元素假設(shè)是有序的。 3 2 1集合交集 設(shè)集合b 和c 為在域值空間 曲，c ) 上的集合，求b n c 。 由集合的交集定義知，b n c = 缸i 石肼_ g x c ，即結(jié)果集合為既包含 在b 中又包含在c 中的元素，該運算可以由二進制的位與運算來實現(xiàn)。通過兩 個集合的二進制位串表示的相應(yīng)下標(biāo)的位與運算，得出兩個集合交集的結(jié)果對 應(yīng)的位串，從而很快得出兩個集合中的公共元素。例如，假設(shè)b = a ，b ) ，c = a ，c ) ， 則b 對應(yīng)的二進制位串為0 1 1 ，c 對應(yīng)的二進制位串為1 0 1 ，b n c = 0 1 1 & 1 0 1 = 0 0 1 ， 因此bnc = a 。 算法具體實現(xiàn)為每3 2 位位串用一個整數(shù)來存儲，本例中b 對應(yīng)位串?dāng)?shù)據(jù)存 儲值為3 ，c 對應(yīng)位串?dāng)?shù)據(jù)存儲值為5 ，計算得b n c = 3 & 5 = 1 ，因此b n c = a ) 。 u n s i g n e di n t e r s e c t i o n ( u n s i g n e db ，u n s i g n e dc ) 求b 和c 代表的兩個集合的交集 參數(shù)b ，c 為集合的位串存儲數(shù)據(jù)值 r e t u r n ( b & c ) ； ) 3 2 2 集合并集 設(shè)集合b 和c 為在域值空間 a , b ，c ) 上的集合，求b u c 。 由集合的并集定義知，b uc = 扛lx b 或瓠c ) ，即結(jié)果集合為包含在b 中或者包含在c 中的元素，該運算可以由二進制的位或運算來實現(xiàn)。通過兩個 集合的二進制位串表示的相應(yīng)下標(biāo)的位或運算，得出兩個集合并集的結(jié)果對應(yīng) 的位串，從而很快得出兩個集合的所有元素。例如，假設(shè)b = a ，b ) ，c = a ，c ) ， 則b 對應(yīng)的二進制位串為0 1 1 ，c 對應(yīng)的二進制位串為1 0 1 ，b u c = 0 1 1i1 0 1 = 1 1 1 ， 因此buc = a ，b ，c ) 。 算法具體實現(xiàn)為每3 2 位位串用一個整數(shù)來存儲，本例中b 對應(yīng)位串?dāng)?shù)據(jù)存 儲值為3 ，c 對應(yīng)位串?dāng)?shù)據(jù)存儲值為5 ，計算得b u c - - 35 = 7 ，因此b u c = a ，b ，c ) 。 3 位運算 u n s i g n e du n i o n s c t ( u n s i