數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則

1、1關(guān)聯(lián)規(guī)則 Association Rules2內(nèi)容提要內(nèi)容提要 n引言引言nApriori Apriori 算法算法nFrequent-pattern tree Frequent-pattern tree 和和FP-growth FP-growth 算法算法n多維關(guān)聯(lián)規(guī)則挖掘多維關(guān)聯(lián)規(guī)則挖掘n相關(guān)規(guī)則相關(guān)規(guī)則n基于約束的關(guān)聯(lián)規(guī)則挖掘基于約束的關(guān)聯(lián)規(guī)則挖掘n總結(jié)總結(jié)3 關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘n在事務(wù)數(shù)據(jù)庫,關(guān)系數(shù)據(jù)庫和其它信息庫中的項或?qū)ο蟮募现g,發(fā)現(xiàn)頻繁模式,關(guān)聯(lián),相關(guān),或因果關(guān)系的結(jié)構(gòu).n頻繁模式: 數(shù)據(jù)庫中出現(xiàn)頻繁的模式(項集,序列,等等)4基本概念基本概念n項集項集n事務(wù)事務(wù)n關(guān)

2、聯(lián)規(guī)則關(guān)聯(lián)規(guī)則n事務(wù)數(shù)據(jù)集事務(wù)數(shù)據(jù)集 ( (例如右圖例如右圖) )n事務(wù)標識事務(wù)標識 TIDTID： 每一個事務(wù)關(guān)聯(lián)著一個標識每一個事務(wù)關(guān)聯(lián)著一個標識IT ,.,21miiiI BAIBIABA,D5基本概念基本概念n支持度支持度s snD D中包含中包含A A和和 B B 的事務(wù)數(shù)與總的事務(wù)數(shù)的比的事務(wù)數(shù)與總的事務(wù)數(shù)的比值值規(guī)則規(guī)則 A AB B 在數(shù)據(jù)集在數(shù)據(jù)集D D中的支持度為中的支持度為s, s, 其中其中s s 表表示示D D中包含中包含A A B B ( (即同時包含即同時包含A A和和B)B)的事務(wù)的百的事務(wù)的百分率分率. .|)(DTBADTBAs6基本概念基本概念n支持度支持

3、度s snD D中包含中包含A A和和 B B 的事務(wù)數(shù)與總的事務(wù)數(shù)的比的事務(wù)數(shù)與總的事務(wù)數(shù)的比值值規(guī)則規(guī)則 A AB B 在數(shù)據(jù)集在數(shù)據(jù)集D D中的支持度為中的支持度為s, s, 其中其中s s 表表示示D D中包含中包含A A B B ( (即同時包含即同時包含A A和和B)B)的事務(wù)的百的事務(wù)的百分率分率. .|)(DTBADTBAs7基本概念基本概念n可信度可信度 c cnD D中同時包含中同時包含A A和和B B的事務(wù)數(shù)與只包含的事務(wù)數(shù)與只包含A A的事務(wù)的事務(wù)數(shù)的比值數(shù)的比值|)(TADTTBADTBAc規(guī)則規(guī)則 A AB B 在數(shù)據(jù)集在數(shù)據(jù)集D D中的中的可信可信度為度為c,c,

4、 其中其中c c表示表示D D中包含中包含A A的事務(wù)中也包含的事務(wù)中也包含B B的百分率的百分率. .即可用條件概率即可用條件概率P(B|A)P(B|A)表示表示. . confidence( confidence(A A B )=P(B|A)B )=P(B|A) 條件概率條件概率 P(B|A) P(B|A) 表示表示A A發(fā)生的條件下發(fā)生的條件下B B也發(fā)生也發(fā)生的概率的概率. .8關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘n兩個基本步驟兩個基本步驟nStep one:Step one:找出所有的頻繁項集找出所有的頻繁項集n滿足最小支持度滿足最小支持度nStep two:Step two:找出所有的強關(guān)聯(lián)規(guī)

5、則找出所有的強關(guān)聯(lián)規(guī)則n由頻繁項集生成關(guān)聯(lián)規(guī)則由頻繁項集生成關(guān)聯(lián)規(guī)則n保留滿足最小可信度的規(guī)則保留滿足最小可信度的規(guī)則9Apriori Apriori 性質(zhì)性質(zhì)n定理定理(Apriori (Apriori 性質(zhì)性質(zhì)): ): 若若A A是一個頻繁項集是一個頻繁項集, ,則則A A的的每一個子集都是一個頻繁項集每一個子集都是一個頻繁項集. .n證明證明: :設(shè)設(shè)n n為事務(wù)數(shù)為事務(wù)數(shù). .假設(shè)假設(shè)A A是是l l個事務(wù)的子集個事務(wù)的子集, ,若若 A A A A , , 則則A A 為為l l (l (l l ) l )個事務(wù)的子集個事務(wù)的子集. .因此因此, , l/n s(l/n s(最小支

6、持度最小支持度), l), l/n s/n s也成立也成立. .10Apriori Apriori 算法算法nAprioriApriori算法是一種經(jīng)典的生成布爾型關(guān)聯(lián)規(guī)則的頻算法是一種經(jīng)典的生成布爾型關(guān)聯(lián)規(guī)則的頻繁項集挖掘算法繁項集挖掘算法. .算法名字是緣于算法使用了頻繁項算法名字是緣于算法使用了頻繁項集的性質(zhì)這一先驗知識集的性質(zhì)這一先驗知識. .n思想思想: Apriori : Apriori 使用了一種稱作使用了一種稱作level-wiselevel-wise搜索的搜索的迭代方法迭代方法, ,其中其中k-k-項集被用作尋找項集被用作尋找(k+1)-(k+1)-項集項集. .首先首先,

7、,找出頻繁找出頻繁1-1-項集項集, ,以以L1L1表示表示.L1.L1用來尋找用來尋找L2,L2,即即頻繁頻繁2-2-項集的集合項集的集合.L2.L2用來尋找用來尋找L3,L3,以此類推以此類推, ,直至沒直至沒有新的頻繁有新的頻繁k-k-項集被發(fā)現(xiàn)項集被發(fā)現(xiàn). .每個每個LkLk都要求對數(shù)據(jù)庫作都要求對數(shù)據(jù)庫作一次完全掃描一次完全掃描.11生成頻繁項集生成頻繁項集n中心思想中心思想: : 由頻繁由頻繁(k-1)-(k-1)-項集構(gòu)建候選項集構(gòu)建候選k-k-項集項集n方法方法n找到所有的頻繁找到所有的頻繁1-1-項集項集n擴展頻繁擴展頻繁(k-1)-(k-1)-項集得到候選項集得到候選k-k

8、-項集項集n剪除不滿足最小支持度的候選項集剪除不滿足最小支持度的候選項集12Apriori: Apriori: 一種候選項集生成一種候選項集生成- -測試方法測試方法nApriori Apriori 剪枝原理剪枝原理: : 若任一項集是不頻繁的若任一項集是不頻繁的, ,則其超則其超集不應(yīng)該被生成集不應(yīng)該被生成/ /測試測試! !n方法方法: : n由頻繁由頻繁k-k-項集生成候選項集生成候選(k+1)-(k+1)-項集項集, ,并且并且n在在DBDB中測試候選項集中測試候選項集n性能研究顯示了性能研究顯示了AprioriApriori算法是有效的和可伸縮算法是有效的和可伸縮(scalablil

9、ity)(scalablility)的的. .13The Apriori The Apriori 算法算法一個示例一個示例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scan14頻繁模式挖掘的挑戰(zhàn)頻繁模式挖掘的挑戰(zhàn)n挑戰(zhàn)n多次掃描事務(wù)數(shù)據(jù)庫n巨大數(shù)量的候選項集n繁重的計算候選項集的支持度工作n改進 Apriori: 大體的思路n減少事務(wù)數(shù)據(jù)庫的掃描次數(shù)n縮減候選項集的數(shù)量n使候選項集的支持度計算更加方便15內(nèi)容提要內(nèi)容提要 n引言nApriori 算法nFrequent-pattern tree 和FP-growth 算法n多維關(guān)聯(lián)規(guī)則挖掘n相關(guān)

10、規(guī)則n基于約束的關(guān)聯(lián)規(guī)則挖掘n總結(jié)16頻繁模式挖掘的瓶頸n多次掃描數(shù)據(jù)庫是高代價的n長模式的挖掘需要多次掃描數(shù)據(jù)庫以及生成許多的候選項集n找出頻繁項集 i1i2i100n掃描次數(shù): 100n候選項集的數(shù)量: (1001) + (1002) + + (110000) = 2100-1 = 1.27*1030 !n瓶頸:候選項集-生成-測試n我們能否避免生成候選項集?17不生成候選項集的頻繁模式挖掘n利用局部頻繁的項由短模式增長為長模式n“abc” 是一個頻繁模式n得到所有包含 “abc”的事務(wù): DB|abcn“d” 是 DB|abc 的一個局部頻繁的項 abcd 是一個頻繁模式18FP Gro

11、wth算法 (Han, Pei, Yin 2000)nApriori算法的一個有問題的方面是其候選項集的生成n指數(shù)級增長的來源n另一種方法是使用分而治之的策略(divide and conquer)n思想思想: : 將數(shù)據(jù)庫的信息壓縮成一個描述頻繁項相關(guān)信息的頻繁模式樹19利用FP-樹進行頻繁模式挖掘n思想: 頻繁模式增長n遞歸地增長頻繁模式借助模式和數(shù)據(jù)庫劃分n方法 n對每個頻繁項,構(gòu)建它的條件模式基,然后構(gòu)建它的條件FP-樹.n對每個新創(chuàng)建的條件FP-樹重復(fù)上述過程n直至結(jié)果FP-樹為空,或者它僅包含一個單一路徑.該路徑將生成其所有的子路徑的組合,每個組合都是一個頻繁模式.20頻繁 1-項

12、集n最小支持度為20% (計數(shù)為 2) 事務(wù)數(shù)據(jù)庫 支持度計數(shù) 頻繁1-項集21FP-樹 構(gòu)建按支持度降序排列22FP-樹 構(gòu)建 創(chuàng)建根結(jié)點null 掃描數(shù)據(jù)庫 事務(wù)1: I1, I2, I5 排序: I2, I1, I5 處理事務(wù) 以項的順序增加結(jié)點 標注項及其計數(shù)(I2,1)(I1,1)(I5,1)1I50I40I31I11I2 維護索引表23FP-樹 構(gòu)建null(I2,2)(I1,1)(I5,1)0I51I40I30I12I2(I4,1)24FP-樹 構(gòu)建null(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(I4,1)(I3,2)(I3,2)(I1,2)(I3,2

13、)(I4,1)(I5,1)25FP-樹 構(gòu)建n掃描事務(wù)數(shù)據(jù)庫D一次,得到頻繁項的集合F及它們的支持度.將F按支持度降序排列成L,L是頻繁項的列表.n創(chuàng)建FP-樹的根, 標注其為NULL.對D中的每個事務(wù)進行以下操作:n根據(jù) L中的次序?qū)κ聞?wù)中的頻繁項進行選擇和排序. 設(shè)事務(wù)中的已排序的頻繁項列表為p|P,其中p表示第一個元素,P表示剩余的列表.調(diào)用insert_Tree(p|P,T).26挖掘 FP-treen從索引表中的最后一個項開始n找到所有包含該項的路徑n沿著結(jié)點-鏈接(node-links)n確定條件模式n路徑中符合頻度要求的模式n構(gòu)建 FP-tree Cn添加項至C中所有路徑,生成頻

14、繁模式n遞歸地挖掘C (添加項)n從索引表和樹中移除項27挖掘 FP-Treenull(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(I4,1)(I3,2)(I3,2)(I4,1)(I5,1)(I1,2)(I3,2) 前綴路徑(I2 I1,1)(I2 I1 I3, 1)條件路徑(I2 I1, 2) 條件 FP-tree (I2 I1 I5, 2), (I2 I5, 2), (I1 I5, 2)null(I2,2)(I1,2)28挖掘 FP-Tree29由事務(wù)數(shù)據(jù)庫構(gòu)建FP-樹f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem

15、frequency head f4c4a3b3m3p3min_support = 3TIDItems bought (ordered) frequent items100f, a, c, d, g, i, m, pf, c, a, m, p200a, b, c, f, l, m, of, c, a, b, m300 b, f, h, j, o, wf, b400 b, c, k, s, pc, b, p500 a, f, c, e, l, p, m, nf, c, a, m, p掃描DB一次,找到頻繁1項 (單一項模式)按支持度降序?qū)︻l繁項排序為 F-list再次掃描DB,構(gòu)建FP-treeF

16、-list=f-c-a-b-m-p30劃分模式和數(shù)據(jù)庫n頻繁模式根據(jù)F-list可以被劃分為若干子集nF-list=f-c-a-b-m-pn包含 p的模式n包含 m 但包含 p的模式nn包含 c 但不包含 a ,b, m, p的模式n模式 fn完整性 和 非冗余性31從P的條件數(shù)據(jù)庫找出包含P的模式n從 FP-tree的索引表的頻繁項開始n沿著每個頻繁項p的鏈接遍歷 FP-treen累積項p的所有轉(zhuǎn)換前綴路徑來形成的p的條件模式基條件模式基條件模式基項項 條件模式基條件模式基cf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1f:4c:1b:

17、1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p332遞歸: 挖掘每個條件FP-treef:3c:3a:3m-條件條件 FP-tree“am”的條件模式基: (fc:3)f:3c:3am-條件條件 FP-tree“cm”的條件模式基: (f:3)f:3cm-條件條件 FP-tree“cam”的條件模式基: (f:3)f:3cam-條件條件 FP-tree33一個特例: FP-tree中的單一前綴路徑n假定 (條件的) FP-tree T 有一個共享的單一前綴路徑 Pn挖掘可以分為兩部分n將單一前綴路徑約簡為

18、一個結(jié)點n將兩部分的挖掘結(jié)果串聯(lián)a2:n2a3:n3a1:n1b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1r1=34通過 DB 投影(Projection)使FP-growth可伸縮nFP-tree 不能全放入內(nèi)存?DB 投影n首先將一個數(shù)據(jù)庫劃分成一個由若干投影(Projected)數(shù)據(jù)庫組成的集合n然后對每個投影數(shù)據(jù)庫構(gòu)建和挖掘 FP-treenParallel projection vs. Partition projection 技術(shù)nParallel projection is space costly35Par

19、tition-based ProjectionnParallel projection 需要很多磁盤空間nPartition projection 節(jié)省磁盤空間Tran. DB fcampfcabmfbcbpfcampp-proj DB fcamcbfcamm-proj DB fcabfcafcab-proj DB fcba-proj DBfcc-proj DBff-proj DB am-proj DB fcfcfccm-proj DB fff36改進途徑n使用哈希表存儲候選k-項集的支持度計數(shù)n移除不包含頻繁項集的事務(wù)n對數(shù)據(jù)采樣n劃分數(shù)據(jù)n若一個項集是頻繁的,則它必定在某個數(shù)據(jù)分區(qū)中是頻繁

20、的.37FP-tree 結(jié)構(gòu)的優(yōu)點n完整性 n保持了頻繁項集挖掘的完整信息n沒有打斷任何事務(wù)的長模式n緊密性n減少不相關(guān)的信息不頻繁的項沒有了n項按支持度降序排列: 越頻繁出現(xiàn),越可能被共享n決不會比原數(shù)據(jù)庫更大 (不計結(jié)點鏈接和計數(shù)域)n對 Connect-4 數(shù)據(jù)庫, 壓縮比率可以超過10038內(nèi)容提要內(nèi)容提要 n引言nApriori 算法nFrequent-pattern tree 和FP-growth 算法n多維關(guān)聯(lián)規(guī)則挖掘n相關(guān)規(guī)則n基于約束的關(guān)聯(lián)規(guī)則挖掘n總結(jié)39挖掘多種規(guī)則或規(guī)律n多層(Multi-level),量化(quantitative)關(guān)聯(lián)規(guī)則, 相關(guān)(correlati

21、on)和因果(causality), 比率(ratio)規(guī)則, 序列 (sequential) 模式,浮現(xiàn)(emerging)模式, temporal associations, 局部周期(partial periodicity)n分類(classification),聚類(clustering),冰山立方體( iceberg cubes), 等等.40多層關(guān)聯(lián)規(guī)則n項常常構(gòu)成層次n可伸縮的(flexible)支持度設(shè)置: 在較低層的項預(yù)期有較低的支持度.n事務(wù)數(shù)據(jù)庫可以基于維度和層次編碼n探尋共享多層挖掘統(tǒng)一支持度Milksupport = 10%2% Milk support = 6%Sk

22、im Milk support = 4%Level 1min_sup = 5%Level 2min_sup = 5%Level 1min_sup = 5%Level 2min_sup = 3%減少的支持度41可伸縮的支持度約束的多層/多維(ML/MD)關(guān)聯(lián)規(guī)則n為什么設(shè)置可伸縮的支持度?n實際生活中項的出現(xiàn)頻率變化巨大n在一個商店購物籃中的鉆石,手表,鋼筆n統(tǒng)一的支持度未必是一個有趣的模型n一個可伸縮模型n較低層的,較多維的組合以及長模式通常具有較小的支持度n總體規(guī)則應(yīng)該要容易說明和理解n特殊的項和特殊的項的組合可以特別設(shè)定(最小支持度)以及擁有更高的優(yōu)先級42多維關(guān)聯(lián)規(guī)則n單維規(guī)則:buys

23、(X, “milk”) buys(X, “bread”)n多維規(guī)則: 2 個維度或謂詞( predicates)n跨維度(Inter-dimension)關(guān)聯(lián)規(guī)則 (無重復(fù)謂詞)age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)n混合維度(hybrid-dimension)關(guān)聯(lián)規(guī)則 (重復(fù)謂詞)age(X,”19-25”) buys(X, “popcorn”) buys(X, “coke”)n分類(Categorical)屬性n有限的幾個可能值,值之間不可排序n數(shù)量(Quantitative)屬性n數(shù)值的,值之間有固有的排序43多層關(guān)聯(lián)規(guī)

24、則:冗余濾除n根據(jù)項之間的”先輩” (ancestor)關(guān)系,一些規(guī)則可能是冗余的. n示例nmilk wheat bread support = 8%, confidence = 70%n2% milk wheat bread support = 2%, confidence = 72%n我們說第1個規(guī)則是第2個規(guī)則的先輩.n一個規(guī)則是冗余的,當其支持度接近基于先輩規(guī)則的”預(yù)期”(expected)值.44多層關(guān)聯(lián)規(guī)則:逐步深化(Progressive Deepening)n一個自上而下的,逐步深化的方法:n 首先挖掘高層的頻繁項: milk (15%), bread (10%)n 然后挖掘

25、它們的較低層”較弱” (weaker)頻繁項: 2% milk (5%), wheat bread (4%)n多層之間不同的最小支持度閾值導(dǎo)致了不同的算法:n如果在多個層次間采用了相同的最小支持度,若t的任何一個先輩都是非頻繁的則扔棄(toss)t.n如果在較低層采用了減少的最小支持度，則只檢驗?zāi)切┫容叺闹С侄仁穷l繁的不可忽略的派生（descendents）即可45多維關(guān)聯(lián)規(guī)則挖掘的技術(shù)n搜索頻繁 k-謂詞集(predicate set):n示例: age, occupation, buys是一個 3-謂詞集n以age處理的方式,技術(shù)可以如下分類1. 利用數(shù)量屬性的統(tǒng)計離散(static di

26、scretization)方法 利用預(yù)先確定的概念層次對數(shù)量屬性進行統(tǒng)計離散化2. 量化關(guān)聯(lián)規(guī)則n基于數(shù)據(jù)的分布,數(shù)量屬性被動態(tài)地離散化到不同的容器空間(bins)3. 基于距離(Distance-based)的關(guān)聯(lián)規(guī)則n這是一個動態(tài)離散化的過程,該過程考慮數(shù)據(jù)點之間的距離46數(shù)量屬性的統(tǒng)計離散化n挖掘之前利用概念層次離散化n數(shù)值被范圍(ranges)替代.n關(guān)系數(shù)據(jù)庫中,找出所有的頻繁k-謂詞(predicate)集要求 k 或 k+1次表掃描.n數(shù)據(jù)立方體(data cube)非常適合數(shù)據(jù)挖掘.nN-維立方體的 cells 與謂詞集( predicate sets)相對應(yīng).n通過數(shù)據(jù)立方體

27、挖掘會非常快速.(income)(age)()(buys)(age, income)(age,buys) (income,buys)(age,income,buys)47量化關(guān)聯(lián)規(guī)則age(X,”30-34”) income(X,”24K - 48K”) buys(X,”high resolution TV”)n數(shù)值屬性動態(tài)離散化n這樣挖掘的規(guī)則的可信度或緊密度最大化n2-維 量化關(guān)聯(lián)規(guī)則: Aquan1 Aquan2 Acatn示例48量化關(guān)聯(lián)規(guī)則nARCS: Association Rule Clustering System (關(guān)聯(lián)規(guī)則聚類系統(tǒng)) 借鑒了圖像處理中的思想. 本質(zhì)上, 這種

28、方法映射一對數(shù)量屬性到滿足給定的分類屬性條件的2-維元組格. 然后對柵格搜索找到聚類點,由其生成關(guān)聯(lián)規(guī)則. nARCS 步驟: 裝箱(Binning)找出頻繁謂詞集(predicate sets) 聚類關(guān)聯(lián)規(guī)則 49量化關(guān)聯(lián)規(guī)則n裝箱(Binning): 劃分 過程被認為是裝箱,即稱作間隔為箱柜(bins). 三種常用裝箱策略是: Equiwidth binning, where the intervalsize of each bin is the same Equidepth: where each bin has approximately the same number of tupl

29、es assigned to it Homogeneity-based binning, where bin size is determined so that the tuples in each bin are uniformly distributed.50量化關(guān)聯(lián)規(guī)則n找出頻繁謂詞集: Once the 2-D array containing the count distribution for each category is set up, this can be scanned in order to find the frequent predicate sets that

30、 also satisfy minimum confidence.n聚類關(guān)聯(lián)規(guī)則: age(X,”34-35”) income(X,”31K - 50K”) buys(X,”high resolution TV”)51ARCS (Association Rules Clustering System)ARCS 1. Binning2. Frequent Items Set3. Clustering4. Optimization52nARCS: n成功的應(yīng)用聚類的概念到分類中. n但僅限于基于2-維規(guī)則的分類,如A B Classi 的格式所示n利用裝箱(Binning)方法將數(shù)據(jù)屬性值離散化,

31、因此ACRS的準確度與使用的離散化程度強烈相關(guān). 53內(nèi)容提要內(nèi)容提要 n引言nApriori 算法nFrequent-pattern tree 和FP-growth 算法n多維關(guān)聯(lián)規(guī)則挖掘n相關(guān)規(guī)則n基于約束的關(guān)聯(lián)規(guī)則挖掘n總結(jié)54相關(guān)規(guī)則(Correlation Rules)n“Beyond Market Baskets,” Brin et al.n假設(shè)執(zhí)行關(guān)聯(lián)規(guī)則挖掘tea = coffee20% support80% confidencebut 90% of the people buy coffee anyway!55相關(guān)規(guī)則n一種度量是計算相關(guān)性n若兩個隨機變量 A 和 B 是統(tǒng)計

32、獨立的n對tea 和 coffee:1)()()(BPAPBAP89.0)()()(cPtPctP56相關(guān)規(guī)則n利用 2 統(tǒng)計檢驗來測試獨立性n設(shè)n為購物籃的總數(shù)n設(shè)k為考慮的項的總數(shù)n設(shè) r 為一個包含項 (ij, ij)的規(guī)則n設(shè)O(r) 表示包含規(guī)則r的購物籃的數(shù)量 (即頻率)n對單個項ij,設(shè) Eij = O(ij) (反過來即為 n - Eij)nEr = n * Er1/n * * Erk / n57相關(guān)規(guī)則n2 統(tǒng)計量定義為nLook up for significance value in a statistical textbooknThere are k-1 degrees of freedomnIf test fails cannot reject independence, otherwise contigency table represents dependence.RrrErErO)(2258示例nBack to tea and coffeenEt = 25, Et=75, Ec=90, Ec=10nEtc=100 * 25/100 * 90 /100=22.5nO(tc) = 20nContrib. to 2 = (20 - 22.5)2 / 22.5 = 0.278nCalculate for the rest to get 2=2.204nN