1、第8章 知識類數(shù)據(jù)挖掘技術(shù)8.1 知識發(fā)現(xiàn)系統(tǒng)的結(jié)構(gòu)8.2 關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘技術(shù)8.3 神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)挖掘技術(shù)8.4 遺傳算法的數(shù)據(jù)挖掘技術(shù)8.1 知識發(fā)現(xiàn)系統(tǒng)的結(jié)構(gòu)知識發(fā)現(xiàn)系統(tǒng)管理器：控制并管理整個(gè)知識發(fā)現(xiàn)過程，包括數(shù)據(jù)選擇過程、抽取算法的選擇及使用過程、發(fā)現(xiàn)的評價(jià)過程。知識庫和商業(yè)分析員數(shù)據(jù)倉庫的數(shù)據(jù)庫接口數(shù)據(jù)選擇知識發(fā)現(xiàn)引擎：分類、聚類、偏差分析、模糊推理等發(fā)現(xiàn)評價(jià)發(fā)現(xiàn)描述8.2 關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘技術(shù)自然界中某種事物發(fā)生時(shí)其他事物也會發(fā)生的這樣一種聯(lián)系稱之為關(guān)聯(lián)。反映事件之間依賴或關(guān)聯(lián)的知識稱為關(guān)聯(lián)型知識（又稱依賴關(guān)系）關(guān)聯(lián)規(guī)則挖掘就是從大量的數(shù)據(jù)中挖掘出有價(jià)值描述數(shù)據(jù)項(xiàng)之間相互聯(lián)系

2、的有關(guān)知識 關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的主要對象是交易型數(shù)據(jù)庫，一個(gè)交易一般由交易處理時(shí)間，一組顧客購買的物品，有時(shí)也有顧客標(biāo)識號(如信用卡號)組成。交易號（TID） 項(xiàng)集合（Itemsets） T100 I1，I2，I5 T200 I2，I4 T300 I2，I3 T400 I1，I2，I4 T500 I1，I3 For rule A C:support = support(A &C) = 50%confidence = support(A &C)/support(A) = 66.6%定義：關(guān)聯(lián)規(guī)則挖掘的交易數(shù)據(jù)集記為D（一般為交易數(shù)據(jù)庫），DT1，T2，Tk，,Tn，Tk（k1,2,，n）稱為交易，對應(yīng)

3、每一個(gè)交易有唯一的標(biāo)識，記作TID。元素im（m1,2,，p）稱為項(xiàng)。設(shè)I=i1，i2，im是D中全體項(xiàng)組成的集合，且TkI。設(shè)X是一個(gè)I中項(xiàng)的集合，如果XTk，那么稱交易Tk包含項(xiàng)集X。若X,Y為項(xiàng)集，XI, YI，并且XY=，則形如X = Y的表達(dá)式稱為關(guān)聯(lián)規(guī)則。 關(guān)聯(lián)規(guī)則形式化定義規(guī)則XY在交易數(shù)據(jù)集D中的置信度是對關(guān)聯(lián)規(guī)則準(zhǔn)確度的衡量。度量關(guān)聯(lián)規(guī)則的強(qiáng)度。即在所有出現(xiàn)了X的活動中出現(xiàn)Y的頻率，即規(guī)則XY的必然性有多大。記為confidence(XY)。計(jì)算方法：包含X和Y的交易數(shù)與包含X的交易數(shù)之比：confidence(XY) = P(YX) = |T: XYT，TD|/|T:XT，

4、TD|100%規(guī)則XY在交易數(shù)據(jù)集D中的支持度是對關(guān)聯(lián)規(guī)則重要性的衡量，反映關(guān)聯(lián)是否是普遍存在的規(guī)律，說明這條規(guī)則在所有交易中有多大的代表性。即在所有交易中X與Y同時(shí)出現(xiàn)的頻率記為：support(XY)。計(jì)算方法：交易數(shù)據(jù)集中同時(shí)包含X和Y的交易數(shù)與所有交易數(shù)之比：support(XY) = P(XY) = |T: XYT，TD|/|D|100%（其中|D|是交易數(shù)據(jù)集D中的所有交易數(shù)）可信度（置信度）支持度 關(guān)聯(lián)規(guī)則度量交易號（TID） 項(xiàng)集合（Itemsets） T100 I1，I2，I5 T200 I2，I4 T300 I2，I3 T400 I1，I2，I4 T500 I1，I3 求

5、I2 I4的置信度和支持度最小置信度閾值最小支持度閾值同時(shí)滿足最小置信度閾值和最小支持度閾值的關(guān)聯(lián)規(guī)則為強(qiáng)關(guān)聯(lián)規(guī)則，是有意義有價(jià)值。 在給定一個(gè)交易數(shù)據(jù)集D，挖掘關(guān)聯(lián)規(guī)則問題就是產(chǎn)生支持度和置信度分別大于用戶給定的最小支持度閾值和最小置信度閾值的關(guān)聯(lián)規(guī)則。項(xiàng)集的出現(xiàn)頻度（項(xiàng)集的支持度）：整個(gè)交易數(shù)據(jù)集D中包含該項(xiàng)集的交易記錄數(shù)最小支持頻度：滿足最小支持閾值所對應(yīng)的交易記錄數(shù)頻繁k項(xiàng)集：滿足最小支持閾值的項(xiàng)集挖掘交易數(shù)據(jù)庫D中所有關(guān)聯(lián)規(guī)則的問題可以被劃分為兩個(gè)子問題：找出所有具有最小支持度的項(xiàng)集(頻繁項(xiàng)集) 。用Apriori、FP-Growth等算法來找出頻繁項(xiàng)集。使用頻繁項(xiàng)集生成期望的關(guān)聯(lián)規(guī)

6、則。對于每一個(gè)頻繁項(xiàng)集l，找出其中所有的非空子集；然后，對于每一個(gè)這樣的子集a，如果support(l)與support(a)的比值大于最小可信度，則存在規(guī)則a=(l-a)。交易號項(xiàng)集合T100 I1，I2，I5 T200 I2，I4 T300 I2，I3 T400 I1，I2，I4 T500 I1，I3 T600 I2，I3 T700 I1，I3 T800 I1，I2，I3，I5 T900 I1，I2，I3 表1 交易數(shù)據(jù)庫D 例：找出頻繁項(xiàng)集Apriori算法項(xiàng)集支持度計(jì)數(shù)I16I27I36I42I52項(xiàng)集支持度計(jì)數(shù)I16I27I36I42I52C1L1掃描D，對每個(gè)候選計(jì)數(shù)比較候選支持度

7、計(jì)數(shù)與最小支持度計(jì)數(shù)找出頻繁1項(xiàng)集的集合L1例：最小支持度閾值 為2項(xiàng)集支持度計(jì)數(shù)I16I27I36I42I52項(xiàng)集I1，I2I1，I3I1，I4I1，I5I2，I3I2，I4I2，I5I3，I4I3，I5I4，I5L1C2由L1產(chǎn)生候選C2Lk-1用于產(chǎn)生候選Ck 連接&剪枝項(xiàng)集支持度計(jì)數(shù)I1，I24I1，I34I1，I41I1，I52I2，I34I2，I42I2，I52I3，I40I3，I51I4，I50項(xiàng)集支持度計(jì)數(shù)I1，I24I1，I34I1，I52I2，I34I2，I42I2，I52C2L2比較候選支持度計(jì)數(shù)與最小支持度計(jì)數(shù)掃描D，對每個(gè)候選計(jì)數(shù)項(xiàng)集支持度計(jì)數(shù)I1，I24I1，I34

8、I1，I52I2，I34I2，I42I2，I52L2項(xiàng)集I1，I2，I3I1，I2，I5由L2產(chǎn)生候選C3C3連接&剪枝連接：C3L2 L2I1,I2, I1,I3, I1,I5, I2,I3, I2,I4, I2,I5 I1,I2, I1,I3, I1,I5, I2,I3, I2,I4, I2,I5 =I1,I2,I3, I1,I2,I5, I1,I3,I5, I2,I3,I4, I2,I3,I4, I2,I3,I5 ,I2,I4,I5項(xiàng)集支持度計(jì)數(shù)I1，I24I1，I34I1，I52I2，I34I2，I42I2，I52L2項(xiàng)集支持度計(jì)數(shù)I1，I2，I32I1，I2，I52C3掃描D，對每個(gè)

9、候選計(jì)數(shù)比較候選支持度計(jì)數(shù)與最小支持度計(jì)數(shù)項(xiàng)集支持度計(jì)數(shù)I1，I2，I32I1，I2，I52L3對每個(gè)交易，使用subset函數(shù)找出交易中是候選的所有子集，并對每個(gè)這樣的候選累加計(jì)數(shù)，所有滿足最小支持度的候選形成頻繁項(xiàng)集L。 輸入：交易數(shù)據(jù)庫D；最小支持度閾值min_sup。輸出：D中的頻繁項(xiàng)集L。方法：(1) L1find_frequent_1_itemset（D）；找頻繁項(xiàng)集1-項(xiàng)集;(2) for （ k=2; Lk-1 ; min_sup） apriori_gen(Lk-1,min_sup) 連接和剪枝。用于在 第k-1次遍歷中生成的Lk-1生成Ck for each t D 掃描數(shù)據(jù)

10、庫，確定每個(gè)候選項(xiàng)集的支持頻度 Ctsubset（Ck ，t）獲得t所包含的候選項(xiàng)集 for each cCt c.count； (3) Lk c Ck | c.count min_sup 由Ck生成Lk(4) return LL1 L2 . Lk Apriori算法procedure has_infrequent_itemset （c，Lk-1）for each（k1） subset s of cif s Lk-1 return true ；else return false ；The Apriori Algorithm ExampleDatabase DScan DC1L1L2C2C2Sc

11、an DC3L3Scan DLet the minimum supportIs 50%, i.e. minimumsupport count is 4 x 50%= 2.Example of Generating CandidatesL3=abc, abd, acd, ace, bcdSelf-joining: L3*L3abcd from abc and abdacde from acd and acePruning:acde is removed because ade is not in L3C4=abcd關(guān)聯(lián)規(guī)則的生成使用頻繁項(xiàng)集生成期望的關(guān)聯(lián)規(guī)則對于每一個(gè)頻繁項(xiàng)集l，找出其中所有的非空子集；然后，對于每一個(gè)這樣的子集a，如果support(l)與support(a)的比值大于最小可信度，則存在規(guī)則a=(l-a)。confidence