【正文】 設(shè)定為 70％，則只有以下三個關(guān)聯(lián)規(guī)則輸出：I1∧I5→I2 confidence=2/2=100%I2∧I5→I1 confidence=2/2=100%I5→I1∧I2 confidence=2/7=100%2023/2/27 星期六 24Data Mining: Concepts and Techniques例子〖例〗以下表所示的事務集為例，其中 C[i]是候選集， L[i]是大數(shù)據(jù)項集。關(guān)聯(lián)規(guī)則產(chǎn)生的步驟：第 1步：對于每一個頻繁項集 I， 產(chǎn)生 I的所有非空子集。2023/2/27 星期六 18Data Mining: Concepts and TechniquesImportant Details of Apriorin How to generate candidates?n Step 1: selfjoining Lkn Step 2: pruningn How to count supports of candidates?n Example of Candidategenerationn L3={abc, abd, acd, ace, bcd}n Selfjoining: L3*L3n abcd from abc and abdn acde from acd and acen Pruning:n acde is removed because ade is not in L3n C4={abcd}2023/2/27 星期六 19Data Mining: Concepts and TechniquesHow to Generate Candidates?n Suppose the items in Lk1 are listed in an ordern Step 1: selfjoining Lk1 insert into Ckselect , , …, k1, from Lk1 p, Lk1 qwhere =, …, k2=, n Step 2: pruningforall itemsets c in Ck doforall (k1)subsets s of c doif (s is not in Lk1) then delete c from Ck2023/2/27 星期六 20Data Mining: Concepts and TechniquesHow to Count Supports of Candidates?n Why counting supports of candidates a problem?n The total number of candidates can be very hugen One transaction may contain many candidatesn Method:n Candidate itemsets are stored in a hashtreen Leaf node of hashtree contains a list of itemsets and countsn Interior node contains a hash tablen Subset function: finds all the candidates contained in a transaction2023/2/27 星期六 21Data Mining: Concepts and TechniquesExample: Counting Supports of Candidates1,4,72,5,83,6,9Subset function2 3 45 6 71 4 5 1 3 61 2 44 5 7 1 2 54 5 8 1 5 93 4 5 3 5 63 5 76 8 93 6 73 6 8Transaction: 1 2 3 5 61 + 2 3 5 61 2 + 3 5 61 3 + 5 62023/2/27 星期六 22Data Mining: Concepts and Techniques由頻繁項集而產(chǎn)生關(guān)聯(lián)規(guī)則 一旦數(shù)據(jù)庫 D中的事務找出的頻繁項集，由它們產(chǎn)生強關(guān)聯(lián)規(guī)則是直截了當?shù)摹?k++) do begin Ck+1 = candidates generated from Lk。for (k = 1。對給定的 L， 如果其非空子集 A?L， sup(L)為 L的支持度，sup(A)為 A的支持度，則產(chǎn)生形式為 A?LA的規(guī)則?？梢詮?1到 k遞歸查找 k頻繁項集。 如果項集滿足最小支持度，則稱該項集為頻繁項集（ frequent itemset ）。包含項集的事務數(shù)稱為項集的出現(xiàn)頻率，簡稱為項集的頻率或支持度計數(shù)。n 多維關(guān)聯(lián)規(guī)則：處理多個維中屬性之間的關(guān)系，即在多維的關(guān)聯(lián)規(guī)則中，要處理的數(shù)據(jù)將會涉及多個維。 2023/2/27 星期六 10Data Mining: Concepts and Techniques關(guān)聯(lián)規(guī)則挖掘的分類 — 基于數(shù)據(jù)的維數(shù) 基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù) ,關(guān)聯(lián)規(guī)則可以分為單維的和多維的 n 單維關(guān)聯(lián)規(guī)則：處理單個維中屬性間的關(guān)系，即在單維的關(guān)聯(lián)規(guī)則中，只涉及到數(shù)據(jù)的一個維。n多層的關(guān)聯(lián)規(guī)則：變量涉及不同抽象層次的項或?qū)傩浴?023/2/27 星期六 9Data Mining: Concepts and Techniques關(guān)聯(lián)規(guī)則挖掘的分類 — 基于 抽象層次 基于規(guī)則中數(shù)據(jù)的抽象層次 ,可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則：n單層的關(guān)聯(lián)規(guī)則：所有的變量都不涉及不同抽象層次的項或?qū)傩?。例如，以下是量化型關(guān)聯(lián)規(guī)則的一個例子（其中 X為表示顧客的變量，量化屬性 age 和 ine已經(jīng)離散化）： age(X,“30…39”)∧ine(“42K…48K”) buys(X,“high_resolution_TV”) 量化型關(guān)聯(lián)規(guī)則中也可以包含多種變量。例如，由購物籃分析得出的關(guān)聯(lián)規(guī)則。 關(guān)聯(lián)規(guī)則挖掘：給定一組 Item和記錄集合，挖掘出 Item間的相關(guān)性，使其置信度和支持度分別大于用戶給定的最小置信度和、最小支持度。 ― 核心 根據(jù)頻繁項集和最小置信度產(chǎn)生關(guān)聯(lián)規(guī)則。 強規(guī)則 X?Y對應的項集（ X∪Y ） 必定是頻繁集。通過設(shè)置最小支持度和最小置信度可以了解某些數(shù)據(jù)之間的關(guān)聯(lián)程度。 2023/2/27 星期六 7Data Mining: Concepts and Techniques關(guān)聯(lián)規(guī)則挖掘167。167。2023/2/27 星期六 6Data Mining: Concepts and Techniques關(guān)聯(lián)規(guī)則挖掘數(shù)據(jù)挖掘主要就是對強規(guī)則的挖掘。即： support(X?Y)＝ (包含 X和 Y的事務數(shù) / 事務總數(shù) )100 ％ confidence(X?Y)＝ 包含 X和 Y的事務數(shù) / 包含 X的事務數(shù))100 ％〖定義 8－ 3〗 置信度和支持度均大于給定閾值（即最小置信度閾值和最小支持度閾值）。2023/2/27 星期六 5Data Mining: Concepts and Techniques置信度和支持度〖定義 8－ 2〗 關(guān)聯(lián)規(guī)則 X?Y對事物集 D的支持度（ support，） 定義為 D中包含有事務 X和 Y的百分比。事務 T是 I上的一個子集，集合 T?I， 每個事務用唯一的標志 TID來標識。項目之間的相關(guān)性用關(guān)聯(lián)規(guī)則來描述，關(guān)聯(lián)規(guī)則反映了一組數(shù)據(jù)項之間的密切程度或關(guān)系。該規(guī)則表示：在所分析的全部事務中，有 2％的事務同時購買計算機和財務管理軟件；在購買計算機的顧客中 60％也購買財務管理軟件。這些模式可用關(guān)聯(lián)規(guī)則描述。第 6章 : 關(guān)聯(lián)規(guī)則挖掘n Association rule miningn Algorithms for scalable mining of (singledimensional Boolean) association rules in transactional databasesn Mining various kinds of association/correlation rules n Constraintbased association miningn Sequential pattern miningn Applications/extensions of frequent pattern miningn Summary2023/2/27 星期六 1Data Mining: Concepts and TechniquesWhat Is Association Mining?n Association rule mining:n Finding frequent patterns, associations, correlations, or causal structures among sets of items or objects in transaction databases, relational databases, and other information repositories.n Frequent pattern: pattern (set of items, sequence, etc.) that occurs frequently in a database [AIS93]n Motivation: finding regularities in datan What products were often purchased together? — Beer and diapers?!n What are the subsequent purchases after buying a PC?n What kinds of DNA are sensitive to this new drug?n Can we automatically classify web documents?2023/2/27 星期六 2Data Mining: Concepts and Techniques關(guān)聯(lián)規(guī)則挖掘的基本概念 購物籃分析－引發(fā)關(guān)聯(lián)規(guī)則挖掘的例子問題： “ 什么商品組或集合顧客多半會在一次購物中同時購買？ ”購物籃分析：設(shè)全域為商店出售的商品的集合（即項目全集），一次購物購買（即事務）的商品為項目全集的子集，若每種商品用一個布爾變量表示該商品的有無，則每個購物籃可用一個布爾向量表示。通過對布爾向量的分析，得到反映商品頻繁關(guān)聯(lián)或同時購買的購買模式?！祭劫徺I計算機與購買財務管理軟件的關(guān)聯(lián)規(guī)則可表示為：puter financial_management_softwar [support=2%,confidence=60%]support為支持度， confidence為置信度。2023/2/27 星期六 3Data Mining: Concepts and TechniquesWhy Is Frequent Pattern or Assoiciation Mining an Essential Task in Data Mining?n Foundation for many essential data mining tasksn Association, correlation, causalityn Sequential patterns, temporal or cyclic association, partial periodicity, spatial and multimedia associationn Associative classification, cluster analysis, iceberg cube, fascicles (semantic data pression)n Broad applicationsn Basket data analysis, crossmarketing, catalog design, sale campaign analysisn Web log (click stream) analysis, DNA sequence analysis, etc.2023/2/27 星期六 4Data Mining: Concepts and Techniques關(guān)聯(lián)規(guī)則 關(guān)聯(lián)（ Associations） 分析的目的是為了挖掘隱藏在數(shù)據(jù)間的相互關(guān)系，即對于給定的一組項目和一個記錄集，通過對記錄集的分析，得出項目集中的項目之間的相關(guān)性?！级x 8－ 1〗 令 I={i1， i2， …,in} 是項目集， D是全體事務的集合。關(guān)聯(lián)規(guī)則是形如 X?Y的蘊含式，其中X?I， Y?I且 X?Y=?， X稱為規(guī)則的條件， Y稱為規(guī)則的結(jié)果。關(guān)聯(lián)規(guī)則 X?Y對事務集合 D的置信度（confidence） 定義為 D中包含有 X的事務數(shù)與同時包含 Y的百分比。即：support(X?Y) ＝ min_supconfidence(X?Y) ＝ min_conf 的關(guān)聯(lián)規(guī)則稱為強規(guī)則；否則稱為弱規(guī)則。通過設(shè)置最小支持度和最小置信度可以了解某些數(shù)據(jù)之間的關(guān)聯(lián)程度。關(guān)聯(lián)規(guī)則挖掘：給定一組 Item和記錄集合，挖掘出