關(guān)聯(lián)規(guī)則
關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘研究里的重要內(nèi)容儒恋，目的是為了找出不同東西之間的相關(guān)性弊予。下面來介紹關(guān)聯(lián)規(guī)則中一些重要的定義嚷硫。
下面借用一個(gè)引例來介紹關(guān)聯(lián)規(guī)則簿晓。
項(xiàng)集
D是一個(gè)事務(wù)數(shù)據(jù)庫，其中每一個(gè)事務(wù)T由一些項(xiàng)目構(gòu)成罗晕，并且都有一個(gè)唯一的標(biāo)識(shí)（TID）济欢。如上圖所示，每一個(gè)TID對(duì)應(yīng)一條事務(wù)Ti小渊，每一個(gè)事務(wù)Ti中的物品稱為項(xiàng)目法褥，項(xiàng)目的集合就稱為項(xiàng)目集，而含有K個(gè)項(xiàng)目的項(xiàng)目集稱為K-項(xiàng)目集酬屉。
支持度
項(xiàng)目集X的支持度是指在事務(wù)數(shù)據(jù)庫D中包含項(xiàng)目集X的事務(wù)占整個(gè)事務(wù)的比例半等，記為sup(X)，可以看作是項(xiàng)目集X在總事務(wù)中出現(xiàn)的頻率呐萨。一般定義為sup(X)=X出現(xiàn)的次數(shù)/事務(wù)總數(shù)T杀饵。
引例中X={bread, milk}出現(xiàn)在T1，T2垛吗，T5，T9和T10中烁登，所以支持度為0.5怯屉。
最小支持度
最小支持度是項(xiàng)集的最小支持閾值，記為min_sup饵沧，代表了用戶關(guān)心的關(guān)聯(lián)規(guī)則的最低重要性锨络。支持度不小于min_sup的稱為頻繁項(xiàng)目集，長度為K的頻繁集稱為K-頻繁集狼牺。如果設(shè)定sup_min為0.3羡儿，引例中{bread, milk}的支持度是0.5，所以是2-頻繁集是钥。
可信度
可信度是指在事務(wù)數(shù)據(jù)庫D中掠归，同時(shí)含項(xiàng)目集X和Y的事務(wù)與含項(xiàng)目集X的事務(wù)的比缅叠，即sup(XUY)/sup(X)，看作是項(xiàng)目集X出現(xiàn)虏冻，使項(xiàng)目集Y也出現(xiàn)肤粱，這一件事情在總事務(wù)中出現(xiàn)的頻率。
關(guān)聯(lián)規(guī)則
關(guān)聯(lián)規(guī)則可形式化為X?Y厨相，它的含義是XUY的支持度sup(XUY)大于用戶指定的最小支持度min_sup领曼，且可信度conf大于用戶指定的最小可信度min_conf。關(guān)聯(lián)規(guī)則挖掘就是在事務(wù)數(shù)據(jù)庫D中找出滿足用戶指定的最小支持度min_sup和最小可信度min_conf的所有關(guān)聯(lián)規(guī)則蛮穿。
Apriori關(guān)聯(lián)規(guī)則算法
Apriori算法是一種以概率為基礎(chǔ)的關(guān)聯(lián)規(guī)則算法庶骄，它是一種迭代算法，從少到多践磅，從簡單到復(fù)雜尋找極大頻繁集的算法单刁。
1.Apriori特性
如果一個(gè)擁有K個(gè)項(xiàng)目的項(xiàng)目集I不滿足最小支持度，根據(jù)定義音诈，項(xiàng)目集I不是一個(gè)頻繁集幻碱，如果往I中加入任意一個(gè)新的項(xiàng)目得到一個(gè)擁有K+1個(gè)項(xiàng)目的項(xiàng)目集I'，則I'必定也不是頻繁集细溅。
2.算法過程
- 制定最小支持度及最小置信度
- Apriori算法使用了候選項(xiàng)集的概念褥傍，首先掃描數(shù)據(jù)庫產(chǎn)生候選項(xiàng)目集，如果候選項(xiàng)目集的支持度不小于最小支持度喇聊，則該候選項(xiàng)目集為頻繁項(xiàng)目集
- 從數(shù)據(jù)庫中讀入所有事務(wù)數(shù)據(jù)恍风，得到出候選1項(xiàng)集C1及相應(yīng)的支持度數(shù)據(jù)，通過將每個(gè)1項(xiàng)集的支持度與最小支持度比較誓篱，得出頻繁項(xiàng)集合L1朋贬，然后將這些頻繁1項(xiàng)集兩兩進(jìn)行連接，產(chǎn)生候選2項(xiàng)集合C2窜骄。
- 然后再次掃描數(shù)據(jù)庫得到候選2項(xiàng)集合C2的支持度锦募，將2項(xiàng)集的支持度與最小支持度比較，確定頻繁2項(xiàng)集邻遏。類似地糠亩，利用這些頻繁2項(xiàng)集L2產(chǎn)生候選3項(xiàng)集和確定頻繁3項(xiàng)集，以此類推准验。
- 反復(fù)掃描數(shù)據(jù)庫赎线，與最小支持度比較，產(chǎn)生更高項(xiàng)的頻繁項(xiàng)集合糊饱，再結(jié)合產(chǎn)生下一級(jí)候選項(xiàng)集垂寥，直到不再產(chǎn)生出新的候選項(xiàng)集為止。
