【正文】 信息越是出乎意料 ,就可能越有價(jià)值 .在商業(yè)應(yīng)用中最典型的例子就是一家連鎖店通過(guò)數(shù)據(jù)挖掘發(fā)現(xiàn)了小孩尿布和啤酒之間有著驚人的聯(lián)系 . 數(shù)據(jù)挖掘不能干什么 DM 不能告訴你某個(gè)模型對(duì)你的企業(yè)的實(shí)際價(jià)值 DM 是一個(gè)工具，他只是幫助商業(yè)人士更深入、更容易地分析數(shù)據(jù)，但是無(wú)法告訴你某個(gè)模型對(duì)你的企業(yè)的實(shí)際價(jià)值， DM 中得到的模型必須在現(xiàn)實(shí)生活中進(jìn)行驗(yàn)證， DM 不會(huì)在缺乏指導(dǎo)的情況下自動(dòng)的發(fā)現(xiàn)模型。 DM 永遠(yuǎn)不會(huì)替代有經(jīng)驗(yàn)的商業(yè)分析師或管理人員所起的作用，它只是一個(gè)強(qiáng)大的工具。 具體形式為 {X}→ {Y}，即通?？梢悦枋鰹?:當(dāng)一個(gè)事務(wù)中顧客購(gòu)買了一樣?xùn)|西 {鋼筆 }(這里 X=“鋼筆” )則很可能他同時(shí)還購(gòu)買了 {墨水 }(這里 Y= 墨水 )，這就是關(guān)聯(lián)規(guī)則。這種說(shuō)法有其一定的現(xiàn)實(shí)意義 :1)或許是該年齡段的經(jīng)常喝啤酒的人剛好家庭開始養(yǎng)育小孩 。然而不管怎樣，如果沒有數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則在這里的應(yīng)用，你是無(wú)論如何想象不出這樣有點(diǎn)驚人的“笑話”。 陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系開放性實(shí)驗(yàn)結(jié)題報(bào)告 4 聚類分析 ： 數(shù)據(jù)庫(kù)中的記錄可被化分為一系列有意義的子集，即聚類。聚類技術(shù)主要包括傳統(tǒng)的模式識(shí)別方法和數(shù)學(xué)分類學(xué)。 3 關(guān)于關(guān)聯(lián)規(guī)則的討論 購(gòu)物籃分析 關(guān)聯(lián)規(guī)則挖掘的一個(gè)典型例子是購(gòu)物籃分析。如果顧客買牛奶，他也購(gòu)買面包的可能性有多大？ 什么商品組或集合顧客多半會(huì)在一次購(gòu)物時(shí)同時(shí)購(gòu)買？例如，買牛奶的顧客有 80%也同時(shí)買面包，或買鐵錘的顧客中有 70%的人同時(shí)也買鐵釘，這就是從購(gòu)物籃數(shù)據(jù)中提取的關(guān)聯(lián)規(guī)則。一種策略是：經(jīng)常一塊購(gòu)買的商品可以放近一些，以便進(jìn)一步刺激這些商品一起銷售，例如，如果顧客購(gòu)買計(jì)算機(jī) 又傾向于同時(shí)購(gòu)買財(cái)務(wù)軟件，那么將硬件擺放離軟件陳列近一點(diǎn)，可能有助于增加兩者的銷售。 關(guān)聯(lián)規(guī)則基本問題描述 關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫(kù)中數(shù)據(jù)項(xiàng)之間存在的潛在關(guān)系的規(guī)則 ,形式為“ A1∧A2 ∧ ... ∧ Am=B1 ∧ B2 ∧ ... ∧ Bn ” , 其中Ai(i=1,2,......,m),Bj(j=1,2,......,n)是數(shù)據(jù)庫(kù)中的數(shù)據(jù)項(xiàng) .數(shù)據(jù)項(xiàng)之間的陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系開放性實(shí)驗(yàn)結(jié)題報(bào)告 5 關(guān)聯(lián)規(guī)則即根據(jù)一個(gè)事務(wù)中某些項(xiàng)的出現(xiàn) ,可推導(dǎo)出另一些項(xiàng)在同一事務(wù)中也出現(xiàn) . 挖掘關(guān) 聯(lián)規(guī)則的問題描述如下 : 設(shè) : I={i1,i2......,im}是所有項(xiàng)目的集合 . D 是所有事務(wù)的集合 (即數(shù)據(jù)庫(kù) ), 每個(gè)事務(wù) T 是一些項(xiàng)目的集合 , T 包含在 I 中 , 每個(gè)事務(wù)可以用唯一的標(biāo)識(shí)符 TID 來(lái)標(biāo)識(shí) . 設(shè) X為某些項(xiàng)目的集合 ,如果 X 包含在 T 中 , 則稱事務(wù) T包含X, 關(guān)聯(lián)規(guī)則則表示為如下形式 (X 包含在 T)=(Y 包含在 T)的蘊(yùn)涵式 , 這里 X包含在 I中 , Y 包含在 I 中 , 并且 X∧ Y=Φ . 其意義在于一個(gè)事務(wù)中某些項(xiàng)的出現(xiàn) ,可推導(dǎo)出另一些項(xiàng)在同一事務(wù)中也出現(xiàn) (為簡(jiǎn)單化 ,將 (X包含在 T)=(Y包含在 T)表示為 X=Y, 這里 ,‘ =’稱為‘關(guān)聯(lián)’操作 , X 稱為關(guān)聯(lián)規(guī)則的先決條件 , Y稱為關(guān)聯(lián)規(guī)則的結(jié)果 ). 事務(wù)集 D中的規(guī)則 X=Y 是由支持度 s(support)和置信度 c(confidence)約束 ,置信度表示規(guī)則的強(qiáng)度 , 支持度表示在規(guī)則中出現(xiàn)的頻度 。 規(guī)則 X=Y 的支持度 s 定義為 : 在 D 中包含 X∪ Y 的事務(wù)所占比例為 s%, 表示同時(shí)包含 X和 Y的事務(wù)數(shù)量與 D 的 總事務(wù)量之比 。 (3) XK是 K 維頻繁項(xiàng)集，如果所有 K1維 頻繁項(xiàng)集集合 XK1中包含 XK 的 K1維子項(xiàng)集的個(gè)數(shù)小于 K，則 XK不可能是 K維最大頻繁數(shù)據(jù)項(xiàng)集。如果高頻繁數(shù)據(jù)項(xiàng)集XK1，中包含 XK的 k，則存在 XK的 K1 維子項(xiàng)集不是頻繁數(shù)據(jù)項(xiàng)集，由結(jié)論 (2)知 K 維數(shù)據(jù)項(xiàng)集本身也不是高頻繁數(shù)據(jù)項(xiàng)集 。表 31中記錄了 5 個(gè)顧客的購(gòu)物單。 KDD 系統(tǒng)通過(guò)特定算法（例如著名的 Apriori(驗(yàn)證 )算法及或改進(jìn)算法）多次掃描數(shù)據(jù)庫(kù)，依次得出如表 2 和表 3。 單項(xiàng)統(tǒng)計(jì) 支持度 {啤酒 } 4/5 {尿布 } 4/5 {嬰兒爽身粉 } 2/5 {牛奶 } 2/5 表 32 表 33 從單項(xiàng)統(tǒng)計(jì)中看出 80%的顧客買了啤酒、 80%的顧客買了尿布。還可觀察到買了啤酒顧客中又買了尿布的占 {啤酒，尿布 }/{啤酒 }=75% (稱為置信度 )。 R1：啤酒→尿布 ,S=60%， C=R2：尿布→啤酒 ,S=60%， C=R3：牛奶→啤酒 , S=40%， C=R4：啤酒→牛奶 , S=40%， C=R5：尿布→爽身粉。 S=40%， C=雙項(xiàng)統(tǒng)計(jì) 支持度 {啤酒，尿布 } 3/5 {啤酒，牛奶 } 2/5 {尿布，嬰兒爽身粉 } 2/5 陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系開放性實(shí)驗(yàn)結(jié)題報(bào)告 8 KDD 規(guī)則反映了物品之間的表面聯(lián)系，不一定是現(xiàn)實(shí)世界的因果關(guān)系。例如， R6“嬰兒爽身粉→尿布”有很高的置信度，是合理可理解的， R3有很高的置信度將提示進(jìn)一 步的調(diào)查分析，本例中是因?yàn)橛?xùn)練資料太少引起的失真。 4 Apriori 算法的描述 Apriori 算法的說(shuō)明 在 Apriori 算法中 ,尋找最大項(xiàng)目集的基本思想是 : 算法需要對(duì)數(shù)據(jù)集進(jìn)行多步處理 .第一步 ,簡(jiǎn)單統(tǒng)計(jì)所有含一個(gè)元素項(xiàng)目集出現(xiàn)的頻率 ,并找出那些不小于最小支持度的項(xiàng)目集 , 即一維最大項(xiàng)目集 . 從第二步開始循環(huán)處理直到再?zèng)]陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系開放性實(shí)驗(yàn)結(jié)題報(bào)告 9 有最大項(xiàng)目集生成 . 循 環(huán)過(guò)程是 : 第 k 步中 , 根據(jù)第 k1 步生成的 (k1)維最大項(xiàng)目集產(chǎn)生 k 維侯選項(xiàng)目集 , 然后對(duì)數(shù)據(jù)庫(kù)進(jìn)行搜索 , 得到侯選項(xiàng)目集的項(xiàng)集支持度 , 與最小支持度比較 , 從而找到 k維最大項(xiàng)目集 . 為方便后文敘述，現(xiàn)約定如下 : ,每個(gè)項(xiàng)目用 TID,item來(lái)標(biāo)識(shí) , 這里 TID 表示相應(yīng)事務(wù)的標(biāo)識(shí)符 , item 則表示項(xiàng)目名稱 . size. 當(dāng)項(xiàng)目集的 size=k時(shí) , 稱該項(xiàng)目集為 kitemset(k 維項(xiàng)目集 ). 下文中遇到的以下符號(hào) ,分別代表相應(yīng)的內(nèi)容 kitemset k 維項(xiàng)目集 Lk 具有最小支持度的最大 kitemset Ck 侯選的 kitemsets(潛在的最大項(xiàng)目集 ) Apriori 算法的描述 Apriori 算法的第一步是簡(jiǎn)單統(tǒng)計(jì)所有含一個(gè)元素的項(xiàng)集出現(xiàn)的頻率 ,來(lái)決定最大的一維項(xiàng)目集 .在第 k步 ,分兩個(gè)階段 ,首先用一函數(shù) sc_candidate(候選 ),通過(guò)第 (k1)步中生成的最大項(xiàng)目集 Lk1來(lái)生成侯選項(xiàng)目集 Ck. 然后搜索數(shù)據(jù)庫(kù)計(jì)算侯選項(xiàng)目集 Ck的支持度 . 為了更快速地計(jì)算 Ck中項(xiàng)目的支持度 , 文 中使用函數(shù) count_support 計(jì)算支持度 . Apriori 算法描述如下 (1) C1={candidate1itemsets}。 (3) For(k=2,Lk1≠Φ ,k++) //直到不能再生成最大項(xiàng)目集為止 陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系開放性實(shí)驗(yàn)結(jié)題報(bào)告 10 (4) Ck=sc_candidate(Lk1)。 //包含在事務(wù) t中的侯選項(xiàng)目集 (7) for all candidates c∈ Ct (8) =+1。 (11) next (12) resultset=resultset∪ Lk 其中 , D 表示數(shù)據(jù)庫(kù) 。 resultset 表示所有最大項(xiàng)目集 . Sc_candidate 函數(shù) 該函數(shù)的參數(shù)為 Lk1,即 : 所有最大 k1 維項(xiàng)目集 ,結(jié)果返回含有 k 個(gè)項(xiàng)目的侯選項(xiàng)目集 ,Ck是 k維最大項(xiàng)目集的超集 ,通過(guò)函數(shù) count_support計(jì)算項(xiàng)目的支持度 ,然后生成 Lk. 該函數(shù)是如何完成這些功能的 , 詳細(xì)說(shuō)明如下 : 首先 , 通過(guò)對(duì) Lk1 自連接操作生成 Ck39。={X∪ X39。∈ Lk1,|X∩ X39。 用集合表 示 :Ck=={X∈ Ck39。, 則 c39。也為最大項(xiàng)目集 . (2) 在 prune 步中 , 刪除 Ck39。中所有不在 Lk1中的 k1維子集 . count_support 函數(shù) count_support函數(shù)為是以 t和 Ck 為條件 . 來(lái)求出 t 中所包含的侯選項(xiàng)目集的 . 同時(shí)計(jì)算出所包含的侯選項(xiàng)目集的數(shù)目 . Apriori 算法的舉例 示例說(shuō)明 Apriori 算法運(yùn)作過(guò)程 有 一數(shù)據(jù)庫(kù) D, 其中有四個(gè)事務(wù)記錄 , 分別表示為 陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系開放性實(shí)驗(yàn)結(jié)題報(bào)告 12 TI