畢業(yè)論文--基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘.doc

內(nèi)蒙古科技大學(xué)畢業(yè)論文 I 內(nèi)蒙古科技大學(xué) 本科生畢業(yè)畢業(yè)論文 題 目 基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘 學(xué)生姓名 孫成偉 學(xué) 號 0710132133 專 業(yè) 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 班 級 2007 級 1 班 指導(dǎo)教師 王培吉 副教授 內(nèi)蒙古科技大學(xué)畢業(yè)論文 I 基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘 摘摘 要要 數(shù)據(jù)挖掘利用了統(tǒng)計(jì)學(xué)的抽樣 估計(jì)和假設(shè)檢驗(yàn)及人工智能 模式識別和 機(jī)器學(xué)習(xí)的搜索算法 建模技術(shù)和學(xué)習(xí)理論等領(lǐng)域的思想 數(shù)據(jù)挖掘在這種具 有固定形式的數(shù)據(jù)集上完成知識的提煉 最后以合適的知識模式用于進(jìn)一步分 析決策工作 在數(shù)據(jù)挖掘所發(fā)現(xiàn)的知識模型中 關(guān)聯(lián)規(guī)則模式是非常重要的一種 也是 最活躍的一個分支 關(guān)聯(lián)規(guī)則表示數(shù)據(jù)庫中一組對象之間某種關(guān)聯(lián)關(guān)系的規(guī)則 本文通過 Apriori 算法 將收集來的歷年全國各地區(qū)城鎮(zhèn)居民食品消費(fèi)情況 進(jìn)行數(shù)據(jù)挖掘 通過數(shù)據(jù)挖掘 找到頻繁項(xiàng)集并得到關(guān)聯(lián)規(guī)則 由關(guān)聯(lián)規(guī)則進(jìn) 行相關(guān)分析 并將得出的分析結(jié)果應(yīng)用到實(shí)際當(dāng)中 關(guān)鍵字 數(shù)據(jù)挖掘 關(guān)聯(lián)規(guī)則 關(guān)鍵字 數(shù)據(jù)挖掘 關(guān)聯(lián)規(guī)則 Apriori 算法 食品消費(fèi)分析算法 食品消費(fèi)分析 內(nèi)蒙古科技大學(xué)畢業(yè)論文 II Data mining based on association rules Abstract Using the statistical data mining the sampling estimation and hypothesis testing and artificial intelligence pattern recognition and machine learning search algorithm modeling technology and learning theory and other areas of thought Data mining in this has fixed forms of datasets finally complete knowledge refining in the proper knowledge model for further analysis and decision work In the knowledge models that data mining has found association rules mode is a very important kind it is also a branch of the most activities Association rules is the relationship between some of the rules in a group of objects in the database Through Apriori algorithm in this paper will collect of calendar year the national regions to urban residents food consumption data mining By data mining to find frequent Itemset and get association rules Correlation analysis by association rules and will the results of analysis in the practical application Key words Data Mining Association rules Apriori algorithm Food consumption analysis 內(nèi)蒙古科技大學(xué)畢業(yè)論文 III 目目 錄錄 摘 要 I ABSTRACT II 目 錄 II 第一章 引 言 1 1 1 研究背景 1 1 1 1 數(shù)據(jù)挖掘與傳統(tǒng)分析方法的區(qū)別 3 1 2 數(shù)據(jù)挖掘的主要問題 3 1 2 1 數(shù)據(jù)挖掘技術(shù)和用戶界面問題 3 1 2 2 挖掘不同類型的知識問題 3 1 2 3 多個抽象層的交互知識挖掘問題 3 1 2 4 數(shù)據(jù)挖掘結(jié)果的表示和顯示問題 3 1 2 5 處理噪音和不完全數(shù)據(jù) 3 1 2 6 模式評估 興趣度問題 4 1 2 7 性能問題 4 1 2 8 數(shù)據(jù)挖掘算法的有效性和可規(guī)模性 4 1 2 9 并行 分布和增量挖掘算法 4 1 3 數(shù)據(jù)挖掘的研究方向 4 1 4 擬解決的問題 5 1 5 本章小結(jié) 6 第二章 數(shù)據(jù)挖掘概念與技術(shù) 7 2 1 數(shù)據(jù)挖掘的任務(wù) 7 2 1 1 數(shù)據(jù)挖掘的職能 7 2 2 數(shù)據(jù)挖掘的對象 8 2 3 可數(shù)據(jù)挖掘的知識模型 9 2 4 數(shù)據(jù)挖掘的技術(shù) 9 內(nèi)蒙古科技大學(xué)畢業(yè)論文 IV 2 4 1 數(shù)據(jù)挖掘的方法 9 2 4 2 數(shù)據(jù)挖掘的步驟 11 第三章 關(guān)聯(lián)規(guī)則 13 3 1 由購物籃分析得到的關(guān)聯(lián)規(guī)則 13 3 2 關(guān)聯(lián)規(guī)則的相關(guān)概念 13 3 2 1 關(guān)聯(lián)規(guī)則的概念 13 3 2 2 支持度與置信度 14 3 3 關(guān)聯(lián)規(guī)則挖掘的過程及分類 15 3 3 1 關(guān)聯(lián)規(guī)則的挖掘過程 15 3 3 2 關(guān)聯(lián)規(guī)則的分類 15 3 4 關(guān)聯(lián)規(guī)則的相關(guān)算法 16 3 4 1 Apriori 算法 16 3 4 2 基于劃分的算法 16 3 4 3 FP 樹頻集算法 17 第四章 APRIORI 算法 18 4 1 APRIORI算法的定義及思想 18 4 1 1 Apriori 算法的基本思想 18 4 2 APRIORI算法的性質(zhì) 18 4 3 APRIORI 算法的步驟 18 4 4 APRIORI算法的特點(diǎn)及局限性 19 4 5 APRIORI算法評價 20 第五章 應(yīng)用 APRIORI 算法的實(shí)例分析 21 5 1 研究說明 21 5 2 研究方法 21 5 2 1 數(shù)據(jù)采集 21 5 2 2 數(shù)據(jù)處理 21 5 2 3 應(yīng)用算法進(jìn)行數(shù)據(jù)挖掘 23 5 2 4 結(jié)果分析 26 內(nèi)蒙古科技大學(xué)畢業(yè)論文 V 參考文獻(xiàn) 27 附 錄 28 致 謝 32 內(nèi)蒙古科技大學(xué)畢業(yè)論文 1 第第一一章章 引引 言言 數(shù)據(jù)挖掘 Data Mining DM 又稱數(shù)據(jù)庫中的知識發(fā)現(xiàn) Knowledge Discover in Database KDD 是目前人工智能和數(shù)據(jù)庫領(lǐng)域研究的熱點(diǎn)問題 所謂數(shù)據(jù)挖掘是指從數(shù)據(jù)庫的大量數(shù)據(jù)中揭示出隱含的 先前未知的并有潛在 價值的信息的非平凡過程 數(shù)據(jù)挖掘是一種決策支持過程 它主要基于人工智能 機(jī)器學(xué)習(xí) 模式識 別 統(tǒng)計(jì)學(xué) 數(shù)據(jù)庫 可視化技術(shù)等 高度自動化地分析企業(yè)的數(shù)據(jù) 做出歸 納性的推理 從中挖掘出潛在的模式 幫助決策者調(diào)整市場策略 減少風(fēng)險 做出正確的決策 1 1 研究背景研究背景 自 2000 年以來 數(shù)據(jù)挖掘引起了信息產(chǎn)業(yè)界的極大關(guān)注 其主要原因是存 在大量數(shù)據(jù) 可以廣泛使用 并且迫切需要將這些數(shù)據(jù)轉(zhuǎn)換成有用的信息和知 識 獲取的信息和知識可以廣泛用于各種應(yīng)用 包括商務(wù)管理 生產(chǎn)控制 市 場分析 工程設(shè)計(jì)和科學(xué)探索等 數(shù)據(jù)挖掘利用了統(tǒng)計(jì)學(xué)的抽樣 估計(jì)和假設(shè)檢驗(yàn)及人工智能 模式識別和 機(jī)器學(xué)習(xí)的搜索算法 建模技術(shù)和學(xué)習(xí)理論等領(lǐng)域的思想 數(shù)據(jù)挖掘也吸納了 其他領(lǐng)域的思想 包括最優(yōu)化 進(jìn)化計(jì)算 信息論 信號處理 可視化和信息 檢索 其中的一些領(lǐng)域在數(shù)據(jù)挖掘中起到了重要的支撐作用 特別的 需要數(shù) 據(jù)庫系統(tǒng)提供有效的存儲 索引和查詢處理的支持 廣義上說 任何從數(shù)據(jù)庫中挖掘信息的過程都叫做數(shù)據(jù)挖掘 從這點(diǎn)看來 數(shù)據(jù)挖掘就是 BI 商業(yè)智能 但從技術(shù)術(shù)語上說 數(shù)據(jù)挖掘 Data Mining 特 指的是 源數(shù)據(jù)經(jīng)過清洗和轉(zhuǎn)換等成為適合于挖掘的數(shù)據(jù)集 數(shù)據(jù)挖掘在這種 具有固定形式的數(shù)據(jù)集上完成知識的提煉 最后以合適的知識模式用于進(jìn)一步 分析決策工作 從這種狹義的觀點(diǎn)上 我們可以定義 數(shù)據(jù)挖掘是從特定形式 的數(shù)據(jù)集中提煉知識的過程 數(shù)據(jù)挖掘往往針對特定的數(shù)據(jù) 特定的問題 選 擇一種或者多種挖掘算法 找到數(shù)據(jù)下面隱藏的規(guī)律 這些規(guī)律往往被用來預(yù) 測 支持決策 自 60 年代以來 數(shù)據(jù)庫和信息技術(shù)已經(jīng)系統(tǒng)地從原始的文件處理進(jìn)化到 內(nèi)蒙古科技大學(xué)畢業(yè)論文 2 復(fù)雜的 功能強(qiáng)大的數(shù)據(jù)庫系統(tǒng) 自70年代以來 數(shù)據(jù)庫系統(tǒng)的研究和開發(fā)已 經(jīng)從層次和網(wǎng)狀數(shù)據(jù)庫發(fā)展到開發(fā)關(guān)系數(shù)據(jù)庫系統(tǒng) 數(shù)據(jù)建模工具 索引和數(shù) 據(jù)組織技術(shù) 自 80 年代中期以來 數(shù)據(jù)庫技術(shù)的特點(diǎn)是廣泛接受關(guān)系技術(shù) 研究和開 發(fā)新的 功能強(qiáng)大的數(shù)據(jù)庫系統(tǒng) 這些使用了先進(jìn)的數(shù)據(jù)模型 如擴(kuò)充關(guān)系 面向?qū)ο?對象 關(guān)系和演繹模型 圖 1 1 數(shù)據(jù)庫技術(shù)的進(jìn)化 內(nèi)蒙古科技大學(xué)畢業(yè)論文 3 1 1 11 1 1 數(shù)據(jù)挖掘與傳統(tǒng)分析方法的區(qū)別數(shù)據(jù)挖掘與傳統(tǒng)分析方法的區(qū)別 數(shù)據(jù)挖掘與傳統(tǒng)的數(shù)據(jù)分析 如查詢 報表 聯(lián)機(jī)應(yīng)用分析 的本質(zhì)區(qū)別 是數(shù)據(jù)挖掘是在沒有明確假設(shè)的前提下去挖掘信息 發(fā)現(xiàn)知識 數(shù)據(jù)挖掘所得 到的信息應(yīng)具有先未知 有效和可實(shí)用三個特征 先前未知的信息是指該信息是預(yù)先未曾預(yù)料到的 即數(shù)據(jù)挖掘是要發(fā)現(xiàn)那 些不可能靠直覺發(fā)現(xiàn)的信息或知識 甚至是違背直覺的信息或知識 挖掘出的 信息越是出乎意料 就可能越有價值 在商業(yè)應(yīng)用中最典型的例子就是一家連 鎖超市通過數(shù)據(jù)挖掘發(fā)現(xiàn)了小孩尿布與啤酒之間的聯(lián)系 1 1 2 數(shù)據(jù)挖掘的主要問題數(shù)據(jù)挖掘的主要問題 由于強(qiáng)調(diào)數(shù)據(jù)挖掘的主要問題 考慮挖掘技術(shù) 用戶界面 性能和各種數(shù) 據(jù)類型 這些問題介紹如下 1 2 1 數(shù)據(jù)挖掘技術(shù)和用戶界面問題數(shù)據(jù)挖掘技術(shù)和用戶界面問題 這反映所挖掘的知識類型 在多粒度上挖掘知識的能力 領(lǐng)域知識的使用 特定的挖掘和知識顯示 1 2 2 挖掘不同類型的知識問題挖掘不同類型的知識問題 由于不同的用戶可能對不同類型的知識感興趣 數(shù)據(jù)挖掘系統(tǒng)應(yīng)當(dāng)覆蓋廣 譜的數(shù)據(jù)分析和知識發(fā)現(xiàn)任務(wù) 包括數(shù)據(jù)特征 區(qū)分 關(guān)聯(lián) 聚類 趨勢 偏 差分析和類似性分析 這些任務(wù)可能以不同的方式使用相同的數(shù)據(jù)庫 并需要 開發(fā)大量數(shù)據(jù)挖掘技術(shù) 1 2 3 多個抽象層的交互知識挖掘問題多個抽象層的交互知識挖掘問題 由于很難準(zhǔn)確地知道能夠在數(shù)據(jù)庫中發(fā)現(xiàn)什么 數(shù)據(jù)挖掘過程應(yīng)當(dāng)是交互 的 1 2 4 數(shù)據(jù)挖掘結(jié)果的表示和顯示問題數(shù)據(jù)挖掘結(jié)果的表示和顯示問題 發(fā)現(xiàn)的知識應(yīng)當(dāng)用高級語言 可視化表示形式 或其它表示形式表示 使 得知識易于理解 能夠直接被人使用 如果數(shù)據(jù)挖掘系統(tǒng)是交互的 這一點(diǎn)尤 為重要 這要求系統(tǒng)采用有表達(dá)能力的知識表示技術(shù) 如樹 表 圖 圖表 交叉表 矩陣或曲線 1 2 5 處理噪音和不完全數(shù)據(jù)處理噪音和不完全數(shù)據(jù) 內(nèi)蒙古科技大學(xué)畢業(yè)論文 4 存放在數(shù)據(jù)庫中數(shù)據(jù)可能反映噪音 例外情況 或不完全的數(shù)據(jù)對象 這 些對象可能搞亂分析過程 導(dǎo)致數(shù)據(jù)與所構(gòu)造的知識模型過分適應(yīng) 其結(jié)果是 所發(fā)現(xiàn)的模式的精確性可能很差 1 2 6 模式評估模式評估 興趣度問題興趣度問題 數(shù)據(jù)挖掘系統(tǒng)可能發(fā)現(xiàn)數(shù)以千計(jì)的模式 對于給定的用戶 許多模式不是 有趣的 它們表示平凡知識或缺乏新穎性 1 2 7 性能問題性能問題 這包括數(shù)據(jù)挖掘算法的有效性 可規(guī)模性和并行處理 1 2 8 數(shù)據(jù)挖掘算法的有效性和可規(guī)模性數(shù)據(jù)挖掘算法的有效性和可規(guī)模性 為了有效地從數(shù)據(jù)庫中大量數(shù)據(jù)提取信息 數(shù)據(jù)挖掘算法必須是有效的和 可規(guī)模化的 1 2 9 并行 分布和增量挖掘算法并行 分布和增量挖掘算法 許多數(shù)據(jù)庫的大容量 數(shù)據(jù)的廣泛分布和一些數(shù)據(jù)挖掘算法的計(jì)算復(fù)雜性 是促使開發(fā)并行和分布式數(shù)據(jù)挖掘算法的因素 這些算法將數(shù)據(jù)劃分成部分 這些部分可以并行處理 然后合并每部分的結(jié)果 1 3 數(shù)據(jù)挖掘的研究方向數(shù)據(jù)挖掘的研究方向 1 數(shù)據(jù)輸入形式的多樣性 應(yīng)用中經(jīng)常需要對一些半結(jié)構(gòu)化 非結(jié)構(gòu)化的數(shù)據(jù)形式如文本 圖形 數(shù) 學(xué)公式 圖像或WWW 資源進(jìn)行挖掘操作 但目前的數(shù)據(jù)挖掘工具一般只能提 供對數(shù)值型的結(jié)構(gòu)化數(shù)據(jù)的處理 對數(shù)據(jù)中存在缺損或噪聲的情況也沒有有效 的方法 2 數(shù)據(jù)挖掘算法的有效性與可測性 數(shù)據(jù)挖掘的對象向更大型的數(shù)據(jù)庫 更高的維數(shù)和屬性之間更復(fù)雜的關(guān)系 方向發(fā)展 更多的記錄和屬性意味著更大 更高維的搜索空間 從而導(dǎo)致組合 爆炸 屬性之間的關(guān)系變得更為復(fù)雜如表現(xiàn)為層次結(jié)構(gòu) 會大大提高知識搜索的 代價 從1個大型數(shù)據(jù)庫中抽取知識的算法必須高效 可測量 即數(shù)據(jù)挖掘算法 的運(yùn)行時間必須可預(yù)測 且可接受 指數(shù)和多項(xiàng)式算法等復(fù)雜性的算法不具有實(shí) 用價值 目前的研究發(fā)展到用并行處理或抽樣的方法處理大規(guī)模數(shù)據(jù)以獲得較 高的計(jì)算效率 根據(jù)問題的定義和領(lǐng)域知識選擇出需要的屬性從而降低維數(shù)并 內(nèi)蒙古科技大學(xué)畢業(yè)論文 5 有效處理屬性之間的復(fù)雜關(guān)系等 3 用戶參與和領(lǐng)域知識 有效的決策過程往往需要多次交互和多次反復(fù) 使數(shù)據(jù)挖掘的結(jié)果準(zhǔn)確地 描述數(shù)據(jù)挖掘的要求 并易于表達(dá) 實(shí)現(xiàn)在多抽象層次上交互挖掘知識 目前許 多知識發(fā)現(xiàn)系統(tǒng)和工具缺乏與用戶的交互 難以有效利用領(lǐng)域知識 4 證實(shí)技術(shù)的局限 數(shù)據(jù)挖掘使用特定的分析方法或邏輯形式發(fā)現(xiàn)知識 如歸納方法 但系統(tǒng) 可能無法去交互證實(shí)所發(fā)現(xiàn)的知識的正確或正確的程度 使得發(fā)現(xiàn)的知識沒有 普遍性而不能成為有用的知識 5 知識的表達(dá)和解釋機(jī)制 許多應(yīng)用中重要的是用戶能夠理解發(fā)現(xiàn)的知識 這要求知識的表達(dá)不僅限 于數(shù)字或符號 而是更易于理解的方式 如圖形 自然語言和可視化技術(shù)等 同 時 只有當(dāng)數(shù)據(jù)挖掘系統(tǒng)能提供更好的解釋機(jī)制 用戶才能更有效地評價這些知 識 并且區(qū)分出哪些是真正有用的知識 哪些只是常識性的知識或異常情況 6 知識的維護(hù)和更新 新的知識發(fā)現(xiàn)可能導(dǎo)致以前發(fā)現(xiàn)的知識失效 因此知識需要動態(tài)維護(hù)和及 時更新 目前研究采用增量更新的方法 數(shù)據(jù)快照和時間戳等方法來維護(hù)已有 的知識 7 私有性和安全性 數(shù)據(jù)挖掘能從不同角度 不同抽象層次上觀察數(shù)據(jù) 將影響到數(shù)據(jù)挖掘的 私有性和安全性 通過研究數(shù)據(jù)挖掘?qū)е碌臄?shù)據(jù)非法侵入 可改進(jìn)數(shù)據(jù)庫安全 方法 以避免信息泄露 8 支持的局限與其他系統(tǒng)的集成 目前的數(shù)據(jù)挖掘系統(tǒng)尚不能支持多種平臺 一些產(chǎn)品是基于PC的 一些是 面向大型主機(jī)系統(tǒng)的 還有一些是面向客戶機(jī) 服務(wù)器環(huán)境的 另外 由于方法 功能單一的發(fā)現(xiàn)系統(tǒng)的適應(yīng)范圍的限制 要充分發(fā)揮系統(tǒng)的作用 應(yīng)該和數(shù)據(jù)庫 知識庫 專家系統(tǒng) 決策支持系統(tǒng) 可視化工具 網(wǎng)絡(luò)技術(shù)等進(jìn)行有機(jī)集成 5 6 1 4 擬解決的問題擬解決的問題 內(nèi)蒙古科技大學(xué)畢業(yè)論文 6 通過調(diào)查 9 類食品歷年 2000 2009 年 2004 年除外 各地區(qū)的人均食物消 費(fèi)情況 可以清楚的知道各地區(qū)人民的飲食習(xí)慣 對這些數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘 得到相應(yīng)的關(guān)聯(lián)規(guī)則 依據(jù)得到的關(guān)聯(lián)規(guī)則 可以建立相應(yīng)的食品供給機(jī)制 提供合理的飲食建議 可以使人們在日常的飲食中吃的更健康 本文通過對采集來的數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘 運(yùn)用 apriori 算法進(jìn)行相關(guān)的挖掘 得到關(guān)聯(lián)規(guī)則 并應(yīng)用到實(shí)際 1 5 本章小結(jié)本章小結(jié) 本章介紹了數(shù)據(jù)挖掘技術(shù)的研究意義及技術(shù)背景 數(shù)據(jù)挖掘的主要問題 論文選題的依據(jù) 數(shù)據(jù)挖掘的研究方向及我們所做論文的主要內(nèi)容等 在當(dāng)今 社會 正處于信息爆炸的年代 怎樣從眾多的 無序 紛亂 復(fù)雜的信息中得 到自己有用的信息 這就需要一定的信息處理能力 數(shù)據(jù)挖掘就是在這樣的環(huán) 境中得到完善和發(fā)展 數(shù)據(jù)挖掘技術(shù)融合了當(dāng)今的許多學(xué)科的最新研究成果和 技術(shù)而形成的一個具有自己特色的研究分支 可進(jìn)行數(shù)據(jù)挖掘的項(xiàng)目極其豐富 進(jìn)行數(shù)據(jù)挖掘的方法也有很多種 本文是對全國各地區(qū)歷年對 9 類食品的消費(fèi) 情況進(jìn)行數(shù)據(jù)挖掘 并得出相應(yīng)的分析 內(nèi)蒙古科技大學(xué)畢業(yè)論文 7 第第二二章章 數(shù)數(shù)據(jù)據(jù)挖挖掘掘概概念念與與技技術(shù)術(shù) 數(shù)據(jù)挖掘 Data Mining 就是從存放在數(shù)據(jù)庫 數(shù)據(jù)倉庫或其他信息庫中 的大量的數(shù)據(jù)中獲取有效的 新穎的 潛在有用的 最終可理解模式的非平凡 過程 數(shù)據(jù)挖掘涉及多學(xué)科技術(shù)的集成 包括數(shù)據(jù)庫技術(shù) 統(tǒng)計(jì) 機(jī)器學(xué)習(xí) 高 性能計(jì)算 模式識別 神經(jīng)網(wǎng)絡(luò) 數(shù)據(jù)可視化 信息提取 圖像與信號處理和 空間數(shù)據(jù)分析 簡單地說 數(shù)據(jù)挖掘是從大量數(shù)據(jù)中提取或 挖掘 知識 該術(shù)語實(shí)際上有 點(diǎn)用詞不當(dāng) 注意 從礦石或砂子挖掘黃金稱作黃金挖掘 而不是砂石挖掘 這樣 數(shù)據(jù)挖掘應(yīng)當(dāng)更正確地命名為 從數(shù)據(jù)中挖掘知識 知識挖掘 是一個 短術(shù)語 可能不能強(qiáng)調(diào)從大量數(shù)據(jù)中挖掘 畢竟 挖掘是一個很生動的術(shù)語 它抓住了從大量的 未加工的材料中發(fā)現(xiàn)少量金塊這一過程的特點(diǎn) 圖 2 1 通過數(shù)據(jù)挖掘 可以從數(shù)據(jù)庫提取有趣的知識 規(guī)律 或高層信息 并可 以從不同角度觀察或?yàn)g覽 發(fā)現(xiàn)的知識可以用于決策 過程控制 信息管理 查詢處理 等等 因此 數(shù)據(jù)挖掘被信息產(chǎn)業(yè)界認(rèn)為是數(shù)據(jù)庫系統(tǒng)最重要的前 沿之一 是信息產(chǎn)業(yè)最有前途的交叉學(xué)科 2 1 數(shù)據(jù)挖掘的任務(wù)數(shù)據(jù)挖掘的任務(wù) 通常數(shù)據(jù)挖掘的任務(wù)可以分為預(yù)測和描述兩大類 預(yù)測任務(wù)是根據(jù)己知屬性的值 推斷特定的未知屬性的值 被預(yù)測的屬性一 般稱為目標(biāo)變量 用于做預(yù)測的屬性稱為說明變量 預(yù)測分為針對離散的目標(biāo) 變量的分類任務(wù)和針對連續(xù)的目標(biāo)變量的回歸任務(wù) 描述任務(wù)是刻畫數(shù)據(jù)庫中數(shù)據(jù)的一般特性 目標(biāo)是以簡潔概要的方式導(dǎo)出 概括數(shù)據(jù)中潛在聯(lián)系的模式 描述任務(wù)可以發(fā)現(xiàn)的模式有 概念描述 特征化和 比較 關(guān)聯(lián)規(guī)則 聚類 異常等 2 1 1 數(shù)據(jù)挖掘的職能數(shù)據(jù)挖掘的職能 內(nèi)蒙古科技大學(xué)畢業(yè)論文 8 數(shù)據(jù)挖掘能做以下七種不同事情 分析方法 分類 Classification 估值 Estimation 預(yù)言 Prediction 相關(guān)性分組或關(guān)聯(lián)規(guī)則 Affinity grouping or association rules 聚集 Clustering 描述和可視化 Description and Visualization 復(fù)雜數(shù)據(jù)類型挖掘 Text Web 圖形圖像 視頻 音頻等 以上七種數(shù)據(jù)挖掘的分析方法可以分為兩類 直接數(shù)據(jù)挖掘 間接數(shù)據(jù)挖 掘 1 直接數(shù)據(jù)挖掘直接數(shù)據(jù)挖掘 目標(biāo)是利用可用的數(shù)據(jù)建立一個模型 這個模型對剩余的數(shù)據(jù) 對一個特 定的變量 可以理解成數(shù)據(jù)庫中表的屬性 即列 進(jìn)行描述 2 間接數(shù)據(jù)挖掘 間接數(shù)據(jù)挖掘 目標(biāo)中沒有選出某一具體的變量 用模型進(jìn)行描述 而是在所有的變量中 建立起某種關(guān)系 分類 估值 預(yù)言屬于直接數(shù)據(jù)挖掘 后三種屬于間接數(shù)據(jù)挖掘 數(shù)據(jù)挖掘的范圍非常廣泛 可以是社會科學(xué) 經(jīng)濟(jì)學(xué) 商業(yè)數(shù)據(jù) 科學(xué)處 理產(chǎn)生的數(shù)據(jù)和衛(wèi)星觀測得到的數(shù)據(jù) 它們的數(shù)據(jù)結(jié)構(gòu)也各不相同 可以是層 次的 網(wǎng)狀的 關(guān)系的和面向?qū)ο蟮臄?shù)據(jù) 2 2 數(shù)據(jù)挖掘的對象數(shù)據(jù)挖掘的對象 數(shù)據(jù)挖掘是一個以數(shù)據(jù)庫 人工智能 數(shù)理統(tǒng)計(jì) 可視化四大支柱技術(shù)為 基礎(chǔ) 多學(xué)科交叉 滲透 融合形成的新的交叉學(xué)科 其研究內(nèi)容十分廣泛 目前存在很多數(shù)據(jù)挖掘方法或算法 因此有必要對這些方法進(jìn)行分門別類 描 述或說明一個算法涉及三個部分 輸入 輸出和處理過程 數(shù)據(jù)挖掘算法的輸 入是數(shù)據(jù)庫 算法的輸出是要發(fā)現(xiàn)的知識或模式 算法的處理過程則涉及具體 的搜索方法 從算法的輸入 輸出和處理過程三個角度 我們可以確定這樣幾 種分類標(biāo)準(zhǔn) 挖掘?qū)ο?挖掘方法 挖掘任務(wù) 根據(jù)挖掘?qū)ο蠓?有如下若干種數(shù)據(jù)庫或數(shù)據(jù)源 關(guān)系數(shù)據(jù)庫 面向?qū)ο髷?shù) 內(nèi)蒙古科技大學(xué)畢業(yè)論文 9 據(jù)庫 空間數(shù)據(jù)庫 時態(tài)數(shù)據(jù)庫 文本數(shù)據(jù)庫 多媒體數(shù)據(jù)庫 異質(zhì)數(shù)據(jù)庫 歷史數(shù)據(jù)庫 以及萬維網(wǎng) Web 根據(jù)挖掘方法分 可粗分為 統(tǒng)計(jì)方法 機(jī)器學(xué)習(xí)方法 神經(jīng)網(wǎng)絡(luò)方法和數(shù) 據(jù)庫方法 統(tǒng)計(jì)方法可細(xì)分為 回歸分析 判別分析 聚類分析 探索性分析等 機(jī)器學(xué)習(xí)可細(xì)分為 歸納學(xué)習(xí)方法 基于范例學(xué)習(xí) 遺傳算法等 神經(jīng)網(wǎng)絡(luò)方法 可細(xì)分為 前向神經(jīng)網(wǎng)絡(luò) 自組織神經(jīng)網(wǎng)絡(luò)等 數(shù)據(jù)庫方法主要是多維數(shù)據(jù)分析 或 OLAP 方法 另外還有面向?qū)傩缘臍w納方法 2 3 可數(shù)據(jù)挖掘的知識模型可數(shù)據(jù)挖掘的知識模型 根據(jù)挖掘任務(wù)分 數(shù)據(jù)挖掘主要發(fā)現(xiàn)以下五類知識 1 廣義型知識 根據(jù)數(shù)據(jù)的微觀特性發(fā)現(xiàn)其表征的 帶有普遍性的 較高 層次概念的 中觀或宏觀的知識 2 分類型知識 反映同類事物共同性質(zhì)的特征型知識和不同事物之間差異 性特征知識 用于反映數(shù)據(jù)的匯聚模式或根據(jù)對象的屬性區(qū)分其所屬類別 3 關(guān)聯(lián)型知識 反映一個事件和其他事件之間依賴或關(guān)聯(lián)的知識 又稱依 賴關(guān)系 這類知識可用于數(shù)據(jù)庫中的歸一化 查詢優(yōu)化等 4 預(yù)測型知識 通過時間序列型數(shù)據(jù) 有歷史的和當(dāng)前的數(shù)據(jù)去預(yù)測未來 的情況 它實(shí)際上是一種以時間為關(guān)鍵屬性的關(guān)聯(lián)知識 5 偏差型知識 通過分析標(biāo)準(zhǔn)類以外的特例 數(shù)據(jù)聚類外的離群值 實(shí)際 觀測值和系統(tǒng)預(yù)測值間的顯著差別 來對差異和極端特例進(jìn)行描述 2 4 數(shù)據(jù)挖掘的技術(shù)數(shù)據(jù)挖掘的技術(shù) 2 4 1 數(shù)據(jù)挖掘的方法數(shù)據(jù)挖掘的方法 從不同的角度看 數(shù)據(jù)挖掘技術(shù)有多種分類方法 如根據(jù)發(fā)現(xiàn)的知識種類分 類 根據(jù)挖掘的數(shù)據(jù)庫類型分類 根據(jù)挖掘方法分類 根據(jù)挖掘的途徑分類 根 據(jù)所采用的技術(shù)分類等等 目前常用的數(shù)據(jù)挖掘技術(shù)內(nèi)容包括如下 1 決策樹方法 利用信息論中的互信息 信息增益 尋找數(shù)據(jù)庫中具有最大信息量的字段 建立決策樹的一個結(jié)點(diǎn) 再根據(jù)字段的不同取值建立樹的分支 在每個分支子集 中重復(fù)建立樹的下層結(jié)點(diǎn)和分支的過程 即可建立決策樹 國際上最有影響和 最早的決策樹算法是 Quiulan 研制的 ID3 方法 數(shù)據(jù)庫越大它的效果越好 此 內(nèi)蒙古科技大學(xué)畢業(yè)論文 10 后又發(fā)展了各種決策樹方法 如 IBL E 方法使識別率提高了 10 2 神經(jīng)網(wǎng)絡(luò)方法 它模擬人腦神經(jīng)元結(jié)構(gòu) 以 MP 模型和 Hebb 學(xué)習(xí)規(guī)則為基礎(chǔ) 用神經(jīng)網(wǎng)絡(luò) 連接的權(quán)值表示知識 其學(xué)習(xí)體現(xiàn)在神經(jīng)網(wǎng)絡(luò)權(quán)值的逐步計(jì)算上 目前主要有 3 大類多種神經(jīng)網(wǎng)絡(luò)模型 前饋式網(wǎng)絡(luò) 它以感知機(jī) 反向傳播模型 函數(shù)型 網(wǎng)絡(luò)為代表 可用于預(yù)測 模式識別等方面 反饋式網(wǎng)絡(luò) 它以 Hopf ield 的 離散模型和連續(xù)模型為代表 分別用于聯(lián)想記憶和優(yōu)化計(jì)算 自組織網(wǎng)絡(luò) 它以 ART 模型 Koholon 模型為代表 用于聚類 3 覆蓋正例排斥反例方法 它是利用覆蓋所有正例 排斥所有反例的思想來尋找規(guī)則 首先在正例集 合中任選一個種子 到反例集合中逐個比較 與字段取值構(gòu)成的選擇子相容則舍 去 相反則保留 按此思想循環(huán)所有正例種子 將得到正例的規(guī)則 選擇子的合 取式 比較典型的算法有 M ichalsk i 的 AQ 11 方法 洪家榮改進(jìn)的 AQ 15 方 法以及他的 A E5 方法 4 粗集 Rough Set 方法 在數(shù)據(jù)庫中 將行元素看成對象 列元素看成屬性 分為條件屬性和決策屬 性 等價關(guān)系 R 定義為不同對象在某個 或幾個 屬性上取值相同 這些滿足 等價關(guān)系的對象組成的集合稱為該等價關(guān)系 R 的等價類 條件屬性上的等價類 E 與決策屬性上的等價類 Y 之間有 3 種情況 下近似 Y 包含 E 上近似 Y 和 E 的交非空 無關(guān) Y 和 E 的交為空 對下近似建立確定性規(guī)則 對上近似 建立不確定性規(guī)則 含可信度 對無關(guān)情況不存在規(guī)則 5 概念樹方法 對數(shù)據(jù)庫中記錄的屬性字段按歸類方式進(jìn)行抽象 建立起來的層次結(jié)構(gòu)稱 之為概念樹 利用概念樹提升的方法可以大大濃縮數(shù)據(jù)庫中的記錄 對多個屬 性字段的概念樹進(jìn)行提升 將得到高度概括的知識基表 然后可再將它轉(zhuǎn)換成規(guī) 則 6 遺傳算法 這是模擬生物進(jìn)化過程的算法 由 3 個基本算子組成 繁殖 選擇 是從 1 個舊種群 父代 選出生命力強(qiáng)的個體 產(chǎn)生新種群 后代 的過程 交叉 重 內(nèi)蒙古科技大學(xué)畢業(yè)論文 11 組 選擇 2 個不同個體 染色體 的部分 基因 進(jìn)行交換 形成新個體 變 異 突變 對某些個體的某些基因進(jìn)行變異 1 變 0 0 變 1 這種遺傳算法可以 起到產(chǎn)生優(yōu)良后代的作用 這些后代需滿足適應(yīng)度值 經(jīng)過若干代的遺傳 將得 到滿足要求的后代 問題的解 遺傳算法已在優(yōu)化計(jì)算和分類機(jī)器學(xué)習(xí)方面顯 示了明顯的優(yōu)勢 7 公式發(fā)現(xiàn) 在工程和科學(xué)數(shù)據(jù)庫 由實(shí)驗(yàn)數(shù)據(jù)組成 中 對若干數(shù)據(jù)項(xiàng) 變量 進(jìn)行一定 的數(shù)學(xué)運(yùn)算 求得相應(yīng)的數(shù)學(xué)公式 比較典型的 BACON 發(fā)現(xiàn)系統(tǒng)完成了對物 理學(xué)中大量定律的重新發(fā)現(xiàn) 其基本思想是 對數(shù)據(jù)項(xiàng)進(jìn)行初等數(shù)學(xué)運(yùn)算 加 減 乘 除等 形成組合 數(shù)據(jù)項(xiàng) 若它的值為常數(shù)項(xiàng) 就得到了組合數(shù)據(jù)項(xiàng)等于常數(shù)的公式 8 統(tǒng)計(jì)分析方法 在數(shù)據(jù)庫字段項(xiàng)之間存在兩種關(guān)系 函數(shù)關(guān)系 能用函數(shù)公式表示的確定性 關(guān)系 和相關(guān)關(guān)系 不能用函數(shù)公式表示 但仍是相關(guān)確定關(guān)系 對它們的分析 采用如下方法 回歸分析 相關(guān)分析 主成分分析 9 模糊集方法 利用模糊集理論對實(shí)際問題進(jìn)行模糊評判 模糊決策 模糊模式識別和模 糊聚類分析 模糊性是客觀存在的 系統(tǒng)的復(fù)雜性越高 精確化能力就越低 即 模糊性就越強(qiáng) 這是 Zadeh 總結(jié)出的互克性原理 10 可視化技術(shù) 可視化數(shù)據(jù)分析技術(shù)拓寬了傳統(tǒng)的圖表功能 使用戶對數(shù)據(jù)的剖析更清楚 例如 把數(shù)據(jù)庫中的多維數(shù)據(jù)變成多種圖形 這對揭示數(shù)據(jù)的狀況 內(nèi)在本質(zhì)及 規(guī)律性起了很大作用 2 4 2 數(shù)據(jù)挖掘的步驟數(shù)據(jù)挖掘的步驟 一些人只是把數(shù)據(jù)挖掘視為數(shù)據(jù)庫中知識發(fā)現(xiàn)過程的一個基本步驟 知識 發(fā)現(xiàn)過程 由以下步驟組成 1 數(shù)據(jù)清理 消除噪音或不一致數(shù)據(jù) 2 數(shù)據(jù)集成 多種數(shù)據(jù)源可以組合在一起 3 數(shù)據(jù)選擇 從數(shù)據(jù)庫中提取與分析任務(wù)相關(guān)的數(shù)據(jù) 內(nèi)蒙古科技大學(xué)畢業(yè)論文 12 4 數(shù)據(jù)變換 數(shù)據(jù)變換或統(tǒng)一成適合挖掘的形式 如 通過匯總或聚集操 作 5 數(shù)據(jù)挖掘 基本步驟 使用智能方法提取數(shù)據(jù)模式 6 模式評估 根據(jù)某種興趣度度量 識別提供知識的真正有趣的模式 7 知識表示 使用可視化和知識表示技術(shù) 向用戶提供挖掘的知識 數(shù)據(jù)挖掘步驟可以與用戶或知識庫交互 有趣的模式提供給用戶 或作為 新的知識存放在知識庫中 注意 根據(jù)這種觀點(diǎn) 數(shù)據(jù)挖掘只是整個過程中的 一步 盡管是最重要的一步 因?yàn)樗l(fā)現(xiàn)隱藏的模式 內(nèi)蒙古科技大學(xué)畢業(yè)論文 13 第第三三章章 關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則 3 1 由購物籃分析得到的關(guān)聯(lián)規(guī)則由購物籃分析得到的關(guān)聯(lián)規(guī)則 作為超市的一名銷售經(jīng)理 應(yīng)該最想知道的是消費(fèi)者購物的心里 消費(fèi)者 在購物時最想買到的物品 在買一件商品時會有這個商品會再買那種商品 也 是哪幾種商品會被消費(fèi)者頻繁購買 例如 在一家超市中 人們發(fā)現(xiàn)了一個特 別有趣的現(xiàn)象 尿布與啤酒這兩種風(fēng)馬牛不相及的商品居然擺在一起 但這一 奇怪的舉措居然使尿布和啤酒的銷量大幅增加了 這可不是一個笑話 而是一 直被商家所津津樂道的發(fā)生在美國沃爾瑪連鎖超市的真實(shí)案例 原來 美國的婦女通常在家照顧孩子 所以她們經(jīng)常會囑咐丈夫在下班回 家的路上為孩子買尿布 而丈夫在買尿布的同時又會順手購買自己愛喝的啤酒 這個發(fā)硯為商家?guī)砹舜罅康睦麧?但是如何從浩如煙海卻又雜亂無章的數(shù)據(jù) 中 發(fā)現(xiàn)啤酒和尿布銷售之間的聯(lián)系呢 這又給了我們什么樣的啟示呢 3 啤酒 和 尿布 兩個看上去沒聯(lián)系的兩種商品放在一起 卻獲得了豐 厚的利潤 這種現(xiàn)象就是賣場中商品直接的關(guān)聯(lián)性 研究 啤酒和尿布 關(guān)聯(lián) 的方法就是購物籃分析 3 2 關(guān)聯(lián)規(guī)則的相關(guān)概念關(guān)聯(lián)規(guī)則的相關(guān)概念 在數(shù)據(jù)挖掘所發(fā)現(xiàn)的知識模型中 關(guān)聯(lián)規(guī)則模式是非常重要的一種 也是 最活躍的一個分支 關(guān)聯(lián)規(guī)則表示數(shù)據(jù)庫中一組對象之間某種關(guān)聯(lián)關(guān)系的規(guī)則 關(guān)聯(lián)規(guī)則挖掘是指發(fā)現(xiàn)大量數(shù)據(jù)中項(xiàng)集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系 關(guān)聯(lián) 規(guī)則問題由 R Agrawal 等在 1993 年提出 隨即引起了廣泛的關(guān)注 許多研究者 對關(guān)聯(lián)規(guī)則挖掘問題進(jìn)行了深入的研究 對最初的關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行了改 進(jìn)和擴(kuò)展 同時 關(guān)聯(lián)規(guī)則的挖掘被應(yīng)用到許多其它領(lǐng)域的數(shù)據(jù)庫 取得了良 好的挖掘效果 3 2 1 關(guān)聯(lián)規(guī)則的概念關(guān)聯(lián)規(guī)則的概念 內(nèi)蒙古科技大學(xué)畢業(yè)論文 14 設(shè) I 是項(xiàng)的集合 設(shè)任務(wù)相關(guān)的數(shù)據(jù) D 是數(shù)據(jù)庫事務(wù)的集 1i2imi 合 其中每個事務(wù) T 是項(xiàng)的集合 使得 TI 每一個事務(wù)有一個標(biāo)識符 稱作 TID 設(shè) A 是一個項(xiàng)集 事務(wù) T 包含 A 當(dāng)且僅當(dāng) A I 關(guān)聯(lián)規(guī)則是形如 A B 的蘊(yùn)涵式 其中 A I B I 并且 A B 3 2 2 支持度與置信度支持度與置信度 規(guī)則的支持度和置信度是兩個規(guī)則興趣度量值 它們分別表示發(fā)現(xiàn)規(guī)則的 有用性和確定性 規(guī)則 AB 在事務(wù)集 D 中出現(xiàn) 具有支持度 s 其中 s 是 D 中事務(wù)包含 A B 即 A 和 B 二者 的百分比 它是概率 P A B 規(guī)則 A B 在 事務(wù)集 D 中具有置信度 c 如果 D 中包含 A 的事務(wù)的同時也包含 B 的百分比是 c 這是條件概率 P B A 即是 support AB P A B 3 1 即 關(guān)聯(lián)模式的支持度是模式為真的任務(wù)相關(guān)的元組 或事務(wù) 所占的百 分比 對于關(guān)聯(lián)規(guī)則 AB 其中 A 和 B 是項(xiàng)目的集合 支持度定義為 元組總數(shù) 的元組數(shù)和包含 支持度 BA BA confidence AB P B A 3 2 即 每個發(fā)現(xiàn)模式都應(yīng)當(dāng)由一個表示其有效性或 值得信賴性 的確定性 度量 對于關(guān)聯(lián)規(guī)則 AB 其中 A 和 B 是項(xiàng)目的集合 其確定性度量置信 度定義為 的元組數(shù)包含 的元組數(shù)和包含 置信度 A BA BA 同時滿足最小支持度閾值 min sup 和最小置信度閾值 min conf 的規(guī) 則稱作強(qiáng)規(guī)則 我們用 0 和 100 之間的值而不是用 0 到 1 之間的值表示支持 度和置信度 為挖掘有效的關(guān)聯(lián)規(guī)則 必須給定最小支持度 min sup 和最小置信度 min conf 關(guān)聯(lián)規(guī)則的挖掘問題就是在 D 中求解所有支持度和置信度均分別 超過 min sup 和 min conf 的關(guān)聯(lián)規(guī)則 即要求解滿足 support AB min sup 和 confidence AB min conf 的規(guī)則 AB 同時滿足最小支持度閾值 min sup 和最小置信度閾值 min conf 的規(guī)則稱為強(qiáng)規(guī)則 7 內(nèi)蒙古科技大學(xué)畢業(yè)論文 15 項(xiàng)的集合稱為項(xiàng)集 包含 k 個項(xiàng)的項(xiàng)集稱為 k 項(xiàng)集 3 3 關(guān)聯(lián)規(guī)則挖掘的過程及分類關(guān)聯(lián)規(guī)則挖掘的過程及分類 3 3 1 關(guān)聯(lián)規(guī)則的挖掘過程關(guān)聯(lián)規(guī)則的挖掘過程 關(guān)聯(lián)規(guī)則的挖掘是一個兩步的過程 1 找出所有頻繁項(xiàng)集 根據(jù)定義 這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的 最小支持度計(jì)數(shù)一樣 2 由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則 根據(jù)定義 這些規(guī)則必須滿足最小支持度 和最小置信度 關(guān)聯(lián)規(guī)則的第一階段必須從原始資料集合中 找出所有高頻項(xiàng)目組 Large Itemsets 第二階段是要產(chǎn)生關(guān)聯(lián)規(guī)則 Association Rules 從高頻項(xiàng)目組產(chǎn) 生關(guān)聯(lián)規(guī)則 是利用前一步驟的頻繁 k 項(xiàng)集來產(chǎn)生規(guī)則 在最小置信度 Minimum Confidence 的條件下 若這一規(guī)則所求得的置信度滿足最小置信 度 則稱此規(guī)則為關(guān)聯(lián)規(guī)則 4 3 3 2 關(guān)聯(lián)規(guī)則的分類關(guān)聯(lián)規(guī)則的分類 按照不同情況 關(guān)聯(lián)規(guī)則可以進(jìn)行分類如下 1 基于規(guī)則中處理的變量的類別 關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型 布爾型關(guān)聯(lián)規(guī)則處理的值都是離散的 種類化的 它顯示了這些變量之 間的關(guān)系 而數(shù)值型關(guān)聯(lián)規(guī)則可以和多維關(guān)聯(lián)或多層關(guān)聯(lián)規(guī)則結(jié)合起來 對 數(shù)值型字段進(jìn)行處理 將其進(jìn)行動態(tài)的分割 或者直接對原始的數(shù)據(jù)進(jìn)行處 理 當(dāng)然數(shù)值型關(guān)聯(lián)規(guī)則中也可以包含種類變量 2 基于規(guī)則中數(shù)據(jù)的抽象層次 可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則 在單層的關(guān)聯(lián)規(guī)則中 所有的變量都沒有考慮到現(xiàn)實(shí)的數(shù)據(jù)是具有多個 不同的層次的 而在多層的關(guān)聯(lián)規(guī)則中 對數(shù)據(jù)的多層性已經(jīng)進(jìn)行了充分的 考慮 3 基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù) 關(guān)聯(lián)規(guī)則可以分為單維的和多維的 內(nèi)蒙古科技大學(xué)畢業(yè)論文 16 在單維的關(guān)聯(lián)規(guī)則中 我們只涉及到數(shù)據(jù)的一個維 如用戶購買的物品 而在多維的關(guān)聯(lián)規(guī)則中 要處理的數(shù)據(jù)將會涉及多個維 換成另一句話 單 維關(guān)聯(lián)規(guī)則是處理單個屬性中的一些關(guān)系 多維關(guān)聯(lián)規(guī)則是處理各個屬性之 間的某些關(guān)系 例如 啤酒 尿布 這條規(guī)則只涉及到用戶的購買的物品 性別 女 職業(yè) 秘書 這條規(guī)則就涉及到兩個字段的信息 是兩個維上 的一條關(guān)聯(lián)規(guī)則 3 4 關(guān)聯(lián)規(guī)則的相關(guān)算法關(guān)聯(lián)規(guī)則的相關(guān)算法 3 4 1 Apriori 算算法法 Apriori 算法 使用候選項(xiàng)集找頻繁項(xiàng)集 Apriori 算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法 其核 心是基于兩階段頻集思想的遞推算法 該關(guān)聯(lián)規(guī)則在分類上屬于單維 單層 布爾關(guān)聯(lián)規(guī)則 在這里 所有支持度大于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集 簡稱頻集 Apriori 算法的基本思想是 1 找出所有的頻集 這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度 一樣 2 由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則 這些規(guī)則必須滿足最小支持度和最小可 信度 3 使用第一步找到的頻集產(chǎn)生期望的規(guī)則 產(chǎn)生只包含集合的項(xiàng)的所有 規(guī)則 其中每一條規(guī)則的右部只有一項(xiàng) 這里采用的是中規(guī)則的定義 一旦 這些規(guī)則被生成 那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下 來 為了生成所有頻集 使用了遞推的方法 可能產(chǎn)生大量的候選集 以及可能需要重復(fù)掃描數(shù)據(jù)庫 是 Apriori 算法 的兩大缺點(diǎn) 3 4 2 基基于于劃劃分分的的算算法法 基于劃分的算法 是由 Savasere 等人設(shè)計(jì)的 這個算法先把數(shù)據(jù)庫從邏輯 上分成幾個互不相交的塊 每次單獨(dú)考慮一個分塊并對它生成所有的頻集 然后把產(chǎn)生的頻集合并 用來生成所有可能的頻集 最后計(jì)算這些項(xiàng)集的支 持度 這里分塊的大小選擇要使得每個分塊可以被放入主存 每個階段只需 內(nèi)蒙古科技大學(xué)畢業(yè)論文 17 被掃描一次 該算法是可以高度并行的 可以把每一分塊分別分配給某一個 處理器生成頻集 算法的正確性是由每一個可能的頻集 至少在某一個分 塊中保證是頻繁項(xiàng)集 產(chǎn)生頻集的每一個循環(huán)結(jié)束后 處理器之間進(jìn)行通信 來產(chǎn)生全局的候選 k 項(xiàng)集 通常這里的通信過程是算法執(zhí)行時間的主要瓶頸 而另一方面 每個獨(dú)立的處理器生成頻集的時間也是一個瓶頸 3 4 3 FP 樹頻集算法樹頻集算法 針對 Apriori 算法的固有缺陷 J Han 等提出了不產(chǎn)生候選挖掘頻繁項(xiàng) 集的方法 FP 樹頻集算法 采用分而治之的策略 在經(jīng)過第一遍掃描之后 把數(shù)據(jù)庫中的頻集壓縮進(jìn)一棵頻繁模式樹 FP tree 同時依然保留其中的 關(guān)聯(lián)信息 隨后再將 FP tree 分化成一些條件庫 每個庫和一個長度為1 的 頻集相關(guān) 然后再對這些條件庫分別進(jìn)行挖掘 當(dāng)原始數(shù)據(jù)量很大的時候 也可以結(jié)合劃分的方法 使得一個 FP tree 可以放入主存中 實(shí)驗(yàn)表明 FP tree 對不同長度的規(guī)則都有很好的適應(yīng)性 同時在效率上較之Apriori 算法 有巨大的提高 本文主要是應(yīng)用 Apriori 算法 對本文中的是實(shí)例進(jìn)行分析 研究 內(nèi)蒙古科技大學(xué)畢業(yè)論文 18 第四章第四章 Apriori 算法算法 4 1 Apriori 算法的定義及思想算法的定義及思想 Apriori 算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法 算法的 名字基于這樣的事實(shí) 算法使用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識 正如我們將看到的 Apriori 使用一種稱作逐層搜索的迭代方法 k 項(xiàng)集用于探索 k 1 項(xiàng)集 4 1 14 1 1 AprioriApriori 算法的基本思想算法的基本思想 1 首先 通過掃描數(shù)據(jù)集 產(chǎn)生一個大的候選數(shù)據(jù)項(xiàng)集 并計(jì)算每個候 選數(shù)據(jù)項(xiàng)發(fā)生的次數(shù) 然后基于預(yù)先給定的最小支持度生成頻繁1 項(xiàng)集的集合 該集合記作L1 2 然后基于L1 和數(shù)據(jù)集中的數(shù)據(jù) 產(chǎn)生頻繁2 項(xiàng)集L2 3 用同樣的方法 直到生成頻繁n 項(xiàng)集Ln 其中已不再可能生成滿足最 小支持度的 N 1 項(xiàng)集 4 最后 從大數(shù)據(jù)項(xiàng)集中導(dǎo)出規(guī)則 為提高頻繁項(xiàng)集逐層產(chǎn)生的效率 一種稱作 Apriori 性質(zhì)的重要性質(zhì)用于 壓縮搜索空間 4 2 Apriori 算法的性質(zhì)算法的性質(zhì) 為了提高按層搜索并產(chǎn)生相應(yīng)頻繁項(xiàng)集的處理效率 Apriori 算法利用了如 下一個重要性質(zhì)來幫助有效縮小頻繁項(xiàng)集的搜索空間 Apriori 性質(zhì) 一個頻繁項(xiàng)集中 任一子集也應(yīng)是頻繁項(xiàng)集 Apriori 性質(zhì)是根據(jù)以下觀察而得出結(jié)論 根據(jù)定義 若一個項(xiàng)集 I 不滿 足最小支持度閾值s 那么該項(xiàng)集 I 就不是頻繁項(xiàng)集 即P I s 若增加一個項(xiàng)A 到項(xiàng)集 I 中 那么所獲得的新項(xiàng)集 I A在整個交易數(shù)據(jù)庫所出現(xiàn)的次數(shù)也不 可能多于原項(xiàng)集 I 出現(xiàn)的次數(shù) 因此 I A 也不能是頻繁的 即P I A s 根據(jù)逆反公理 即若一個集合不能通過測試 該集合所有超集也不能通過 內(nèi)蒙古科技大學(xué)畢業(yè)論文 19 同樣的測試 因此很容易確定Apriori 算法是正確的 4 3 Apriori 算法的步驟算法的步驟 第一步 初始化數(shù)據(jù)庫 根據(jù)條件初始化數(shù)據(jù)庫 掃描事務(wù)數(shù)據(jù)庫 從中找 出所有的項(xiàng)集長度為 k 1 的項(xiàng)集 且支持度大于 s 形成頻繁 1 項(xiàng)集 Lk 第二步 根據(jù)頻繁 k 項(xiàng)集產(chǎn)生候選 k 十 1 項(xiàng)候選項(xiàng)集 Ck 1 如果 Ck 1 進(jìn)入下一步 否則循環(huán)結(jié)束 第三步 掃描數(shù)據(jù)庫 以確定每個候選項(xiàng)集的支持度 第四步 刪除候選項(xiàng)中支持度小于 s 的候選項(xiàng) 形成 k 1 頻繁項(xiàng)集 Lk 1 第五步 k k 1 轉(zhuǎn)入第二步 Apriori 算法的第一步就是發(fā)現(xiàn)頻繁 1 項(xiàng)集 L1 在第二至第五步 利用 Lk 1 產(chǎn)生 Ck以便獲得 Lk 在這個過程產(chǎn)生相應(yīng)的候選項(xiàng)集 然后利用 Apriori 算法 性質(zhì)刪除那些子集為非頻繁項(xiàng)集的候選項(xiàng)集 一旦產(chǎn)生所有候選 就要掃描數(shù) 據(jù)庫 由此求出每個候選項(xiàng)集的支持度 算法中的第三步 最終滿足最小支持 度的候選項(xiàng)集組成了頻繁項(xiàng)集 Lk 1 這樣可以利用該過程來幫助從所獲得頻繁 項(xiàng)集中生成所有的關(guān)聯(lián)規(guī)則 Apriori 過程完成兩個操作 一是連接 二是剪枝操作 正如上面所介紹的 在連接過程中 Lk與 Lk連接以產(chǎn)生潛在候選項(xiàng)集 算法中的第二步 剪枝過程 中 算法中的第四步 利用 Apriori 性質(zhì)刪除候選項(xiàng)集中那些子集為非頻繁項(xiàng)集的 項(xiàng)集 4 4 Apriori 算法的特點(diǎn)及局限性算法的特點(diǎn)及局限性 Apriori 算法利用候選項(xiàng)集和頻繁項(xiàng)集的相互作用 得到了全部頻集 并通 過對候選項(xiàng)集進(jìn)行剪枝 大大地減少了候選項(xiàng)集的尺寸 獲得了令人滿意的結(jié) 果 然而 當(dāng)面對挖掘?qū)ο缶哂蟹倍嗟念l繁模式或者用戶給定的最小支持度較 低時 Apriori 算法仍然有可能因?yàn)槿缦聝蓚€方面的巨大開銷而面臨困境 1 在處理候選項(xiàng)集方面 如果算法得到了大量的頻繁1 項(xiàng)集 那么 在產(chǎn) 生候選項(xiàng)集時 會遇到大量候選項(xiàng)集難以處理的情況 所以 在有大量候選項(xiàng) 集產(chǎn)生的情況下 Apriori 算法基本無法運(yùn)行 2 Apriori 算法采用的模式匹配方式 在檢測大量的候選項(xiàng)集 特別是在 內(nèi)蒙古科技大學(xué)畢業(yè)論文 20 挖掘長模式時 對數(shù)據(jù)庫的重復(fù)掃描非常多 大量的時間消耗在內(nèi)存與數(shù)據(jù)庫 中的數(shù)據(jù)的交換上 8 4 5 Apriori 算法評價算法評價 在許多情況下 Apriori算法的候選產(chǎn)生檢查方法大幅度壓縮了候選項(xiàng)集的 大小 并導(dǎo)致很好的性能 然而 它有兩種開銷可能并非微不足道的 9 1 它可能產(chǎn)生大量候選項(xiàng)集 例如 如果有104個頻繁1 項(xiàng)集 則需要產(chǎn) 107 個頻繁2 項(xiàng)集 并累計(jì)和檢查其頻繁性 為發(fā)現(xiàn)長度為100的頻繁模式 a1 a2 a100 則需產(chǎn)生多達(dá)約1030個候選 2 它可能需要重復(fù)的掃描數(shù)據(jù)庫 通過模式匹配檢查一個很大的候選集 合 為了提高Apriori 算法的效率 已經(jīng)提出了許多Apriori 算法的變形 3 無法對稀有信息進(jìn)行分析 由于頻繁集的使用了參數(shù)min sup 所以就 無法對小于min sup的事件進(jìn)行分析 而如果將min sup設(shè)成一個很低的值 那 么算法的效率就成了一個很難處理的問題 內(nèi)蒙古科技大學(xué)畢業(yè)論文 21 第五章第五章 應(yīng)用應(yīng)用 Apriori 算法的實(shí)例分析算法的實(shí)例分析 居民在飲食方面的合理設(shè)置 對我們的生活質(zhì)量起到重要的作用 合理的 飲食習(xí)慣 使我們身體健康 生活質(zhì)量也有一定的提高 5 1 研究說明研究說明 通過對 2000 2009 年 2004 年除外 全國各地區(qū)城鎮(zhèn)居民對淀粉及薯類 豆制品 油脂類 肉禽及制品 水產(chǎn)品類 菜類 干鮮瓜果類和奶及奶制品 9 類食品的消費(fèi)情況及各地區(qū)城鎮(zhèn)居民的歷年人均收入及人均消費(fèi)性支出進(jìn)行統(tǒng) 計(jì) 并進(jìn)行一系列的處理之后 進(jìn)行相關(guān)的數(shù)據(jù)挖掘和關(guān)聯(lián)規(guī)則分析 中國國家統(tǒng)計(jì)局組織實(shí)施全國及省 自治區(qū) 直轄市國民經(jīng)濟(jì)核算制度和 全國投入產(chǎn)出調(diào)查 并建立信息數(shù)據(jù)庫 通過統(tǒng)計(jì)數(shù)據(jù)可以了解到一些相應(yīng)的 信息 但是 將同一類型的數(shù)據(jù)結(jié)合到一起 獲得的意義就會更大 本文就是 采用收集 9 類食品的相關(guān)數(shù)據(jù) 進(jìn)行數(shù)據(jù)挖掘 得到關(guān)聯(lián)規(guī)則 食品消費(fèi)的相關(guān)性分析可以更加明確居民在食品購物方面的一些內(nèi)在聯(lián)系 為政府及商家提供了相關(guān)的銷售意見 5 2 研究方法研究方法 首先 采集相關(guān)數(shù)據(jù)信息 其次 對數(shù)據(jù)進(jìn)行處理 得到布爾數(shù)據(jù)庫 第 三 應(yīng)用 Apriori 算法對布爾數(shù)據(jù)庫進(jìn)行數(shù)據(jù)挖掘 得到關(guān)聯(lián)規(guī)則 最后 對得 到的結(jié)果進(jìn)行相關(guān)分析 5 2 1 數(shù)據(jù)采集數(shù)據(jù)采集 在中國國家統(tǒng)計(jì)局公布的 2000 2009 年統(tǒng)計(jì)年鑒中篩選出 淀粉及薯類 豆制品 油脂類 肉禽及制品 水產(chǎn)品類 菜類 干鮮瓜果類和奶及奶制品 9 類食品的消費(fèi)情況及各地區(qū)城鎮(zhèn)居民的歷年人均收入和人均消費(fèi)性支出 其中 包括 2000 2009 年 2004 年除外 的 9 年間的 31 個省 市 自治區(qū)的情況 得 到 31 個 省 市 自治區(qū) 9 年間 9 類食品的 279 9 個數(shù)據(jù) 內(nèi)蒙古科技大學(xué)畢業(yè)論文 22 5 2 2 數(shù)據(jù)處理數(shù)據(jù)處理 首先 將得到九種食品的消費(fèi)支出與全年的消費(fèi)性支出比值及全年消費(fèi)性 支出與人均收入的比值 得到的數(shù)值都為 0 1 之間的小數(shù) 其次 將上面得到的數(shù)值進(jìn)行分區(qū) 將 9 類食品與消費(fèi)性支出的比值等分 為 3 個區(qū)間 全年消費(fèi)性支出與人均收入的比值等分為 4 個區(qū)間 應(yīng)用 Excel 處理將比值落在對應(yīng)區(qū)間的為 1 另外的幾個區(qū)間則為 0 得到新的數(shù)據(jù)庫 打開數(shù)據(jù)文件所在的 Excel 表格 在右邊的空白出 N2 中輸入 c2 d2 在 N2 中得到的就是消費(fèi)性支出與工資的比例 將鼠標(biāo)放在此時 N2 的黑色 框的右下角當(dāng)鼠標(biāo)是十字形時 向下拖拽 得到的就是 C 列與 D 列各行的比值 E 列之后是 E 列與 C 列的比值 將得到的結(jié)果重新存儲到新的表格中 得到的 比例數(shù)據(jù)為 打開比例數(shù)據(jù)表格 同樣是在右邊的空白處 N2 輸入 IF AND C2 0 33 C2 0 48 1 0 表示落在 0 33 0 48 區(qū)間的數(shù)值輸出為 1 不在這個區(qū)間的數(shù)值為 0 把得到的結(jié)果存儲到新的數(shù)據(jù)表格 5 2 3 應(yīng)用算法進(jìn)行數(shù)據(jù)挖掘應(yīng)用算法進(jìn)行數(shù)據(jù)挖掘 應(yīng)用 MATLAB 軟件進(jìn)行數(shù)據(jù)挖掘 通過 File Import Data 將生成的布爾數(shù)據(jù)庫導(dǎo)入到 MATLAB 中 內(nèi)蒙古科技大學(xué)畢業(yè)論文 24 將導(dǎo)入到 MATLAB 中的 Data 文件 重命名為 X 在 MATLAB 中新建 4 個 M 文件 association rules m subset m setsub m in m 其中 association rules m 為主程 序 在 command window 窗口中分別輸入 內(nèi)蒙古科技大學(xué)畢業(yè)論文 25 得到的頻繁 2 項(xiàng)集為 內(nèi)蒙古科技大學(xué)畢業(yè)論文 26 得到的頻繁 3 項(xiàng)集為 內(nèi)蒙古科技大學(xué)畢