關(guān)聯(lián)分析(數(shù)據(jù)庫)

時間：2022-12-23 04:30:01 | 來源：信息時代

時間：2022-12-23 04:30:01 來源：信息時代

    關(guān)聯(lián)分析 : 尋找數(shù)據(jù)項之間感興趣的關(guān)聯(lián)關(guān)系,用關(guān)聯(lián)規(guī)則的形式描述。
項(item): 元素i_m(m=1,2,…,p)稱為項,如購買的物品“籃球”,“籃球服”等。
全項集(itemsets): 所有項的非空有限集合,記為∑,∑={i₁,i₂,…,i_m,…,i_p}。
項集(itemset): 全項集的子集,記為I,I={i₁,i₂, …,i_j}(j<=p),I∑。
項集長度(size): 項集中項的數(shù)目。一個長度為k的項集稱為k-項集,如項集{籃球,籃球服}的長度為2,是一個2-項集。
交易(transaction): 形如(TID,I)的一條數(shù)據(jù)記錄T_k(k=1,2,…,n)稱為一個交易,其中,TID為交易標(biāo)識,I為項集。設(shè)X也是一個項集,如果XI, 那么稱交易T_k包含項集X, 或X被T_k包含,記為XT_k·I。
交易數(shù)據(jù)集(transaction data set):一系列交易組成的集合稱為交易數(shù)據(jù)集,記為D,D={T₁,T₂,…,T_k,…,T_n},其中,T_k(k=1,2,…,n)為一個交易。
關(guān)聯(lián)規(guī)則(association rule): 是形如X⇒Y的蘊涵式,X,Y為項集,X∑,Y∑,并且XY=Φ, X稱為輸入或左部,Y稱為輸出或右部。
關(guān)聯(lián)規(guī)則用興趣度度量評估。
興趣度度量(interest measure):幫助用戶評估得到的關(guān)聯(lián)規(guī)則。與關(guān)聯(lián)規(guī)則評估相關(guān)的興趣度包括簡潔性、正確性、實用性、新穎性。
簡潔性度量是衡量一個規(guī)則結(jié)構(gòu)的復(fù)雜程度,復(fù)雜結(jié)構(gòu)的規(guī)則難以解釋與理解,造成其興趣度降低; 正確性度量用以判斷規(guī)則令人信服的程度有多高,在關(guān)聯(lián)規(guī)則中用置信度表示; 實用性度量用以判斷該規(guī)則再次出現(xiàn)的可能性有多大,在關(guān)聯(lián)規(guī)則中用支持度表示; 新穎性度量判斷規(guī)則是否已被導(dǎo)出的規(guī)則集中的另一規(guī)則所蘊涵,用以去除冗余規(guī)則。
支持度(support):關(guān)聯(lián)規(guī)則X⇒Y在交易數(shù)據(jù)集D中的支持度是指交易數(shù)據(jù)集中包含X和Y的交易數(shù)與所有交易數(shù)之比,表示在所有交易中同時含有X與Y的概率(P(X∪Y),其中P表示概率),記為support(X⇒Y)。 計算方法為: support(X⇒Y)=P(X∪Y)=|{T:X∪YT.I,T∈D}|/|D|×100%(其中|D|是數(shù)據(jù)集D中的所有交易數(shù))。
支持度表示關(guān)聯(lián)規(guī)則出現(xiàn)的概率是多少,是對關(guān)聯(lián)規(guī)則重要性(或適用范圍)的衡量,反映了這條規(guī)則在所有交易中的普遍程度。
置信度(confidence): 關(guān)聯(lián)規(guī)則X⇒Y在交易數(shù)據(jù)集D中的置信度是指交易數(shù)據(jù)集中包含X和Y的交易數(shù)與包含X的交易數(shù)之比,表示在所有出現(xiàn)了X的交易中出現(xiàn)Y的概率(P(Y|X),其中P表示概率),記為confidence(X⇒Y)。計算方法為:confidence(X⇒Y)=P(Y|X)=|{T:X∪YT.I,T∈D}|/|{T:X T.I,T∈D}|×100%。
置信度表示關(guān)聯(lián)規(guī)則正確的概率是多少。它是對關(guān)聯(lián)規(guī)則準(zhǔn)確度的衡量,反映了關(guān)聯(lián)規(guī)則前提成立的條件下結(jié)果成立的概率。
為了發(fā)現(xiàn)符合特定應(yīng)用和用戶感興趣的關(guān)聯(lián)規(guī)則,需要給每個度量指定一個可以由用戶控制的閾值。常用的是最小支持度閾值(min_sup)和最小置信度閾值(min_conf)。前者是用戶規(guī)定的關(guān)聯(lián)規(guī)則必須滿足的最小支持度,它反映了關(guān)聯(lián)規(guī)則的最低普遍程度;后者是用戶規(guī)定的關(guān)聯(lián)規(guī)則必須滿足的最小置信度,它反映了關(guān)聯(lián)規(guī)則的最低可靠度。最小支持度閾值、最小置信度閾值一般由用戶和領(lǐng)域?qū)＜以O(shè)定。
頻繁項集(frequent itemset): 項集出現(xiàn)的頻率表示包含項集的交易數(shù),如果項集的出現(xiàn)頻率大于或等于最小支持度閾值與交易數(shù)據(jù)集D中交易總數(shù)的乘積,即項集滿足最小支持度閾值要求,則該項集是頻繁項集; 其余稱為非頻繁項集。
強(qiáng)關(guān)聯(lián)規(guī)則: 強(qiáng)關(guān)聯(lián)規(guī)則是指同時滿足用戶定義的最小支持度閾值和最小置信度閾值的關(guān)聯(lián)規(guī)則。相反,不滿足用戶定義的最小支持度閾值和最小置信度閾值的規(guī)則,是弱關(guān)聯(lián)規(guī)則。
關(guān)聯(lián)規(guī)則挖掘是在交易數(shù)據(jù)集中發(fā)現(xiàn)超過用戶指定的最小支持度閾值和最小置信度閾值的強(qiáng)關(guān)聯(lián)規(guī)則。其挖掘過程一般分為兩個步驟:
第一步:所有頻繁項集的生成(這個步驟需借助最小支持度閾值)。
第二步:由頻繁項集到強(qiáng)關(guān)聯(lián)規(guī)則的生成(這個步驟需要借助最小置信度閾值)。
典型的關(guān)聯(lián)規(guī)則挖掘算法主要有:基于Apriori性質(zhì)的生成候選項集的Apriori算法和不生成候選項集的模式增長的FP-Growth算法等。
根據(jù)不同的標(biāo)準(zhǔn)可將關(guān)聯(lián)規(guī)則進(jìn)行以下分類:
(1)基于規(guī)則中處理的數(shù)據(jù)的類型,分為布爾關(guān)聯(lián)規(guī)則和量化關(guān)聯(lián)規(guī)則。布爾關(guān)聯(lián)規(guī)則描述離散(或類別)屬性之間關(guān)系的關(guān)聯(lián)規(guī)則; 量化關(guān)聯(lián)規(guī)則描述量化(或數(shù)值型)屬性之間的關(guān)系的關(guān)聯(lián)規(guī)則。
(2)基于規(guī)則中數(shù)據(jù)的抽象層次,分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。單層關(guān)聯(lián)規(guī)則不涉及不同抽象層的項(或?qū)傩?的規(guī)則;多層關(guān)聯(lián)規(guī)則涉及不同抽象層的項(或?qū)傩?的規(guī)則。
(3)基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù),分為單維關(guān)聯(lián)規(guī)則和多維關(guān)聯(lián)規(guī)則。單維關(guān)聯(lián)規(guī)則處理同一個屬性(或維)內(nèi)的聯(lián)系;多維關(guān)聯(lián)規(guī)則處理多個屬性(或維)之間的聯(lián)系。