摘要 摘要 數(shù)據(jù)挖掘是當(dāng)今國(guó)際上人工智能和數(shù)據(jù)庫(kù)研究方面最富活力的新興領(lǐng)域， 從大型數(shù)據(jù)庫(kù)中挖掘關(guān)聯(lián)規(guī)則的問(wèn)題已經(jīng)成為近年來(lái)數(shù)據(jù)挖掘研究領(lǐng)域中的一 個(gè)新熱點(diǎn)。股票投資風(fēng)險(xiǎn)與機(jī)遇并存。如何把握風(fēng)險(xiǎn)，投資回報(bào)最大化? 是投 資者追求的目標(biāo)t 而股票行情受經(jīng)濟(jì)、政治等因素的作用，其走勢(shì)變化莫測(cè)， 難以把握?，F(xiàn)有的股票分析軟件其可靠性有待驗(yàn)證。在股票行情數(shù)據(jù)庫(kù)中積累 了大量歷史交易數(shù)據(jù)，如何充分利用這些歷史數(shù)據(jù)，從關(guān)聯(lián)規(guī)則挖掘領(lǐng)域進(jìn)行 新的研究和探索變得很有意義。 本文基于國(guó)內(nèi)外研究成果，首先介紹了數(shù)據(jù)挖掘的理論，引入關(guān)聯(lián)規(guī)則挖 掘技術(shù)，對(duì)頻繁項(xiàng)集生成算法a p r i o r i 進(jìn)行了分析。針對(duì)股票數(shù)據(jù)的特點(diǎn)和關(guān)聯(lián) 規(guī)則算法a p r i o r i 存在的不足，提出一種基于比特向量和h a s h 技術(shù)的頻繁項(xiàng)集 生成優(yōu)化算法，并將其嵌入開(kāi)源數(shù)據(jù)挖掘工具w e k a 中。 同時(shí)對(duì)股票行情數(shù)據(jù)庫(kù)的原數(shù)據(jù)文件進(jìn)行分析，結(jié)合w e k a 數(shù)據(jù)格式的特 點(diǎn)設(shè)計(jì)了預(yù)處理模塊。 最后使用改進(jìn)后w e k a 挖掘工具對(duì)預(yù)處理后股票數(shù)據(jù)進(jìn)行挖掘。對(duì)挖掘出 的股票規(guī)則進(jìn)行了分析，為股票投資者預(yù)測(cè)股票未來(lái)的走勢(shì)提供了有價(jià)值的參 考。 關(guān)鍵詞：頻繁項(xiàng)集，股票預(yù)測(cè)，w e k a ，數(shù)據(jù)預(yù)處理 a b s t r a c t d a t am i n i n gi st h em o s t d e v e l o p i n g ，m a i na n dv i g o r o u sr e s e a r c hc o n t e n ti na r t i 6 c i a l i n t e l l i g e n c ea n dd a t a b a s er e s e a r c h a s s o c i a t i o nr u l em i n i n gf r o ml a r g ed a t a b a s ei s n e wh o tp o i n ti nd a t am i n i n g i th a sv e n t u r ea n do p p o r t u n i t yi ns t o c ki n v e s t i t u l e h o wt o g e tm em o s ty i e l da n dh o l dt h ev e n t u r e ? i n v e s t o rh a l l l ( e r e df o rt h e m h o w e v e r , s t o c kp r i c ew a sa l w a y sf l u c t u a n tf o rc o m p l e xp o l i t i c sa n de c o n o m y a m d d e p e n d a b i l i t ya b o u ts t o c ka n a l y s i ss o f t w a r en e e dv a l i d a t e w i t ht h ed e v e l o p m e n to f t h es t o c km a r k e t ，l o t so fh i s t o r yt r a n s a c t i o nd a t ah a v eb e e ns t o r e di ns t o c kd a t a b a s e i tb e c o m e ss i g n i f i c a t i o nu s i n ga s s o c i a t i o nr u l em i n i n gt e c h n o l o g yt o a n a l y z e da n d f o r e c a s tt h es t o c km a r k e t t h i sa r t i c l eb a s e do nt h ed o m e s t i ca n df o r e i g nr e s e a r c hr e s u l t s ，f i r s ti m r o d u c e dm e t h e o r yo fd a t am i n i n ga n da n a l y z e da l g o r i t h ma p r i o r i ，t h r o u g ht h ea n a l y s i so nt h e i n s u f f i c i e n c yo ft h et r a d i t i o n a la s s o c i a t i o nr u l ea l g o r i t h ma n ds p e c i a l t yi ns t o c kd a t a p r o d u c e da no p t i m i z e da l g o r i t h mi nf r e q u e n ti t e m st h a tb a s e do nb i tv e c t o r 趾dh a s h t e c h n o l o g yw h i c hi n s e r t e dt h ed a t am i n i n gt o o lw e k a 。 s i m u l t a n e i t y , d e s i g n e da n di m p l e m e n t e dd a t ap r e p r o c e s s i n gm o d e lt h r o u g ha n a l y s i s s t o c kr e s o u r c ed a t aa n dw e k a d a t at y p e f i n a l l ye x p l a i n e dt h ep r o c e s sa b o u ts t o c k a n a l y z e da p p l i c a t i o nm e r i t so fs t o c kr u l e s i t i n v e s t o rf o r e c a s ts t o c ke a ta n df l o w r u l e su s i n gm o d i f i c a t i o nw e k aa n d s u p p l i e dau s e f u lr e f e r e n c ef o rs t o c k k e y w o r d s ：f r e q u e n ti t e m s ，s t o c kf o r e c a s t ，w e k a , d a t ap r e p r o c e s s i n gm o d e l i i 學(xué)位論文獨(dú)創(chuàng)性聲明 學(xué)位論文獨(dú)創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工 作及取得的研究成果。據(jù)我所知，除了文中特別加以標(biāo)注和致謝的地 方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果，也不包含 為獲得直昌太堂或其他教育機(jī)構(gòu)的學(xué)位或證書(shū)而使用過(guò)的材料。與 我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確 的說(shuō)明并表示謝意。 一 正- 學(xué)位論文作者簽名( 手寫(xiě)) ：茭0簽字日期：如可年1 2 月7 0 日 學(xué)位論文版權(quán)使用授權(quán)書(shū) 本學(xué)位論文作者完全了解直邑太堂有關(guān)保留、使用學(xué)位論文 的規(guī)定，有權(quán)保留并向國(guó)家有關(guān)部門(mén)或機(jī)構(gòu)送交論文的復(fù)印件和磁 盤(pán)，允許論文被查閱和借閱。本人授權(quán)直昌態(tài)堂可以將學(xué)位論文的全 部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描 等復(fù)制手段保存、匯編本學(xué)位論文。同時(shí)授權(quán)中國(guó)科學(xué)技術(shù)信息研究 所將本學(xué)位論文收錄到中國(guó)學(xué)位論文全文數(shù)據(jù)庫(kù)，并通過(guò)網(wǎng)絡(luò)向 社會(huì)公眾提供信息服務(wù)。 ( 保密的學(xué)位論文在解密后適用本授權(quán)書(shū)) 學(xué)位論文作者簽名：鬟k 朽導(dǎo)師簽名勃參節(jié) ， f 簽字日期：) x 年l2 月3 。日 簽字日期： 稚年j 明弘日 第1 章緒論 1 1 選題意義 第1 章緒論 數(shù)據(jù)挖掘是當(dāng)今國(guó)際上人工智能和數(shù)據(jù)庫(kù)研究方面最富活力的新興領(lǐng)域， 其目標(biāo)是為了滿(mǎn)足用戶(hù)目標(biāo)，自動(dòng)處理大量的原始數(shù)據(jù)，從中識(shí)別重要和有意 義的模式，并將其作為知識(shí)加以表達(dá)。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘研究領(lǐng)域的一個(gè)重 要分支。從大型數(shù)據(jù)庫(kù)中挖掘關(guān)聯(lián)規(guī)則的問(wèn)題已經(jīng)成為近年來(lái)數(shù)據(jù)挖掘研究領(lǐng) 域中的一個(gè)新熱點(diǎn)。 股票投資風(fēng)險(xiǎn)與機(jī)遇并存。如何把握風(fēng)險(xiǎn)，投資回報(bào)最大化? 是投資者追 求的目標(biāo)。投資者時(shí)刻在關(guān)心股市、分析股市、試圖預(yù)測(cè)股市的發(fā)展趨勢(shì)。而 股票行情受經(jīng)濟(jì)、政治等因素( 如發(fā)行公司的經(jīng)營(yíng)狀況和財(cái)務(wù)狀況、新股上市、 利率水平、匯率變動(dòng)、國(guó)際收支、物價(jià)因素、經(jīng)濟(jì)周期、經(jīng)濟(jì)政策等) 的作用， 其內(nèi)部規(guī)律非常復(fù)雜，變化周期無(wú)序，同時(shí)我國(guó)資本市場(chǎng)投資者結(jié)構(gòu)具有特殊 性，個(gè)人投資者比例高，投資心態(tài)不同，對(duì)股票交易的行為產(chǎn)生直接的影響， 從而導(dǎo)致股價(jià)波動(dòng)，使股票走勢(shì)變化莫測(cè)，難以把握。 因此，研究和開(kāi)發(fā)能幫助投資者分析股市。預(yù)測(cè)股票走勢(shì)，輔助投資者投 資的軟件變得非常有意義，而目前，大部分的股票分析軟件是基于傳統(tǒng)的統(tǒng)計(jì) 分析技術(shù)，如k 線圖分析法、柱狀圖分析法、點(diǎn)數(shù)圖分析法、移動(dòng)平均法，還 有形態(tài)分析法、趨勢(shì)分析、基本面分析等，智能化水平不高，一般投資者一下 很難掌握并且其分析的可靠性還要進(jìn)一步實(shí)踐修正，真正的投資專(zhuān)家并不單純 以它為投資的依據(jù)，往往實(shí)踐經(jīng)驗(yàn)更重要。在這種情況下，針對(duì)海量股票數(shù)據(jù)， 從數(shù)據(jù)挖掘和人工智能領(lǐng)域進(jìn)行新的研究和探索，顯得很有意義。 1 2 國(guó)內(nèi)外的研究動(dòng)態(tài) 關(guān)聯(lián)規(guī)則挖掘及其挖掘算法是由i b ma l m a d e nr e a e a r c hc e n t e r 的a g r a w a l 首先提出的【1 1 ，因此，國(guó)外對(duì)挖掘頻繁項(xiàng)集的算法研究比較深入和成功。i b m a l m a d e nr e a e a r c hc e n t e r 的a g r a w a l 等1 9 9 4 年提出關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法 第1 章緒論 a p f i o n 算法之后a g r a w a l 和s f i k a n t 在此基礎(chǔ)上提出了a p f i o f i t i d 算法，美國(guó)的 p a r k 在19 9 6 年提出的d h p ( d i r e c th a s h i n ga n d p r u n i n g ) 算法、加拿大的z a k i 在 1 9 9 7 年提出的m a x c l i q u e 算法等，都是在基于a p f i o f i 算法的基礎(chǔ)上提出的改 良算法。2 0 0 0 年，德國(guó)的o z d e n 在“c y c l i c a s s o c i t i o nr u l e s 一文中提出了周 期關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法。但算法的時(shí)間段是人為確定的，從而得到的關(guān)聯(lián)規(guī)則不 能充分反映數(shù)據(jù)的內(nèi)在規(guī)律。a p r i o r i 算法在實(shí)際數(shù)據(jù)挖掘系統(tǒng)中得到了很好的 應(yīng)用，例如，i b m 公司a l m a d e n 研究中心開(kāi)發(fā)的q u e s t 系統(tǒng)，s g i 公司開(kāi)發(fā) 的m i n e s e t 系統(tǒng)，加拿大s i m o n f r a s e r 大學(xué)開(kāi)發(fā)的d b m i n e r 系統(tǒng)。然而試驗(yàn)結(jié) 果，類(lèi)a p d o r i 算法在最初的兩次數(shù)據(jù)庫(kù)掃描時(shí)開(kāi)銷(xiāo)很大，導(dǎo)致了算法的效率瓶 頸【5 1 。 國(guó)外已是研究熱門(mén)，并已經(jīng)達(dá)到一定的水平投入了應(yīng)用領(lǐng)域，而國(guó)內(nèi)對(duì)關(guān) 聯(lián)規(guī)則挖掘的研究還處于起步階段。國(guó)內(nèi)的部分學(xué)者對(duì)關(guān)聯(lián)規(guī)則挖掘進(jìn)行了大 量的研究，但提出的算法也都是基于國(guó)外所提出算法的改進(jìn)算法。中科院計(jì)算 所的歐陽(yáng)為民首先引入國(guó)外關(guān)聯(lián)規(guī)則挖掘的概念和思想，并在基于a p r i o r i 算法 的基礎(chǔ)上提出了時(shí)態(tài)約束的關(guān)聯(lián)規(guī)則。中科院計(jì)算機(jī)研究所的智能信息處理重 點(diǎn)實(shí)驗(yàn)室研制開(kāi)發(fā)的多策略數(shù)據(jù)挖掘平臺(tái)m s m i n e r 系統(tǒng)，將關(guān)聯(lián)規(guī)則挖掘算法 集成到此系統(tǒng)中。復(fù)旦大學(xué)研制開(kāi)發(fā)的a r m i n e r 系統(tǒng)，是專(zhuān)門(mén)針對(duì)智能化的 p o s 系統(tǒng)開(kāi)發(fā)的關(guān)聯(lián)規(guī)則挖掘工具，此系統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法是基于a p r i o r i 的改進(jìn)算法。雖然已經(jīng)取得了相當(dāng)?shù)某晒Γ壳霸谔幚順O大數(shù)據(jù)量時(shí)，如何 提高算法效率；如何迅速更新數(shù)據(jù)；在挖掘的過(guò)程中，如何提供一種與用戶(hù)進(jìn) 行交互的方法，以便把用戶(hù)的領(lǐng)域知識(shí)結(jié)合在其中等等都是尚待研究和解決的 問(wèn)題【2 1 。 1 9 9 1 年，數(shù)據(jù)挖掘的出現(xiàn)為股票投資分析研究提供了一種新的方式和思路。 國(guó)內(nèi)外許多學(xué)者紛紛采用數(shù)據(jù)挖掘技術(shù)，對(duì)原始的股票數(shù)據(jù)進(jìn)行處理，挖掘蘊(yùn) 含在交易數(shù)據(jù)背后，反應(yīng)股市變化的潛在規(guī)則，以實(shí)現(xiàn)對(duì)股票市場(chǎng)未來(lái)變化趨 勢(shì)進(jìn)行分析并期望達(dá)到指導(dǎo)股票投資者進(jìn)行理性投資的目的。 在國(guó)內(nèi)，香港科技大學(xué)的b e a tw u t h r i c h 開(kāi)發(fā)了基于因特網(wǎng)的股票預(yù)測(cè)系統(tǒng)， 這個(gè)系統(tǒng)根據(jù)幾個(gè)金融網(wǎng)站( 例如w w w w s j c o m ，w w w f t c o m ， w w w a s i a n u p d a t e t o m 等) 提供的實(shí)時(shí)數(shù)據(jù)，通過(guò)基于規(guī)則的方法，預(yù)測(cè)恒生等 指數(shù)的升斛1 8 j 。 國(guó)際方面，m o r g a n 、s t a n n l o g 等人已經(jīng)開(kāi)發(fā)了a i ( a u t o m a t e di n v e s t o r ) 系統(tǒng)。 2 第1 章緒論 該系統(tǒng)通過(guò)采用聚類(lèi)、可視化和預(yù)測(cè)技術(shù)來(lái)尋求最佳投資時(shí)機(jī)。d a l w as e c u r i t i e s 利用m a t l a b 強(qiáng)大的模擬仿真能力建立了一個(gè)有價(jià)證券管理系統(tǒng)，旨在分析 大量的證券數(shù)據(jù)。g o l a n r 和z i a r k o w w 應(yīng)用r o u g hs e t ( 粗糙集理論) 方法分析 了十年間股票的歷史數(shù)據(jù)，研究股票價(jià)格和經(jīng)濟(jì)指數(shù)之間的依賴(lài)關(guān)系，且所獲 得的預(yù)測(cè)規(guī)則得到了華爾街證券交易專(zhuān)家認(rèn)可。l o c k h e e dm a r t i n 公司的人工智 能中心開(kāi)發(fā)的r e c o n 系統(tǒng)，利用數(shù)據(jù)庫(kù)對(duì)數(shù)據(jù)集合進(jìn)行離散化、歸一化，然后 通過(guò)專(zhuān)家系統(tǒng)和先驗(yàn)知識(shí)獲得初始規(guī)則，并自動(dòng)分析、搜索數(shù)據(jù)庫(kù)對(duì)規(guī)則進(jìn)行 調(diào)整( 加入新規(guī)則，合并冗余規(guī)則) ，這個(gè)系統(tǒng)可用來(lái)輔助預(yù)測(cè)某種股票的趨勢(shì) 或判斷是否可能出現(xiàn)異常變化等【2 0 1 。 1 3 本文的研究?jī)?nèi)容 本文研究的主要內(nèi)容有以下幾點(diǎn)： 一、介紹了關(guān)聯(lián)規(guī)則技術(shù)在國(guó)內(nèi)外的研究發(fā)展及數(shù)據(jù)挖掘技術(shù)在股票預(yù)測(cè) 方面的應(yīng)用現(xiàn)狀，分析了應(yīng)用關(guān)聯(lián)規(guī)則挖掘技術(shù)進(jìn)行股票預(yù)測(cè)的重要意義。 二、闡述了數(shù)據(jù)挖掘的基本理論、主要技術(shù)，深入研究了關(guān)聯(lián)規(guī)則挖掘技 術(shù)，分析了經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法，指出了該算法存在的優(yōu)、缺點(diǎn)。 三、提出了一種基于比特向量和哈希項(xiàng)關(guān)聯(lián)規(guī)則挖掘優(yōu)化算法，將事務(wù)數(shù) 據(jù)庫(kù)轉(zhuǎn)換成比特向量表示形式，通過(guò)向量的與運(yùn)算來(lái)計(jì)算項(xiàng)集的支持度，在挖 掘過(guò)程中只需掃描一遍數(shù)據(jù)庫(kù)；運(yùn)用哈希技術(shù)，在第一次掃描數(shù)據(jù)庫(kù)的過(guò)程中， 直接生成頻繁2 項(xiàng)集，提高算法的執(zhí)行效率。 四、介紹了數(shù)據(jù)挖掘工具w e k a ，分析了w e k a 的源碼，e c l i p s e 平臺(tái)下實(shí)現(xiàn) 了關(guān)聯(lián)規(guī)則挖掘優(yōu)化算法的嵌入。 五、結(jié)合股票數(shù)據(jù)源文件的特點(diǎn)，設(shè)計(jì)股票預(yù)處理模塊并加以實(shí)現(xiàn)。 六、用改進(jìn)的w e k a 工具對(duì)股票數(shù)據(jù)進(jìn)行挖掘。在將關(guān)聯(lián)規(guī)則挖掘技術(shù)應(yīng) 用到股票數(shù)據(jù)分析中，詳細(xì)闡述了數(shù)據(jù)集、預(yù)處理、關(guān)聯(lián)規(guī)則挖掘的過(guò)程。對(duì) 生成的股票規(guī)則進(jìn)行了詳細(xì)分析，得出了對(duì)股票投資很有價(jià)值的結(jié)論。 1 4 本文組織結(jié)構(gòu) 本文的篇章結(jié)構(gòu)安排如下： 第1 章緒論 第1 章緒論，簡(jiǎn)述了數(shù)據(jù)挖掘研究的意義和技術(shù)背景、論文的選題依據(jù)、 研究背景以及主要的研究?jī)?nèi)容和文章篇章結(jié)構(gòu)安排。 第2 章數(shù)據(jù)挖掘理論，介紹了數(shù)據(jù)挖掘的概念、功能和步驟。 第3 章關(guān)聯(lián)規(guī)則挖掘技術(shù)，介紹了關(guān)聯(lián)規(guī)則挖掘的基本概念、分類(lèi)，深入 研究了關(guān)聯(lián)規(guī)則挖掘算法，對(duì)a p r i o r i 算法性能進(jìn)行分析。 第4 章股票預(yù)測(cè)知識(shí)，介紹了股票預(yù)測(cè)基礎(chǔ)與理論。 第5 章基于股票預(yù)測(cè)的特點(diǎn)關(guān)聯(lián)規(guī)則挖掘優(yōu)化算法，分析了股票事務(wù)數(shù)據(jù) 庫(kù)的特點(diǎn)，提出了一種應(yīng)用比特向量和哈希項(xiàng)的關(guān)聯(lián)規(guī)則優(yōu)化算法。并對(duì)算法 性能進(jìn)行了分析。 第6 章w e k a 平臺(tái)下的關(guān)聯(lián)規(guī)則挖掘算法實(shí)現(xiàn)，介紹了應(yīng)用w e k a 進(jìn)行關(guān) 聯(lián)規(guī)則挖掘過(guò)程，對(duì)w e k a 源碼分析 第7 章總結(jié)與展望，對(duì)本論文的研究進(jìn)行總結(jié)，討論了它的可取與不足之 處，展望了未來(lái)進(jìn)一步的研究工作。 4 第2 章數(shù)據(jù)挖掘理論 第2 章數(shù)據(jù)挖掘理論 2 1 數(shù)據(jù)挖掘基本概念 伴隨著數(shù)據(jù)獲取和存儲(chǔ)技術(shù)的提升，人類(lèi)生活的各個(gè)領(lǐng)域都隨之產(chǎn)生了大 量的大型數(shù)據(jù)庫(kù)。例如超級(jí)市場(chǎng)的交易數(shù)據(jù)、信用卡的使用記錄、通信行業(yè)的 交通記錄、股票市場(chǎng)的交易數(shù)據(jù)等。如何處理這些海量數(shù)據(jù)，如何從這些存儲(chǔ) 了海量數(shù)據(jù)的數(shù)據(jù)庫(kù)中提取出對(duì)我們有用的信息，成為我們面臨的一個(gè)主要問(wèn) 題，數(shù)據(jù)挖掘技術(shù)正是針對(duì)這種需求應(yīng)運(yùn)而生。 人們把原始數(shù)據(jù)看作是形成知識(shí)的源泉，就像從礦石中采礦一樣。原始數(shù) 據(jù)可以是結(jié)構(gòu)化的，如關(guān)系型數(shù)據(jù)庫(kù)中的數(shù)據(jù)，也可以是半結(jié)構(gòu)化的，如文本、 圖形、圖像數(shù)據(jù)，甚至是分布在網(wǎng)絡(luò)上的異構(gòu)型數(shù)據(jù)。發(fā)現(xiàn)知識(shí)的方法可以是 數(shù)學(xué)的，也可以是非數(shù)學(xué)的：可以是演繹的，也可以是歸納的。發(fā)現(xiàn)了的知識(shí)可 以被用于信息管理、查詢(xún)優(yōu)化、決策支持、過(guò)程控制等，還可以用于數(shù)據(jù)自身 的維護(hù)。 數(shù)據(jù)挖掘的定義在學(xué)術(shù)界一直存在一定的爭(zhēng)議，沒(méi)有一個(gè)完全統(tǒng)一的精確 定義，針對(duì)本文的應(yīng)用研究，數(shù)據(jù)挖掘引用如下的定義：數(shù)據(jù)挖掘( d a t am i n i n g ) 就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中發(fā)現(xiàn)提 取隱含在其中的、人們事先未知的、但又是潛在有用信息和知識(shí)的非平凡過(guò)程 【4 】。 2 2 數(shù)據(jù)挖掘功能 數(shù)據(jù)挖掘任務(wù)一般可以分為兩類(lèi)：描述與預(yù)測(cè)。描述性挖掘刻劃數(shù)據(jù)庫(kù)中數(shù) 據(jù)的一般特性。預(yù)測(cè)性挖掘在當(dāng)前數(shù)據(jù)上進(jìn)行推斷，以進(jìn)行預(yù)測(cè)。數(shù)據(jù)挖掘通 過(guò)預(yù)測(cè)未來(lái)趨勢(shì)及行為，做出前瞻性的、基于知識(shí)的決策。數(shù)據(jù)挖掘的目標(biāo)是 從數(shù)據(jù)庫(kù)中發(fā)現(xiàn)隱含的、有意義的知識(shí)，主要有以下六類(lèi)功能1 4 j ： ( 1 ) 概念類(lèi)描述。概念描述就是對(duì)某類(lèi)對(duì)象的內(nèi)涵進(jìn)行描述，并概括這類(lèi)對(duì) 象的有關(guān)特征。概念描述分為特征性描述和區(qū)別性描述，前者描述某類(lèi)對(duì)象的 第2 章數(shù)據(jù)挖掘理論 共同特征，后者描述不同類(lèi)對(duì)象之間的區(qū)別。 ( 2 ) 分類(lèi)與預(yù)測(cè)。分類(lèi)指的是從數(shù)據(jù)庫(kù)中選出類(lèi)標(biāo)號(hào)已知的訓(xùn)練集，對(duì)該訓(xùn) 練集運(yùn)用數(shù)據(jù)挖掘的分類(lèi)技術(shù)，建立分類(lèi)模型，利用該模型對(duì)類(lèi)標(biāo)號(hào)未知的數(shù) 據(jù)進(jìn)行分類(lèi)。預(yù)測(cè)與分類(lèi)類(lèi)似，不同之處在于，分類(lèi)處理的是離散型變量，而 預(yù)測(cè)處理的是連續(xù)型變量。 ( 3 ) 關(guān)聯(lián)分析。若兩個(gè)或多個(gè)變量的取值之間存在某種規(guī)律性，就稱(chēng)為關(guān)聯(lián)。 關(guān)聯(lián)可分為簡(jiǎn)單關(guān)聯(lián)、時(shí)序關(guān)聯(lián)、因果關(guān)聯(lián)。關(guān)聯(lián)分析的目的是找出數(shù)據(jù)庫(kù)中 隱藏的關(guān)聯(lián)網(wǎng)，從而決定哪些事情將一起或按順序發(fā)生。 ( 4 ) 聚類(lèi)分析。聚類(lèi)是將數(shù)據(jù)對(duì)象分組成多個(gè)類(lèi)或簇，在同一個(gè)簇中的對(duì)象 具有較高的相似度，而不同簇中的對(duì)象差別較大。聚類(lèi)和分類(lèi)的區(qū)別是聚類(lèi)不 依賴(lài)于預(yù)先定義好的類(lèi)，不需要訓(xùn)練集。 ( 5 ) 孤立點(diǎn)分析。在大量數(shù)據(jù)中可能包含一些數(shù)據(jù)對(duì)象，這些數(shù)據(jù)與數(shù)據(jù)的 一般行為或模型不一致，這些數(shù)據(jù)對(duì)象成為孤立點(diǎn)。通常這些數(shù)據(jù)對(duì)象被視為 噪聲或異常而丟棄，但有時(shí)候這種數(shù)據(jù)很有用( 如在信用卡欺騙檢測(cè)中，以付款 數(shù)額特別大來(lái)發(fā)現(xiàn)信用卡的欺騙性使用) 。 ( 6 ) 演變分析。數(shù)據(jù)演變分析描述行為隨時(shí)間變化的對(duì)象的規(guī)則或趨勢(shì)，并 對(duì)其建模。演變分析包括時(shí)間序列數(shù)據(jù)分析、周期模式匹配和基于相似性的數(shù) 據(jù)分析。 2 3 數(shù)據(jù)挖掘的步驟 一般而言，數(shù)據(jù)挖掘過(guò)程分為四步1 5 l ： ( 1 ) 數(shù)據(jù)準(zhǔn)備( d a t ar e p a r a t i o n ) ：數(shù)據(jù)準(zhǔn)備包括數(shù)據(jù)集成( d a t ai n t e g r a t i o n ) 和數(shù) 據(jù)選擇與預(yù)分析( d a t as e l e c t i o na n dp r e a n a l y s i s ) 。通過(guò)數(shù)據(jù)集成，從操作環(huán)境 中提取并集成數(shù)據(jù)，解決語(yǔ)義二義性問(wèn)題，消除臟數(shù)據(jù)等。數(shù)據(jù)選擇和預(yù)分析 縮小數(shù)據(jù)范圍，提高數(shù)據(jù)挖掘的質(zhì)量。 ( 2 ) 挖掘( m i n i n g ) ：利用數(shù)據(jù)挖掘方法分析數(shù)據(jù)庫(kù)中的數(shù)據(jù)。 ( 3 ) 表述( p r e s e n t a t i o n ) 。將挖掘獲取的信息以便于用戶(hù)理解和觀察的方式反 映給用戶(hù)。 ( 4 ) 評(píng)價(jià)( a s s e s s ) 。評(píng)定分析結(jié)果的滿(mǎn)意程度。 可用圖2 1 流程圖【5 】表示。 6 第2 章數(shù)據(jù)挖掘理論 卜一i 鼉囊參斗t 曩拓箍- 一嬙肇曩承羞群捧一 躅2 1 數(shù)據(jù)挖獬金過(guò)稷 7 第3 章關(guān)聯(lián)規(guī)則挖掘技術(shù) 3 1 關(guān)聯(lián)規(guī)則挖掘 第3 章關(guān)聯(lián)規(guī)則挖掘技術(shù) 關(guān)聯(lián)規(guī)則挖掘( a s s o c i a t i o nr u l em i n i n g ) 是數(shù)據(jù)挖掘研究中的一個(gè)重要分 支，關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的眾多知識(shí)類(lèi)型中最為典型的一種。該問(wèn)題是a g r a w a l 等在19 9 3 年在對(duì)市場(chǎng)購(gòu)物籃問(wèn)題( m a r k e tb a s k e ta n a l y s i s ) 進(jìn)行分析后首次提出 的，用以發(fā)現(xiàn)商品銷(xiāo)售中的顧客購(gòu)買(mǎi)模式。購(gòu)物籃問(wèn)題源于這樣一個(gè)普通的例 子：美國(guó)加州某個(gè)超級(jí)連鎖店對(duì)記錄著每天銷(xiāo)售信息和顧客基本情況的數(shù)據(jù)庫(kù) 中的數(shù)據(jù)進(jìn)行分析，發(fā)現(xiàn)在下班后前來(lái)購(gòu)買(mǎi)嬰兒尿布的顧客多數(shù)是男性，而且 往往也同時(shí)購(gòu)買(mǎi)啤酒。于是這個(gè)連鎖店的經(jīng)理當(dāng)機(jī)立斷，重新布置貨架，把啤 酒類(lèi)商品布置在嬰兒尿布貨架附近，并在二者之間放上土豆之類(lèi)的佐酒小食品， 同時(shí)把男士們的日常生活用品也就近布置。這樣一來(lái)，上述幾種商品的銷(xiāo)量大 大增加了。 關(guān)聯(lián)規(guī)則挖掘可以發(fā)現(xiàn)交易數(shù)據(jù)庫(kù)中項(xiàng)目( i t e m s ) 或?qū)傩? a t t r i b u t e s ) 之間的 有趣聯(lián)系，這些聯(lián)系是預(yù)先未知的，不能通過(guò)數(shù)據(jù)庫(kù)的邏輯操作( 如表的聯(lián)接) 或統(tǒng)計(jì)的方法得出。這說(shuō)明它們不是基于數(shù)據(jù)自身的固有屬性( 如函數(shù)依賴(lài)關(guān) 系) ，而是基于數(shù)據(jù)項(xiàng)目的同時(shí)出現(xiàn)的特征。關(guān)聯(lián)規(guī)則的特點(diǎn)是形式簡(jiǎn)潔、易于 解釋和理解，并可以有效地捕捉數(shù)據(jù)間的重要關(guān)系。最為典型的例子是“在購(gòu) 買(mǎi)面包的顧客中有8 0 也購(gòu)買(mǎi)了黃油 。大型商場(chǎng)和超市的數(shù)據(jù)庫(kù)中保存了大 量的顧客的購(gòu)買(mǎi)信息，從中發(fā)掘黃油一面包這類(lèi)有趣的關(guān)聯(lián)關(guān)系，可以指導(dǎo)商 家制定正確的銷(xiāo)售決策，又如通過(guò)交叉購(gòu)物、賤賣(mài)分析、目錄設(shè)計(jì)、商品陳列 等，使他們?cè)谑袌?chǎng)競(jìng)爭(zhēng)中取得更大的主動(dòng)權(quán)。其實(shí)，關(guān)聯(lián)規(guī)則的應(yīng)用不僅僅局 限于市場(chǎng)菜籃分析，它有著廣泛的應(yīng)用領(lǐng)域，如商業(yè)與金融、人口普查數(shù)據(jù)分 析、工程技術(shù)數(shù)據(jù)分析、醫(yī)療、財(cái)政、宏觀決策支持、電子商務(wù)、網(wǎng)站設(shè)計(jì)互 聯(lián)網(wǎng)等等。理論上講，關(guān)聯(lián)規(guī)則挖掘是指從一個(gè)大型的數(shù)據(jù)集( d a t as e t ) 中發(fā)現(xiàn) 有趣的關(guān)聯(lián)( a s s o c i a t i o n ) 或相關(guān)( c o r r e l a t i o n ) 關(guān)系，即從數(shù)據(jù)集中識(shí)別出頻繁出現(xiàn) 的屬性值集( s e t so f a t t r i b v a l u e ) ，也稱(chēng)為頻繁項(xiàng)集( f r e q u e n ti t e m s e t s ，簡(jiǎn)稱(chēng)頻繁 集) ，然后再利用這些頻繁集創(chuàng)建描述關(guān)聯(lián)關(guān)系的規(guī)則的過(guò)程【5 】。 8 第3 章關(guān)聯(lián)規(guī)則挖掘技術(shù) 3 2 關(guān)聯(lián)規(guī)則挖掘基本概念 關(guān)聯(lián)規(guī)則的挖掘是對(duì)給定的一個(gè)交易數(shù)據(jù)庫(kù)d ，求出所有滿(mǎn)足最小支持度 和最小置信度的關(guān)聯(lián)規(guī)則的過(guò)程。該問(wèn)題可分解為兩個(gè)子問(wèn)題( 1 ) 根據(jù)給定的最 小支持度，按項(xiàng)目數(shù)自小而大的順序找出數(shù)據(jù)d 中頻繁項(xiàng)目集；( 2 ) 根據(jù)頻繁項(xiàng) 目集和指定的最小置信度生成關(guān)聯(lián)規(guī)則。 設(shè)有i = i l ，i 2 ，i m ) 是由m 個(gè)不同的項(xiàng)組成的集合。給定一個(gè)事務(wù)數(shù)據(jù) 庫(kù)d ，其中每一個(gè)事務(wù)t 是i 中一組項(xiàng)的集合，即t c i ，t 有一個(gè)唯一的標(biāo)識(shí) 符t i d 。若項(xiàng)集a c i 且a ct ，則稱(chēng)事務(wù)t 包含項(xiàng)集a 。如果項(xiàng)集a 中包含 k 個(gè)項(xiàng)，則稱(chēng)為k 項(xiàng)集【l j 。 定義3 1 ：關(guān)聯(lián)規(guī)則是形如a b 的蘊(yùn)涵式，其中a ci ，b c i ，a nb = 。關(guān)聯(lián)規(guī)則a j b 在事務(wù)數(shù)據(jù)庫(kù)d 中成立，具有支持度s ，其中s 是d 中事 務(wù)包a u b 的百分比，記作：s u p p o r t ( a j b ) = p ( a u b ) 。通常用戶(hù)指定最小支持 度，記為m i n s u p i i j 。 定義3 2 ：關(guān)聯(lián)規(guī)則a jb 在事務(wù)數(shù)據(jù)庫(kù)d 中的置信度是d 中包含a 的 事務(wù)同時(shí)也包含b 的百分比，它是條件概率p ( bla ) ，記 作：c o n f i d e n c e ( a j b ) = p ( bia ) 。通常用戶(hù)指定最小置信度，記為m i n c o n f 【l j 。 定義3 3 ： 若s u p p o a ( a = b ) m i n s u p ，且c o n f i d e n c e ( a = b ) 一m i n c o n f , 則稱(chēng)關(guān)聯(lián)規(guī)則a j b 為強(qiáng)關(guān)聯(lián)規(guī)則【l j 。 定義3 4 ： 如果一個(gè)項(xiàng)目集a 滿(mǎn)足最小支持度闡值m i n s u p ，即s u p p o r t ( a ) ， m i n s u p ，則稱(chēng)它為頻繁項(xiàng)集( f r e q u e n ti t e m s e t ) 。頻繁k - 項(xiàng)集通常記為l k 。反 之，如果一個(gè)項(xiàng)目集a 不滿(mǎn)足最小支持度，則稱(chēng)為非頻繁項(xiàng)集。 定義3 5 ：候選項(xiàng)集是潛在的頻繁項(xiàng)集，是頻繁k 1 項(xiàng)集的超集( s u p e r s e t ) ， 含有k 項(xiàng)的候選項(xiàng)集表示為c k ，由它構(gòu)成頻繁k 項(xiàng)集l k 。 定義3 6 ：如果事務(wù)數(shù)據(jù)庫(kù)d 中有e 的事務(wù)支持項(xiàng)集b ，e 稱(chēng)為關(guān)聯(lián)規(guī) 則a j b 的期望可信度( e x p e c t e dc o n f i d e n c e ) 。期望可信度描述了在沒(méi)有任何條 件影響時(shí)，項(xiàng)集b 在所有事務(wù)中出現(xiàn)的概率有多大。如果某天共有1 0 0 0 個(gè)顧 客到商場(chǎng)購(gòu)買(mǎi)物品，其中有2 0 0 個(gè)顧客購(gòu)買(mǎi)了黃油，則上述的關(guān)聯(lián)規(guī)則的期望 可信度就是2 0 。 定義3 7 ：作用度( 1 i f t ) 是可信度與期望可信度的比值。作用度描述項(xiàng) 集a 的出現(xiàn)對(duì)項(xiàng)集b 的出現(xiàn)有多大影響。因?yàn)轫?xiàng)集b 在所有事務(wù)中出現(xiàn)的概率 9 第3 章關(guān)聯(lián)規(guī)則挖掘技術(shù) 是期望可信度；而項(xiàng)集a 在項(xiàng)集a 出現(xiàn)的事務(wù)中出現(xiàn)的概率是可信度，通過(guò)可 信度對(duì)期望可信度的比值反映了在加入“項(xiàng)集a 出現(xiàn)”的這個(gè)條件后，項(xiàng)集b 的出現(xiàn)概率發(fā)生了多大的變化。 關(guān)聯(lián)規(guī)則挖掘的任務(wù)就是在數(shù)據(jù)庫(kù)中挖掘出所有強(qiáng)關(guān)聯(lián)規(guī)則。即在事務(wù)數(shù) 據(jù)庫(kù)中找出所有具有用戶(hù)給定的最小支持度m i n s u p 和最小置信度m i n c o f 的關(guān) 聯(lián)規(guī)則。這樣，每一條被挖掘出來(lái)的關(guān)聯(lián)規(guī)則就可以用一個(gè)蘊(yùn)含式，兩個(gè)閥值 唯一標(biāo)識(shí)。 置信度是對(duì)關(guān)聯(lián)規(guī)則正確程度的衡量，表示規(guī)則的強(qiáng)度；支持度是對(duì)關(guān)聯(lián)規(guī) 則重要性的衡量，表示規(guī)則的頻度。規(guī)則的支持度說(shuō)明它在所有事務(wù)中有多大 的代表性，其值越大，關(guān)聯(lián)規(guī)則越重要。如果關(guān)聯(lián)規(guī)則的置信度很高，但支持 度很低，說(shuō)明該關(guān)聯(lián)規(guī)則實(shí)用機(jī)會(huì)很小；如果支持度很高，而置信度很低，則 說(shuō)明該規(guī)則不可靠。 例如，在購(gòu)物籃分析中，購(gòu)買(mǎi)計(jì)算機(jī)也趨向于同時(shí)購(gòu)買(mǎi)財(cái)務(wù)管理軟件可以 用以下關(guān)聯(lián)規(guī)則表示： c o m p u t e rj f i n a n c i a l _ m a n a g e m e n t _ s o f t w a r e s u p p o r t = 2 ，c o n f i d e u c e 2 6 0 】 ( 3 1 ) 上述規(guī)則中s u p p o r t = 2 表示所有事務(wù)中有2 的顧客同時(shí)購(gòu)買(mǎi)計(jì)算機(jī)和財(cái) 務(wù)管理軟件；c o n f i d e u c e = 6 0 表示購(gòu)買(mǎi)計(jì)算機(jī)的顧客中6 0 的顧客也購(gòu)買(mǎi)了財(cái) 務(wù)軟件。 置信度是對(duì)關(guān)聯(lián)規(guī)則的準(zhǔn)確度的衡量，支持度是對(duì)關(guān)聯(lián)規(guī)則重要性( 或適 用范圍) 的衡量。支持度說(shuō)明了這條規(guī)則在所有事務(wù)中有多大的代表性，顯然支 持度越大，關(guān)聯(lián)規(guī)則越重要，應(yīng)用越廣泛。 期望置信度描述了在沒(méi)有項(xiàng)集a 的作用下，項(xiàng)集b 本身的支持度，作用度 描述了項(xiàng)集a 對(duì)項(xiàng)集b 的影響力的大小。作用度越大，說(shuō)明項(xiàng)集b 受項(xiàng)集a 的影響越大。一般情況，有用的關(guān)聯(lián)規(guī)則的作用度都應(yīng)該大于1 ，只有關(guān)聯(lián)規(guī) 則的可信度大于期望可信度，才說(shuō)明a 的出現(xiàn)對(duì)b 的出現(xiàn)有促進(jìn)作用，也說(shuō)明 了它們之間的某種程度相關(guān)性；如果作用度不大于l ，則關(guān)聯(lián)規(guī)則也就沒(méi)有意義 了。綜合如表3 1 l o 第3 章關(guān)聯(lián)規(guī)則挖掘技術(shù) 表3 1 關(guān)聯(lián)規(guī)則參數(shù)( t h ep a r a m e t e ro fa s s o c i a t i o nr u l e s ) 名稱(chēng)描述 公式 置信度在項(xiàng)集a 出現(xiàn)的前提下，b 出現(xiàn)的概率p ( bia ) 支持度項(xiàng)集a 、b 同時(shí)出現(xiàn)的概率 p ( a u b ) 期望置信度項(xiàng)集b 出現(xiàn)的概率 p ( b ) 作用度可信度對(duì)期望可信度的比值 p ( bia ) p ( b ) 3 3 關(guān)聯(lián)規(guī)則的分類(lèi) 根據(jù)不同的標(biāo)準(zhǔn)，關(guān)聯(lián)規(guī)則有多種分類(lèi)方法： ( 1 ) 根據(jù)規(guī)則中所處理的值類(lèi)型。 如果規(guī)則考慮的關(guān)聯(lián)是項(xiàng)的在與不在，則它是布爾關(guān)聯(lián)規(guī)則b o o l e a n a s s o c i a t i o nr u l e ) ，例如規(guī)則3 2 c o m p u t e rjf i n a n c i a l _ m a n a g e m e n t _ s o f t w a r e s u p p o r t = 2 ，c o n f i d e u c e 2 6 0 】 ( 3 2 ) 如果規(guī)則描述的是量化的項(xiàng)或?qū)傩灾g的關(guān)系，則它是量化關(guān)聯(lián)規(guī)則 ( q u a n t i t a t i v ea s s o c i a t i o nr u l e ) 。在這種規(guī)則中項(xiàng)或?qū)傩缘牧炕祫澐譃閰^(qū)間，例 如規(guī)則( 3 3 ) a g e ( x , 3 0 3 9 ”) a i n c o m e ( x , 4 2 k 4 8 i ( ) j b u y s ( x ，“h i g h _ r e s _ t v ”) ( 3 3 ) 其中量化屬性a g e 和i n c o m e 已經(jīng)離散化，x 代表顧客。 ( 2 ) 根據(jù)規(guī)則中涉及的數(shù)據(jù)維。 如果規(guī)則的項(xiàng)或?qū)傩悦總€(gè)只涉及一個(gè)維，則它是單維關(guān)聯(lián)規(guī)貝j ( s i n g l e d i m e n s i o n a la s s o c i a t i o nr u l e ) ，例如規(guī)貝l l ( 3 4 ) b u y s ( x ，c o m p u t e r ) b u y s ( x ，f i n a n c i a lm a n a g e m e n t _ s o f t w a r e ) ( 3 4 ) 它是單維關(guān)聯(lián)規(guī)則，因?yàn)樗簧婕耙粋€(gè)維b u y s 。 如果規(guī)則中涉及兩個(gè)或多個(gè)維，則它是多維關(guān)聯(lián)規(guī)則( m u l t id i m e n s i o n a l a s s o c i a t i o nr u l e ) ，例如規(guī)貝j j ( 3 3 ) 就是一個(gè)多維關(guān)聯(lián)規(guī)則，因?yàn)樗婕叭齻€(gè)維a g e ， i n c o m e 和b u y s 。 第3 章關(guān)聯(lián)規(guī)則挖掘技術(shù) ( 3 ) 根據(jù)規(guī)則集所涉及的抽象層。 有些挖掘關(guān)聯(lián)規(guī)則方法可以在不同的抽象層發(fā)現(xiàn)規(guī)則。例如，假定挖掘的 關(guān)聯(lián)規(guī)則集包含下面規(guī)則： a g e ( ) ( ，“3 0 3 9 ”) jb u y s ( x ，“l(fā) a p t o pc o m p u t e r ”) ( 3 5 ) a g e ( x ，“3 0 3 9 ”) jb u y s ( x , c o m p u t e r ”) ( 3 6 ) 在規(guī)則( 3 5 ) 和( 3 6 ) 中，購(gòu)買(mǎi)的商品涉及不同的抽象層( 即“c o m p u t e r 在比 “l(fā) a p t o pc o m p u t e r 高的抽象層) 。稱(chēng)所挖掘的規(guī)則集由多層關(guān)聯(lián)規(guī)貝, 1 ( m u l t i l e v e l a s s o c i a t i o nr u l e ) 組成。反之，如果在給定的規(guī)則集中，規(guī)則不涉及不同抽象層的 項(xiàng)或?qū)傩?，則該集合包含單層關(guān)聯(lián)規(guī)貝l j ( s i n g l el e v e la s s o c i a t i o nr u l e ) 。 3 4 關(guān)聯(lián)規(guī)則挖掘算法 關(guān)聯(lián)規(guī)則挖掘算法實(shí)現(xiàn)可以分解為兩個(gè)子問(wèn)題的求解： 1 求出數(shù)據(jù)庫(kù)d 中滿(mǎn)足最小支持度m i n s u p 的所有頻繁項(xiàng)目集。 2 利用頻繁項(xiàng)目集生成所有關(guān)聯(lián)規(guī)則。 其中子問(wèn)題2 的解決方法較為簡(jiǎn)單，對(duì)每個(gè)頻繁項(xiàng)目集l ，對(duì)x 的每個(gè)非 空子集a ，考察規(guī)則a j ( l a ) ，如果該規(guī)則滿(mǎn)足最小支持度和最小信任度則輸 出此規(guī)則。子問(wèn)題1 的求解是關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的關(guān)鍵部分。 1 9 9 3 年r a g r w a a l 等人提出的a p r i o d 算法【1 1 ，該算法是一種挖掘布爾關(guān)聯(lián) 規(guī)則頻繁項(xiàng)集的算法。該算法是基于以下兩個(gè)事實(shí)： 1 如果項(xiàng)目集l 是頻繁項(xiàng)目集，則l 的任一非空子集也必定是頻繁項(xiàng)目 集。 2 如果項(xiàng)目集不是頻繁l 項(xiàng)目集，則l 的任何超集也必定不是頻繁項(xiàng)目集。 3 4 1 候選項(xiàng)集找頻繁項(xiàng)的算法a p r i o r i 算法 討論a p r i o d 算法前要先明確一些符號(hào)的意義，如表3 2 所示。a p r i o d 算法 主要利用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)，使用一種稱(chēng)為逐層搜索的迭代方法來(lái)找出 所有的頻繁項(xiàng)集。其主要步驟如下： 1 產(chǎn)生所有的頻繁1 項(xiàng)集的集合l l 。掃描數(shù)據(jù)庫(kù)d ，對(duì)每個(gè)事務(wù)的數(shù)據(jù) 項(xiàng)進(jìn)行處理。若該數(shù)據(jù)項(xiàng)第1 次出現(xiàn)，則將其加入候選1 項(xiàng)集的集合c l 中，并 將它的計(jì)數(shù)值設(shè)為l 若該數(shù)據(jù)項(xiàng)已在c l 中，則將它的計(jì)數(shù)值加上1 。數(shù)據(jù)庫(kù)事 1 2 第3 章關(guān)聯(lián)規(guī)則挖掘技術(shù) 務(wù)掃描完后得到所有的候選1 項(xiàng)集。將c l ，中所有計(jì)數(shù)值小于m i n s u p 的項(xiàng)集 刪除，就得到了頻繁1 一項(xiàng)集的集合l l 。 2 通過(guò)l k - i 與自己連接產(chǎn)生候選k - 項(xiàng)集的集合c k 。對(duì)于任意的l l l k 1 和 1 2 l k - i 若 i l 【l 】= 1 2 【l 】) 八( 1 l 2 】爿2 2 】) a ( 1 t 啡一2 = 1 2 k 一2 a l l 【k 一1 m i n s u p ) 滿(mǎn)足最小支持度形成頻繁項(xiàng)集 ( 1 0 ) ) ( 1 1 ) r e t u r nl = u kl k o 算法二：產(chǎn)生頻繁1 項(xiàng)集函數(shù) f i n d _ f r e q u e n t _ l i t e m s e t s ( d ：t r a n s a c t i o nd a t a b a s e ) ( 1 ) f o re a c hi t e m s e ti k d ( 2 ) i f i kc o u n t m i n _ s u p ( 3 ) a d di kt ol 1 算法三：通過(guò)( k 1 ) 頻繁項(xiàng)目集產(chǎn)生k 項(xiàng)候選項(xiàng)集 a p r i o r i g e n ( l k 1 ：f r e q u e n t _ ( k - 1 ) 一i t e m s e t s ( d ) ；m i n _ s u p ) ( 1 ) f o re a c hi t e m s e ti i l r 1 ( 2 ) f o re a c hi t e m s e t1 2 l k - i ( 3 ) i f ( 1 1 【l 】= 1 2 【1 】) 八( 1 l 【2 】= 1 2 【2 】) 八八( 1 1 k - 2 1 2 1 2 k 一2 】) 八l l k 一1 。其中 c ，d ) 不是頻 繁2 項(xiàng)集l 2 的元素。因而該候選項(xiàng)必定不是頻繁的。把 a ，b ，d ) 從c 3 刪除。 ( 6 ) 候選項(xiàng) b ，c ，e 的2 - 項(xiàng)子集是 b ，c ) ， c ，e ) ， b ，e ) 。其中 c ，e ) 不是頻繁 2 項(xiàng)集l 2 的元素。因而該候選項(xiàng)必定不是頻繁的。把 a ，b ，d ) 從c 3 刪除。 ( 7 ) 候選項(xiàng) b ，d ，e 的2 一項(xiàng)子集是 b ，d ， d ，e ， b ，e 。其中 d ，e ) 不是頻 繁2 一項(xiàng)集l 2 的元素。因而該候選項(xiàng)必定不是頻繁的。把 a ，b ，d ) 從c 3 刪除。 最后得n - - 個(gè)候選項(xiàng)，如表3 1 0 表3 1 0 剪枝后的候選3 一項(xiàng)集i 。 掃描事務(wù)數(shù)據(jù)庫(kù)d ，對(duì)每個(gè)候選項(xiàng)計(jì)數(shù)，如表3 1 1 所示： 表3 1 1 頻繁3 一項(xiàng)集計(jì)數(shù) 把候選項(xiàng)集集合c 2 的支持度與最小支持度m i n s u p = 2 進(jìn)行比較，得到頻繁 3 項(xiàng)集l 3 如表3 1 2 所示。 1 8 第3 章關(guān)聯(lián)規(guī)則挖掘技術(shù) 表3 1 2 頻繁3 一項(xiàng)集l 3 項(xiàng)集 支持度計(jì)數(shù) a ，b ，c 2 a ，1 3 ，e 2 使用i i 。1 2 連接，產(chǎn)生候選4 - 項(xiàng)集 a ，b ，c ，e ，該項(xiàng)集的一個(gè)子集 b ，c ，e 不 是頻繁3 項(xiàng)集l 3 的元素。因而該候選項(xiàng)必定不是頻繁的。把 a ，b ，c ，e 從c 4 刪 除。c 4 = c i ) ，算法停止。找出了所有的頻繁項(xiàng)集。 3 4 2 a p r i o r i 算法性能分析 a p f i o f i 作為經(jīng)典的頻繁項(xiàng)集生成算法，在關(guān)聯(lián)規(guī)則研究中具有里程碑的作 用。雖然a p f i o f i 算法能找出所有的頻繁項(xiàng)集，其侯選“產(chǎn)生一檢查方法大幅 度壓縮了候選項(xiàng)集的大小，提高了算法的效率。然而，其缺點(diǎn)還是比較突出的， 主要在以下幾方面： ( 1 ) a p r i o r i 算法會(huì)產(chǎn)生大量的候選項(xiàng)集。由于剪枝的作用，產(chǎn)生的候選3 項(xiàng)集以后的候選項(xiàng)數(shù)會(huì)減少。但生成候選2 項(xiàng)集時(shí)，產(chǎn)生的候選項(xiàng)數(shù)仍比較龐 大，如有1 0 4 個(gè)頻繁1 項(xiàng)集，會(huì)產(chǎn)生多達(dá)1 0 7 個(gè)候選2 項(xiàng)集。因此，該算法適 合于最大頻繁項(xiàng)目集相對(duì)較小的數(shù)據(jù)集中的關(guān)聯(lián)規(guī)則挖掘問(wèn)題。 ( 2 ) 在每個(gè)循環(huán)中事務(wù)集的個(gè)數(shù)也將影響整個(gè)算法的效率，在數(shù)據(jù)量比較大 的時(shí)候問(wèn)題尤其突出，如何縮短每一次循環(huán)中的事務(wù)集也需要進(jìn)一步改進(jìn)。反 映在上面的算法中，主要是體現(xiàn)在利用c k 生成l k 時(shí)，效率較低，而且為了計(jì) 算c k 中每個(gè)候選元素的支持度，不得不利用事務(wù)數(shù)據(jù)庫(kù)d 中的所有事務(wù)來(lái)比 較一次；并且每循環(huán)一次就得重新比較一次，這樣這個(gè)算法的時(shí)間復(fù)雜度增加， 效率降低了。 ( 3 ) l k 1 自連接生成c k 產(chǎn)生大量的時(shí)間開(kāi)銷(xiāo)。 3 4 3 由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則 產(chǎn)生頻繁項(xiàng)集后，可由他們產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，強(qiáng)關(guān)聯(lián)規(guī)則就是滿(mǎn)足最小支 持度和最小置信度。最小置信度可用下面公式計(jì)算： s u p p o r t _ c o u n t ( aub ) c o n f i d e n c e ( ajb ) = p ( aib ) 2 面鬲再面萬(wàn) ( 3 7 ) 1 9 第3 章關(guān)聯(lián)規(guī)則挖掘技術(shù) 其中s u p p o r t _ e o u n t ( a u b ) 是含項(xiàng)集a u b 的事務(wù)數(shù)，s u p p o r t _ e o u n t ( a ) 是 包含項(xiàng)集a 的事務(wù)數(shù)。 產(chǎn)生關(guān)聯(lián)規(guī)則的具體步驟如下： ( 1 ) 對(duì)每個(gè)頻繁項(xiàng)集l ，產(chǎn)生l 的所有非空子集。 工1 梧 j b 六2 隹擊。田supportcount(aub ) m i n c o n f ( 2 v 4 于l 的每個(gè)非空子集s ，如果面品磊五五萬(wàn)n 1 ， 則輸出規(guī)則s j ( 1 - s ) 。m i n c o n f 表示最小置信度閥值。 以上例得出的頻繁3 項(xiàng)l = a ，b ，e ) ，說(shuō)明可以產(chǎn)生哪些關(guān)聯(lián)規(guī)則： l 的非空子集有 a ，b ) ， a ，e ) ， b ，e ) ， a ) ， b ) ， e 。產(chǎn)生的關(guān)聯(lián)規(guī)則有 ( 1 ) a 入bjec o n f i d e n c e = 2 4 = 5 0 ( 2 ) a 入e j ec o r t f i d e n c e = 2 2 = 1 0 0 ( 3 ) b 八e j ac o r t f i d e n c e = 2 2 = 1 0 0 ( 4 ) a j e 八bc o n f i d e n c e = 2 6 = 3 3 ( 5 ) b j a 八ec o r t f i d e n c e = 2 7 = 2 9 ( 6 ) e j a 八bc o n f i d e n c e = 2 2 = 1 0 0 如果設(shè)最小置信度閥值為7 0 。則輸出的強(qiáng)關(guān)聯(lián)規(guī)則是2 、3 、6 。 第4 章股票預(yù)測(cè)知識(shí) 第4 章股票預(yù)測(cè)知識(shí) 4 1 股市影響因素分析 股票市場(chǎng)價(jià)格波動(dòng)是股市運(yùn)行的基礎(chǔ)，也是股票投資者關(guān)注的焦點(diǎn)。股價(jià) 的波動(dòng)受各種經(jīng)濟(jì)因素和非經(jīng)濟(jì)因素的影響，分析這些因素的影響，可為投資 者做出正確的投資決策提供一定的依據(jù)。雖然影響股價(jià)波動(dòng)的因素很多，但股 價(jià)有其內(nèi)在價(jià)值，股價(jià)圍繞其內(nèi)在價(jià)值波動(dòng)，內(nèi)在價(jià)值決定論是基本分析法的 基礎(chǔ)；股價(jià)隨投資者對(duì)各種因素的心理預(yù)期的變化而波動(dòng)，心理預(yù)期理論是技術(shù) 分析的基礎(chǔ)；股價(jià)波動(dòng)是各種因素形成合力作用的結(jié)果。 影響股票價(jià)格的因素比較多，可根據(jù)內(nèi)容和性質(zhì)分為宏觀因素、微觀經(jīng)濟(jì) 因素、市場(chǎng)因素和非經(jīng)濟(jì)因素等四個(gè)方面。 1 宏觀經(jīng)濟(jì)因素 宏觀經(jīng)濟(jì)因素從不同的方向直接或間接地影響到公司的經(jīng)營(yíng)及股票的獲利 能力和資本的增值，從不同的側(cè)面影響居民收入和心理預(yù)期，而對(duì)股市的供求 產(chǎn)生相當(dāng)大的影響。宏觀經(jīng)濟(jì)因素包括：經(jīng)濟(jì)周期、通貨變動(dòng)、國(guó)際貿(mào)易支出、 國(guó)際收入、利率、財(cái)政政策、產(chǎn)業(yè)政策、監(jiān)督政策等方面。 2 微觀經(jīng)濟(jì)因素 在影響股價(jià)波動(dòng)微觀經(jīng)濟(jì)因素中