數(shù)據(jù)挖掘基于約束的挖掘(已修改)
2025-09-11 09:03 本頁(yè)面
【正文】 第六章 在大型數(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。amp。=1999 amp。amp。= (5)group by C, (6)having sum(=100)amp。amp。min()=500 (7)with support threshold=1% (8)with confidence threshold=50% Lives(C,_,”Pudong”)^Sales(C,”Census_CD”,_)^Sales(C,”MS/Office”,_)=Sales(C,”MS/SQLSever”,_) [%,65%] 約束的分類 ? 單調(diào)性約束 (monotone constraint) ? 反單調(diào)性約束 (antimonotone constraint) ? 可轉(zhuǎn)變的約束 (convertibale constraint) ? 簡(jiǎn)潔性約束 (succinct constraint) 約束的有關(guān)概念 ? 項(xiàng)目集： I={i1,i2,…… ,im}, ? 交易： T=tid,It ? 模式 S是項(xiàng)目集的子集， S={ij1,ij2,… ,ijk} ? 模式 S包含與 T,T=tid,It,iff S=It。 S’是 S的子模式 (subpattern)且 S 是 S’的超模式 (superpattern)， if 有 S’=S. 約束的有關(guān)概念（續(xù)） ? 定義約束 : C是作用于項(xiàng)目集 I的冪集(powerset)上的謂詞 ,C(S)=True/False。 ? 滿意模式集 (satisfying pattern set) SATc(I)是指那些完全滿足約束 C的項(xiàng)目集的全體 ? 將約束條件用于頻繁集的查詢無(wú)非是找出那些滿足 C的頻繁集 單調(diào)和反單調(diào)的規(guī)則約束 ? 規(guī)則 Ca 是 反單調(diào)的 (antimonotone) iff 對(duì)于任給的不滿足 Ca的項(xiàng)集 (模式 ) S, 不存在 S的超集能夠滿足 Ca : Ca : min(S)=v ， v是 S的一個(gè)項(xiàng)集 ? 約束 Cm 是 單調(diào)的 Cm的項(xiàng)集(模式 ) S, 每一個(gè) S的超集都能夠滿足 Cm : Cm : min(S)=v, v是 S的一個(gè)項(xiàng)集 單調(diào) /反單調(diào)性約束描述 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) yes yes no partly yes no partly no yes partly no yes partly no yes partly convertible (no) no no yes partly no yes partly yes no partly yes no partly yes no partly convertible (yes) 反單調(diào) 單調(diào) 約束規(guī)則 可轉(zhuǎn)變的約束 1 ? 反單調(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)變性約束的例子 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),
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1