數(shù)據(jù)分析與數(shù)據(jù)挖掘課件 【ch08】關(guān)聯(lián)規(guī)則與點(diǎn)對(duì)相關(guān)性

第八章關(guān)聯(lián)規(guī)則與點(diǎn)對(duì)相關(guān)性數(shù)據(jù)分析與數(shù)據(jù)挖掘01主成分分析最初的頻繁模式挖掘是從購(gòu)物籃分析開始的。購(gòu)物籃是用戶的一次購(gòu)買所包含的商品的集合。用戶的一次購(gòu)買行為稱為一個(gè)“事務(wù)”,購(gòu)買的各商品稱為“項(xiàng)”。支持度(Support)是指項(xiàng)集在事務(wù)數(shù)據(jù)庫(kù)中出現(xiàn)的頻率。頻繁模式的基本概念關(guān)聯(lián)規(guī)則中有兩個(gè)重要度量指標(biāo)：支持度(Support)和置信度(Confidence)。X→Y是一個(gè)關(guān)聯(lián)規(guī)則候選，在事務(wù)數(shù)據(jù)庫(kù)D中，如果support%的事務(wù)包含XUY,則X=Y的支持度為support%。關(guān)聯(lián)規(guī)則的基本概念極大頻繁模式與閉頻繁模式性質(zhì)1:頻繁項(xiàng)集的子集必為頻繁項(xiàng)集；性質(zhì)2:非頻繁項(xiàng)集的超集一定是非頻繁的。02頻繁模式挖掘Apriori算法Agrawal在闡述關(guān)聯(lián)規(guī)則模型后又提出經(jīng)典的Apriori頻繁模式挖掘算法。挖掘頻繁模式后可直接計(jì)算出關(guān)聯(lián)規(guī)則的支持度和置信度，通過設(shè)置最小支持度閾值和置信度閾值可實(shí)現(xiàn)關(guān)聯(lián)規(guī)則挖掘。垂直數(shù)據(jù)格式(Verticaldataformat)是通過將事務(wù)數(shù)據(jù)庫(kù)的格式轉(zhuǎn)換為按照項(xiàng)進(jìn)行索引，再通過集合交集運(yùn)算來計(jì)算頻繁模式的。垂直數(shù)據(jù)格式基于前述頻繁模式，可以計(jì)算關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則常用支持度(Support)和置信度(Confidence)作為規(guī)則有用性度量，此外，提升度(Lift)也常被使用?；陬l繁模式計(jì)算關(guān)聯(lián)規(guī)則03頻繁模式樹頻繁模式樹(FrequentPatternTree,FP-Tree)又稱頻繁模式增長(zhǎng)樹(Frequentpatterngrowthtree)也是一種頻繁模式挖掘算法。它通過對(duì)事務(wù)數(shù)據(jù)庫(kù)壓縮表示，減少了事務(wù)數(shù)據(jù)庫(kù)的掃描次數(shù)。頻繁模式樹的構(gòu)建頻繁模式樹的主要工作過程為：①生成頭表(Headlist)。②事務(wù)數(shù)據(jù)庫(kù)中事務(wù)項(xiàng)集重排。③構(gòu)建頻繁模式樹。④提取條件模式基。⑤生成頻繁模式。因子分析過程下面結(jié)合表8.4的示例說明如何構(gòu)建頻繁模式樹，進(jìn)而挖掘頻繁模式。在圖8.6中，將sub-S-n視作新的事務(wù)數(shù)據(jù)庫(kù)，按照8.3.1節(jié)中的步驟一至步驟三，構(gòu)建頭表，并構(gòu)建頻繁模式樹T-d。頻繁模式樹的遞歸過程04點(diǎn)對(duì)相似度的典型度量點(diǎn)對(duì)關(guān)系常見度量

如果將容量為N的樣本集中包括X的樣本視作一個(gè)集合，將包括Y的樣本視作另一個(gè)集合，如圖8.7(a)所示。許多學(xué)者構(gòu)建了較多相關(guān)性度量指標(biāo)，如表8.6所示。點(diǎn)對(duì)關(guān)系常見度量許多學(xué)者構(gòu)建了較多相關(guān)性度量指標(biāo)，如表8.6所示。點(diǎn)對(duì)關(guān)系常見度量

置信度是有方向度量，confidence(X,Y)可能與confidence(Y,X)值相同也可能不同。表8.6中，有些指標(biāo)與置信度存在關(guān)系，舉以下三個(gè)例子：點(diǎn)對(duì)相關(guān)性度量的幾種特性05信息熵及其應(yīng)用與點(diǎn)對(duì)相關(guān)性度量信息熵

把一個(gè)隨機(jī)事件x的自信息量定義為式(8.7)。在信息論中，通常將對(duì)數(shù)的底設(shè)置為2,此時(shí)自信息量的單位為比特(Bit,二進(jìn)制數(shù)的1位),有時(shí)也設(shè)置為自然常數(shù)e,此時(shí)自信息量的單位為奈特(Nat)。圖8.9(b)展示了結(jié)果有兩種狀態(tài)時(shí)，信息熵值與一個(gè)狀態(tài)概率p?的變化曲線。對(duì)于隨機(jī)事件X存在3種或更多種狀態(tài)時(shí)，信息熵仍使用式(8.8)表示。信息熵聯(lián)合熵與互信息聯(lián)合熵與互信息將信息增益(InformationGain,IG)定義為待分類集合的信息熵和選定某個(gè)特征的條件熵之差，如式(8.21)所示。信息增益、相對(duì)熵和交叉熵互信息I(X;Y)可用于相似度的度量。在關(guān)聯(lián)規(guī)則或文本挖掘領(lǐng)域中，衡量?jī)蓚€(gè)項(xiàng)或兩個(gè)詞的相關(guān)性，可以使用點(diǎn)對(duì)互信息，簡(jiǎn)稱點(diǎn)互信息(PointwiseMutualInformation,PMI),如式(8.27)所示?；バ畔ⅰ⒔徊骒赜糜谙嚓P(guān)性06本章小結(jié)本章小結(jié)本章講述了頻繁模式、關(guān)聯(lián)規(guī)則、點(diǎn)對(duì)相關(guān)性度量和信息熵方面的知識(shí)。頻繁模式是事務(wù)數(shù)據(jù)庫(kù)中頻繁出現(xiàn)的項(xiàng)集、子序列或子結(jié)構(gòu)。關(guān)聯(lián)規(guī)則是獲得形如X→Y的規(guī)則，主要指標(biāo)包括支持