正文之前

當初畢設(shè)的時候準備用這個算法來著欣孤，不過后來為了給自己減少工作量（俗稱偷懶）朱巨，就沒搞了，沒想到這兩天看一篇論文看到了這個番官，重新?lián)炱饋韺W(xué)一下。對于我這種算法底子不是很好的來說钢属。徘熔。只能代碼實現(xiàn)來感受下了。淆党。

正文

基本概念

關(guān)聯(lián)分析是一種在大規(guī)模數(shù)據(jù)集中尋找有趣關(guān)系的非監(jiān)督學(xué)習(xí)算法酷师。這些關(guān)系可以有兩種形式：頻繁項集或者關(guān)聯(lián)規(guī)則。頻繁項集（frequent item sets)是經(jīng)常出現(xiàn)在一塊的物品的集合染乌，關(guān)聯(lián)規(guī)則(association rules)暗示兩種物品之間可能存在很強的關(guān)系山孔。

下圖是一個乒乓球店的交易記錄，〇表示顧客購買了商品荷憋。其中{底板,膠皮,澆水}就是一個頻繁項集台颠；從中可以找到底板->膠皮這樣的關(guān)聯(lián)規(guī)則：

然后是兩個至關(guān)重要的參數(shù)的表示法：

支持度

怎樣有效定義頻繁和關(guān)聯(lián)？其中最重要的兩個概念是支持度和置信度勒庄。

支持度(support)從字面上理解就是支持的程度串前，一個項集的支持度(support)被定義為數(shù)據(jù)集中包含該項集的記錄所占的比例。上圖中{底板}的支持度=(5/6) * 100%实蔽。

這個概念其實經(jīng)常在現(xiàn)實生活中出現(xiàn)荡碾，翻譯成支持率似乎更好理解，典型的例子就是投票盐须，比如英國脫歐的支持率為51.89%玩荠。

用數(shù)學(xué)去解釋就是，設(shè)W 中有s％的事務(wù)同時支持物品集A和B贼邓，s％稱為{A阶冈，B}的支持度，即:

support({A,B}) = num(A∪B) / W = P(A∩B)

num(A∪B)表示含有物品集{A,B}的事務(wù)集的個數(shù)塑径，不是數(shù)學(xué)中的并集女坑。

置信度

置信度(confidence)揭示了A出現(xiàn)時B是否一定出現(xiàn)，如果出現(xiàn)统舀，則出現(xiàn)的概率是多大匆骗。如果A->B的置信度是100%劳景，則說明A出現(xiàn)時B一定會出現(xiàn)（返回來不一定）。上圖中底板共出現(xiàn)5次碉就，其中4次同時購買了膠皮盟广，底板->膠皮的置信度是80%。

用公式表示是瓮钥，物品A->B的置信度=物品{A,B}的支持度 / 物品{A}的支持度：

Confidence(A->B) = support({A,B}) / support({A}) = P(B|A)

這是Apriori算法的關(guān)鍵數(shù)學(xué)模型筋量。下面就是關(guān)鍵的Java實現(xiàn)，有時候我覺得看代碼真的比算法更加直觀些碉熄。桨武。。不過锈津，當我打開了算法流程圖的大門呀酸。

Apriori算法過程

發(fā)現(xiàn)頻繁項集的過程如上圖所示：

1. 由數(shù)據(jù)集生成候選項集C1（1表示每個候選項僅有一個數(shù)據(jù)項）；再由C1通過支持度過濾琼梆，生成頻繁項集L1（1表示每個頻繁項僅有一個數(shù)據(jù)項）漫玄。
2. 將L1的數(shù)據(jù)項兩兩拼接成C2孝鹊。
3. 從候選項集C2開始方篮，通過支持度過濾生成L2桩引。L2根據(jù)Apriori原理拼接成候選項集C3练般；C3通過支持度過濾生成L3……直到Lk中僅有一個或沒有數(shù)據(jù)項為止诬留。

下面是一個超市的交易記錄：

Apriori算法發(fā)現(xiàn)頻繁項集的過程如下：

或者這是我抄代碼的博客的圖尤筐，也挺好看的：

還有一段偽代碼奉上：

算法：Apriori
輸入：D - 事務(wù)數(shù)據(jù)庫矾端；min_sup - 最小支持度計數(shù)閾值
輸出：L - D中的頻繁項集
方法：
     L1=find_frequent_1-itemsets(D); // 找出所有頻繁1項集
     For(k=2;Lk-1!=null;k++){
        Ck=apriori_gen(Lk-1); // 產(chǎn)生候選先较，并剪枝
        For each 事務(wù)t in D{ // 掃描D進行候選計數(shù)
            Ct =subset(Ck,t); // 得到t的子集
            For each 候選c 屬于 Ct
                         c.count++;
        }
        Lk={c屬于Ck | c.count>=min_sup}
}
Return L=所有的頻繁集携冤；
 
Procedure apriori_gen(Lk-1:frequent(k-1)-itemsets)
      For each項集l1屬于Lk-1
              For each項集 l2屬于Lk-1
                       If((l1[1]=l2[1])&&( l1[2]=l2[2])&&…….
&& (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])) then{
                   c=l1連接l2 //連接步：產(chǎn)生候選
                   if has_infrequent_subset(c,Lk-1) then
                       delete c; //剪枝步：刪除非頻繁候選
                   else add c to Ck;
                  }
          Return Ck;
 
Procedure has_infrequent_sub(c:candidate k-itemset; Lk-1:frequent(k-1)-itemsets)
        For each(k-1)-subset s of c
            If s不屬于Lk-1 then
               Return true;
        Return false;

下面就是真正的Java代碼實現(xiàn)了。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Apriori{
    // 支持度閾值
    private final static int SUPPORT = 2;
    // 置信度閾值
    private final static double CONFIDENCE = 0.7;
    // 項之間的分隔符
    private final static String GAP = ";";
     // 項之間的分隔符
    private final static String CON = "-->";

    /**
     * 這個是用來找出1-頻繁項集的方法闲勺，因為1-頻繁項集的特殊性曾棕，
     * 所以需要特別的方法來返回1-頻繁項集
     * @param dataList
     * @return
     */

    private Map<String, Integer> find1_FrequentSet(ArrayList<String> dataList){
        Map<String, Integer> resultSetMap = new HashMap<>();
        for (String data:dataList) {
            String [] strings = data.split(GAP);
            //這是把所有的購買記錄一條條的篩選出來
            for (String string : strings) {
                string += GAP;
                if (resultSetMap.get(string)==null) {
                    resultSetMap.put(string,1);
                }
                else {
                    resultSetMap.put(string, resultSetMap.get(string)+1);
                }
            }
        }
        //返回的是一個各種商品對應(yīng)出現(xiàn)頻次的Map（或可稱之為頻繁項集）。鍵為商品序號菜循，值為出現(xiàn)次數(shù)翘地。
        return resultSetMap;    
    }

    /**
     * 使用先驗知識，判斷候選集是否是頻繁項集
     * @param candidate
     * @param setMap
     * @return
     */

    private boolean hasInfrequentSubset(String candidateString, Map<String, Integer> setMap){
        String[] strings = candidateString.split(GAP);
        //找出候選集所有的子集癌幕，并判斷每個子集是否屬于頻繁子集
        for (int i=0; i<strings.length; ++i ) {
            String subString = "";
            for (int j = 0; j<strings.length;++j ) {
                if (j!=i) {
                    subString += strings[j]+GAP;
                }
            }
            if (setMap.get(subString)==null) {
                return true;
            }
        }
        return false;
    }

    /**
     * 根據(jù)上面的頻繁項集的集合選出候選集
     * @param setMap
     * @return
     */
    private Map<String,Integer> aprioriGen(Map<String, Integer> setMap){
        //此處傳入的參數(shù)就是上面返回的頻繁項集衙耕。
        Map<String, Integer> candidateSetMap = new HashMap<>();
        // 對每個商品取集合
        Set<String> candidateSet = setMap.keySet();
        //單獨考慮每個商品的支持度，如果合格勺远，就可以進行拼接橙喘。否則丟掉。
        for (String s1 : candidateSet) {
            String[] strings1 = s1.split(GAP);
            String s1string = "";
            for (String temp : strings1) {
                s1string += temp+GAP;
            }
            for (String s2 :  candidateSet) {
                //此處也是默認商品序號是有序的胶逢。這樣先判定前l(fā)en-1項是否相等厅瞎。
                //如果前面相等饰潜，第len項不相等，那么就可以拼接成len+1長度的候選集了和簸。
                String[] strings2 = s2.split(GAP);
                boolean flag = true;
                for (int i=0; i< strings1.length-1;++i) {
                    if (strings1[i].compareTo(strings2[i]) != 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag && strings1[strings1.length-1].compareTo(strings2[strings2.length-1])<0) {
                   //連接步：產(chǎn)生候選
                   String c=s1string+strings2[strings2.length-1]+GAP;
                   if (hasInfrequentSubset(c,setMap)) {
                        //剪枝步：刪除非頻繁的候選
                    } 
                    else {
                        candidateSetMap.put(c,0);
                    }
                }
            }
        }
        return candidateSetMap;
    }

    /**
     * 算法主程序
     * @param dataList
     * @return
     */

    public Map<String, Integer> apriori(ArrayList<String> dataList){
        Map<String, Integer> setpFrequentSetMap = new HashMap<>();
        setpFrequentSetMap.putAll(find1_FrequentSet(dataList));

        Map<String, Integer> frequentSetMap = new HashMap<String, Integer>();
        frequentSetMap.putAll(setpFrequentSetMap);
        // Into the loop choose
        while(setpFrequentSetMap!=null && setpFrequentSetMap.size() > 0){
            Map<String, Integer> candidateSetMap = aprioriGen(setpFrequentSetMap);
            //得到的就是候選集 candidateSetMap 彭雾，當然我們只要key部分即可啦！
            Set<String> candidateKeySet = candidateSetMap.keySet();

            //掃描D锁保，進行計數(shù)
            for (String data : dataList) {
                for (String candidate :  candidateKeySet) {
                    boolean flag = true;
                    String[] strings = candidate.split(GAP);
                    for (String string : strings) {
                        //意味著在Data薯酝，也就是在初始的購物記錄中查找當前的頻繁項集中的某一條。尋找string如果不成功身诺，則返回-1蜜托；
                        // indexOf(Object o)方法 
                        // 功能：查找某個元素在ArrayList中第一次出現(xiàn)的位置。
                        if (data.indexOf(string+GAP)==-1) {
                            flag = false;
                            break;
                        }
                    }
                    //如果查找成功霉赡，那么就可以丟到正式的候選集中了橄务。
                    if (flag) {
                        candidateSetMap.put(candidate,candidateSetMap.get(candidate)+1);
                    }
                }
            }
            //從候選集中找到符合支持度的頻繁項集，stepFrequentSetMap顧名思義就是每一次找到的新的頻繁集穴亏。
            //所以在置入新的頻繁集之前蜂挪，都要先把上次的清空掉。
            setpFrequentSetMap.clear();
            for (String candidate : candidateKeySet) {
                Integer count = candidateSetMap.get(candidate);
                if (count>=SUPPORT) {
                    setpFrequentSetMap.put(candidate,count);
                }
            }
            // puaAll的作用是把一個Map的所有元素置入并且去重嗓化。
            // 合并所有頻繁集
            frequentSetMap.putAll(setpFrequentSetMap);
        }
        //While循環(huán)結(jié)束的條件是新的頻繁項集的大小為0.也就是必須要完全空了才出來棠涮。
        //這時候已經(jīng)確保了frequentSetMap包含有所有的頻繁項集了。
        return frequentSetMap;
    }
    /**
     * 求一個集合所有的非空真子集
     * 
     * @param sourceSet
     * @return
     * 為了以后可以用在其他地方刺覆，這里我們不是用遞歸的方法
     * 
     * 參考：http://blog.163.com/xiaohui_1123@126/blog/static/3980524020109784356915/
     * 思路：假設(shè)集合S（A,B,C,D）严肪，其大小為4，擁有2的4次方個子集谦屑，即0-15驳糯，二進制表示為0000，0001氢橙，...酝枢，1111。
     * 對應(yīng)的子集為空集悍手，{D}帘睦，...，{A,B,C,D}坦康。
     */

    private List<String> subset(String sourceSet){
        //“按位對應(yīng)法”,從1-2^strings.length-1位竣付，可以用二進制來表示是否取到該值。
        /*
        如集合A={a,b,c},對于任意一個元素涝焙，在每個子集中卑笨，要么存在，要么不存在仑撞。 映射為子集：
        (a,b,c)
        (1,1,1)->(a,b,c)
        (1,1,0)->(a,b)
        (1,0,1)->(a,c)
        (1,0,0)->(a)
        (0,1,1)->(b,c)
        (0,1,0)->(b)
        (0,0,1)->(c)
        (0,0,0)->@(@表示空集)
        */
        List<String> result = new ArrayList<>();
        String[] strings = sourceSet.split(GAP);
        for (int i = 1; i<(Math.pow(2,strings.length)) - 1; ++i ) {
            String item = "";
            int ii = i;
            int[] flag = new int[strings.length]; 
            int count = 0;
            while(ii>=0 && count<strings.length ){
                flag[count] = ii%2;
                //此處可以理解為右移操作赤兴，即檢查完當前位之后妖滔，可以跳到更高位去檢測是否取值。
                ii=ii/2;
                ++count;
            }
            for (int s=0;s<flag.length;++s) {
                if (flag[s]==1) {
                    //此處應(yīng)該是從右邊開始往左邊加桶良。所以item在后面
                    item+=strings[s]+GAP+item;
                }
            }
            result.add(item);
        }
        return result;
    }

    /**
     * 集合運算座舍，A/B
     * @param A
     * @param B
     * @return
     */
    private String expect(String stringA, String stringB){
        String result = "";
        String[] stringAs = stringA.split(GAP);
        String[] stringBs = stringB.split(GAP);

        for(int i=0; i<stringAs.length;++i){
            boolean flag = true;
            for (int j = 0; j<stringBs.length ;++j ) {
                //如果指定的數(shù)與參數(shù)相等返回0。
                // 如果指定的數(shù)小于參數(shù)返回 -1陨帆。
                // 如果指定的數(shù)大于參數(shù)返回 1曲秉。
                if (stringAs[i].compareTo(stringBs[j])==0) {
                    flag=  false;
                    break;
                }
            }
            if (flag) {
                result += stringAs[i]+GAP;
            }
        }
        return result;
    }
    
    /**
     * 由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則
     * @param frequentSetMap
     * @return
     */
    public Map<String, Double> getRelationRules(Map<String, Integer> frequentSetMap){
        Map<String, Double> relationMap = new HashMap<>();
        Set<String> KeySet = frequentSetMap.keySet();
        for (String key : KeySet) {
            List<String> keySubset = subset(key);
            for (String keySubSetItem : keySubset) {
                //子集keySubsetItem也是頻繁項
                Integer count = frequentSetMap.get(keySubSetItem);
                if (count!=null) {
                     /*
                        置信度
                    　　置信度(confidence)揭示了A出現(xiàn)時B是否一定出現(xiàn)，如果出現(xiàn)疲牵，則出現(xiàn)的概率是多大承二。如果A->B的置信度是100%，則說明A出現(xiàn)時B一定會出現(xiàn)（返回來不一定）纲爸。
                        上圖中底板共出現(xiàn)5次亥鸠，其中4次同時購買了膠皮，底板->膠皮的置信度是80%识啦。
                    　　用公式表示是负蚊，物品A->B的置信度=物品{A,B}的支持度 / 物品{A}的支持度：
                    　　Confidence(A->B) = support({A,B}) / support({A}) = P(B|A)
                    */ 
                    Double confidence = (1.0*frequentSetMap.get(key))/(1.0*frequentSetMap.get(keySubSetItem));
                    if (confidence > CONFIDENCE) {
                        relationMap.put(keySubSetItem+CON+expect(key,keySubSetItem),confidence);
                    }
                }
            }
        }   
        return relationMap;
    }

    public static void main(String[] args){
        ArrayList<String> dataList = new ArrayList<>();
        dataList.add("1;2;5;");
        dataList.add("2;4;");
        dataList.add("2;3;");
        dataList.add("1;2;4;");
        dataList.add("1;3;");
        dataList.add("2;3;");
        dataList.add("1;3;");
        dataList.add("1;2;3;5;");
        dataList.add("1;2;3;");
        
        System.out.println("=數(shù)據(jù)集合==========");
        for(String string:dataList){
            System.out.println(string);
        }
        
        Apriori2 apriori2 = new Apriori2();
        
        System.out.println("=頻繁項集==========");
        
        Map<String, Integer> frequentSetMap = apriori2.apriori(dataList);
        Set<String> keySet = frequentSetMap.keySet();
        for(String key:keySet){
            System.out.println(key+" : "+frequentSetMap.get(key));
        }
        
        System.out.println("=關(guān)聯(lián)規(guī)則==========");
        Map<String, Double> relationRulesMap = apriori2.getRelationRules(frequentSetMap);
        Set<String> rrKeySet = relationRulesMap.keySet();
        for (String rrKey : rrKeySet){
            System.out.println(rrKey + "  :  " + relationRulesMap.get(rrKey));
        }
    }
}

上面這些代碼基本是照抄下面這個博客里面的。我就改動了一下那個獲取真子集的函數(shù)而已颓哮。其他的不好怎么改家妆，還不如直接抄。不過自己過一遍手之后確實感覺理解深刻了很多冕茅。

頻繁模式挖掘apriori算法介紹及Java實現(xiàn)

控制臺輸出如下：

[zbzhang@node61 JavaCode]$ java Apriori2
=數(shù)據(jù)集合==========
1;2;5;
2;4;
2;3;
1;2;4;
1;3;
2;3;
1;3;
1;2;3;5;
1;2;3;
=頻繁項集==========
1;2; : 4
1;3; : 4
5; : 2
2;3; : 4
4; : 2
2;4; : 2
1;5; : 2
3; : 6
2; : 7
1; : 6
1;2;5; : 2
1;2;3; : 2
2;5; : 2
=關(guān)聯(lián)規(guī)則==========
4;->2;  :  1.0
5;->1;2;  :  1.0
5;->1;  :  1.0
1;5;->2;  :  1.0
5;->2;  :  1.0
2;5;->1;  :  1.0
[zbzhang@node61 JavaCode]$

正文之后

下面是參考文獻時間：

使用Apriori進行關(guān)聯(lián)分析（一）
頻繁模式挖掘apriori算法介紹及Java實現(xiàn)
Java compareTo() 方法
Map獲取其鍵和值
Java進階--深入理解ArrayList實現(xiàn)原理
ArrayList的用法整理