【正文】 的 1. C(S)既不是單調(diào)性約束，也不是反單調(diào)性約束； R,使得經(jīng) R排序后的 I具有如下性質(zhì)： 任給 S’∈ {suffix_S}, if C(S)=C(S’) 則 C(S)是反單調(diào)可轉(zhuǎn)變的 可轉(zhuǎn)變性約束的例子 1: Avg(S) ? V ? 令 I為一組以升序排列數(shù)值的項(xiàng)目集 ? . I={1， 3， 4， 6， 8， 9, }， R意指升續(xù) ? Avg(S) = v 是反單調(diào)可轉(zhuǎn)變的 ? 如果 S ’ 是 S的一個(gè)后綴 , 那么 avg(S’) = avg(S) ? {6,8,9} is a suffix of {3,4,6,8,9} ? avg({6,8,9})=23/3 ? avg({3,4,6,8,9})=6 ? 如果 S滿足約束 avg(S) ?v, 則 S’也滿足 可轉(zhuǎn)變的約束 2 ? 單調(diào)可轉(zhuǎn)變的 1. C(S)既不是單調(diào)性約束，也不是反單調(diào)性約束； R,使得經(jīng) R排序后的 I具有如下性質(zhì)： 任給 S’∈ {suffix_S}, if C(S’)=C(S) 則 C(S)是單調(diào)可轉(zhuǎn)變的 可轉(zhuǎn)變性約束的例子 2 Avg(S) ? V ? 令 I為一組以降序排列數(shù)值的項(xiàng)目集 ? . I={9, 8, 6, 4, 3, 1}， R意指降續(xù) ? Avg(S) ? v 是單調(diào)可轉(zhuǎn)變的 ? 如果 S ’ 是 S的一個(gè)后綴 , 那么 avg(S) ? avg(S’) ? {8, 4, 3} is a suffix of {9, 8, 4, 3} ? avg({9, 8, 4, 3})=6 ? avg({8, 4, 3})=5 ? 如果 S’滿足約束 avg(S’) ?v, 則 S也滿足 ? {8, 4, 3} satisfies constraint avg(S) ? 4, so does {9, 8, 4, 3} 簡(jiǎn)潔性約束 ? 一個(gè)項(xiàng)目子集 Is 是一個(gè) 簡(jiǎn)潔集 (succinct set), 如果對(duì)于某些選擇性謂詞 p,該項(xiàng)目子集能夠表示為 ?p(I) ，此處， ?是一個(gè)選擇符 ? SP?2I 是一個(gè) 強(qiáng)簡(jiǎn)潔集 ( succinct power set),如果有一個(gè)數(shù)目不變的簡(jiǎn)潔集 I1, …, Ik ?I, SP 能夠用 I1, …, Ik 的并、差運(yùn)算表示出來(lái) be expressed in terms of the strict power sets of I1, …, Ik using union and minus ? 約束 Cs 是 簡(jiǎn)潔的 假如 SATCs(I)是一個(gè)強(qiáng)簡(jiǎn)潔集 簡(jiǎn)潔性約束的舉例 約束規(guī)則 v ? S S ?V S ? V S ? V min(S) ? v min(S) ? v min(S) ? v max(S) ? v max(S) ? v max(S) ? v count(S) ? v count(S) ? v count(S) ? v sum(S) ? v sum(S) ? v sum(S) ? v avg(S) ? v, ? ? { ?, ?, ? } (frequent constraint) 簡(jiǎn)潔性 yes yes yes yes yes yes yes yes yes yes weakly weakly weakly no no no no (no) 幾種約束之間的關(guān)系 Succinctness Antimonotonicity Monotonicity Convertible constraints Inconvertible constraints 頻繁數(shù)據(jù)集應(yīng)用舉例 ? 交易數(shù)據(jù)庫(kù) TDB如下所示， 支持度 為 3 頻繁項(xiàng)目按照 降續(xù) 排列 ： a:5。第六章 在大型數(shù)據(jù)庫(kù)中 挖掘關(guān)聯(lián)規(guī)則 報(bào)告人：張榮祖 2020/11/28 基于約束的挖掘 ? 使用約束的必要性 ? 在數(shù)據(jù)挖掘中常使用的幾種約束： ? 知識(shí)類型約束： 指定要挖掘的知識(shí)類型 如關(guān)聯(lián)規(guī)則 ? 數(shù)據(jù)約束： 指定與任務(wù)相關(guān)的數(shù)據(jù)集 ? Find product pairs sold together in Vancouver in Dec.’98. ? 維 /層次約束 :指定所用的維或概念結(jié)構(gòu)中的層 ? in relevance to region, price, brand, customer category. ? 規(guī)則約束： 指定 要挖掘的規(guī)則形式 (如規(guī)則模板 ) ? 單價(jià) (price $10)的交易項(xiàng)目可能引發(fā)購(gòu)買總額 (sum $200). ? 興趣度約束： 指定規(guī)則興趣度閾值或統(tǒng)計(jì)度量 ? 如 (min_support ? 3%, min_confidence ? 60%). ? 假定 AllElectronics的一個(gè)銷售多維數(shù)據(jù)庫(kù)有如下關(guān)系： ? Sales(customer_name,item_name,transaction_id) ? Lives(customer_name,region,city) ? Items(item_name,category， price) ? Transaction(transaction_id,day,month,year) (1) mine associations as (2)lives(C,_,”Pudong”)^sales(C,{I},{S})=sales(C,{J}{T}) (3) from sales (4)where =1999 amp。 S’是 S的子模式 (subpattern)且 S 是 S’的超模式 (superpattern)， if 有 S’=S. 約束的有關(guān)概念（續(xù)） ? 定義約束 : C是作用于項(xiàng)目集 I的冪集(powerset)上的謂詞 ,C(S)=True/False。 TDB|c。 Lk1 !=?。在小的抽樣集上找到局部頻繁項(xiàng)集，然后在全部數(shù)據(jù)集找頻繁項(xiàng)集。 ? – 底層項(xiàng)不會(huì)成為頻繁集，如果支持度 ? 太高 ? 丟失底層關(guān)聯(lián)規(guī)則 ? 太低 ? 生成太多的高層關(guān)聯(lián)規(guī)則 2 支持度遞減 : 隨著層次的降低支持度遞減 多層關(guān)聯(lián)規(guī)則 : 支持度不變 vs. 支持度遞減 3層次交叉單項(xiàng)過(guò)濾： 4層次交叉 K項(xiàng)過(guò)濾： ? 4種搜索策略： ? 層與層獨(dú)立 ? 用 k項(xiàng)集跨層過(guò)濾 ? 用項(xiàng)跨層過(guò)濾 ? 用項(xiàng)進(jìn)行可控跨層過(guò)濾 支持度不變 支持度不變多層挖掘 牛奶 [support = 10%] 酸奶 [support = 6%] 脫脂奶 [support = 4%] 層 1 min_sup = 5% 層 2 min_sup = 5% 支持度遞減 支持度遞減多層挖掘 酸奶 [support = 6%] 脫脂奶 [support = 4%] 層 1 min_sup = 5% 層 2 min_sup = 3% 牛奶 [support = 10%] 多層關(guān)聯(lián)：冗余過(guò)濾 ? 由于“祖先”關(guān)系的原因，有些規(guī)則可能是多余的。am