apriori.java

it s apriori algorithm source code in java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package dm_lab1;


import java.sql.SQLException;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author smashdown
 */
public class Apriori {

    DB_Manager db_manager;
    double min_sup=0;
    int trans_count=0;
    public Apriori(DB_Manager db)
    {
        db_manager = db;
    }

    public LinkedList<FrequentItem> find_frequent_itemsets(double m_sup)
    {
        int i=1;
        min_sup = m_sup;

        LinkedList<FrequentItem> frequent_itemsets = new LinkedList<FrequentItem>();
        LinkedList<FrequentItem> L;
        LinkedList<FrequentItem> C=null;

        L = Find_frequent_1_itemsets();     // 1-itemset 구하기
        PrintTable("L" + i++, L);
        //while(i++ < 3)
        while(L.size() > 1)
        {
            C = apriori_gen(L);             // Ck-1 table 구하기
            L=C;
            PrintTable("L" + i++, C);
        }
        return frequent_itemsets;
    }

    public LinkedList<FrequentItem> apriori_gen(LinkedList<FrequentItem> L)
    {
        LinkedList<FrequentItem> C = new LinkedList<FrequentItem>();
        //Set<String> keyset = L.keySet();
        //String[] keys = (String[])keyset.toArray();

        int k = L.get(0).itemset.length()/2; // 1
        if(k==0)
        {
            for(int i=0;i<L.size();i++)
            {
                for(int j=i+1; j<L.size();j++)
                {
                    FrequentItem c = new FrequentItem(L.get(i).itemset+","+ L.get(j).itemset,-1);
                    if(IsFrequentItem(c))
                        C.addLast(c);
                }
            }
        }
        else
        {
            for(int i=0;i<L.size();i++)
            {
                for(int j=i+1; j<L.size();j++)
                {
                    // k 전까지 문자가 같으면 합쳐
                    if(IsPosibleInter(L.get(i).itemset, L.get(j).itemset, k))
                    {
                        // 합병된 itemset의 min_sup 테스트
                        FrequentItem c = new FrequentItem(L.get(i).itemset+","+ L.get(j).itemset.substring(k*2),-1);
                        if(IsFrequentItem(c))
                            C.addLast(c);
                    }
                }
            }
        }
        return C;
    }

    // 콜바이레퍼런스 확인해
    private boolean IsFrequentItem(FrequentItem c) {
        boolean r_value = false;
        boolean check=false;
        LinkedList<String> trans = null;
        StringParser sp = new StringParser();
        try {
            trans = db_manager.ScanTable();
        } catch (Exception ex) {
            Logger.getLogger(Apriori.class.getName()).log(Level.SEVERE, null, ex);
        }
        int current_sup = 0;

        for(int i=0; i<trans.size();i++)
        {
            sp.SetString(c.itemset);
            check = true;
            while(!sp.IsEnd())
            {
                String tmp = sp.GetNextItem();
                if(trans.get(i).indexOf(tmp) == -1) // 없는거임
                {
                    check = false;
                    break;
                }
            }
            if(check)
                current_sup++;
        }
        if((current_sup / (double)trans_count) >= min_sup)
            r_value = true;
        c.sup_count = current_sup;
        return r_value;
    }

    // k 전 글자까지가 같은지 체크
    private boolean IsPosibleInter(String s1, String s2, int k)
    {
        boolean r_value = true;
        StringParser sp1 = new StringParser(s1);
        StringParser sp2 = new StringParser(s2);

        for(int i=0; i<k ; i++)
        {
            if(sp1.GetNextItem().compareTo(sp2.GetNextItem()) != 0)
            {
                r_value = false;
                i=k;
            }
        }
        return r_value;
    }
    public LinkedList<FrequentItem> Find_frequent_1_itemsets()
    {
        LinkedList<FrequentItem> r_value = new LinkedList<FrequentItem>();
        LinkedList<String> trans = null;
        StringParser sp = new StringParser();
        try {
            trans = db_manager.ScanTable();
        } catch (Exception ex) {
            Logger.getLogger(Apriori.class.getName()).log(Level.SEVERE, null, ex);
        }
        LinkedList<String> inter = new LinkedList<String>();
        String tmp = "@";
        int i=0;
        System.out.print("\n=====Transaction Table=====\n");
        for(i=0; i<trans.size() ; i++)
        {
            tmp = trans.get(i);
            System.out.print(tmp+"\n");
            sp.SetString(tmp);
            while(!sp.IsEnd())
            {
                String item = sp.GetNextItem();
                if(!IsExistItem(inter, item))
                {
                    inter.addLast(item);
                }
            }
        }
        
        String[] s = inter.toArray(new String[inter.size()]);
        Arrays.sort(s, String.CASE_INSENSITIVE_ORDER);
        List<String> m = Arrays.asList(s);

        trans_count = i;
        int sup = 0;
        for(i=0; i<m.size() ; i++)
        {
            sup=0;
            for(int j=0; j<trans.size(); j++)
            {
                tmp = trans.get(j);
                sp.SetString(tmp);
                while(!sp.IsEnd())
                {
                    if(m.get(i).compareTo(sp.GetNextItem()) == 0)
                    {
                        sup++;
                    }
                }
            }
            if( (sup / (double)trans_count) >= min_sup)
            {
                FrequentItem fi = new FrequentItem(m.get(i), sup);
                r_value.addLast(fi);
            }
        }

        // debug
        //System.out.print("SEE!!   : ");
        //Set<String> set = r_value.keySet();
        //String[] keyset = set.toArray(new String[set.size()]);
        //for(i=0;i<r_value.size();i++)
        //{
        //    int t = r_value.get(keyset[i]);
        //    System.out.print(keyset[i]+ " : " + t + "\n");
        //}
        return r_value;
    }

    private void PrintTable(String table_name, LinkedList<FrequentItem> t)
    {
        System.out.print("\n======" + table_name + "=====\n");
        for(int i=0; i<t.size(); i++)
        {
            System.out.print(t.get(i).itemset + "| " + t.get(i).sup_count + "\n");
        }
    }
    public boolean IsExistItem(LinkedList<String> list, String item)
    {
        for(int i=0; i<list.size() ; i++)
        {
            if(list.get(i).compareTo(item) == 0)
                return true;
        }
        return false;
    }
}