myapriori.java

apriori java 实现 * A program to find association rules with the apriori algorithm (Agrawal et al. 199

        //Contruct the SQL
        if ( previousItems.length() > 0 ) {
            searchItems += " and a0."+transactionIdField+" in (" + previousItems + ") ";
        }
        for (int i = 1; i < noOfItem; i++) {
            transactionIDs += ", a" + i + "."+transactionIdField+"";
            tables += ", "+tableName+" a" + i;
            customerIDs += " and a" + (i - 1) + "."+customerIdField+" = a" + i + "."+customerIdField+"";

            if ( previousItems.length() > 0 )
                searchItems += " and a" + i + "."+transactionIdField+" in (" + previousItems + ") ";

            if (aprioriAll)
                aprioriAllFreq += " and a" + (i - 1) + "."+transactionSequenceField+" < a" + i + "."+transactionSequenceField+"";
            else
                skipDupTransaction += " and a" + (i - 1) + "."+transactionIdField+" < a" + i + "."+transactionIdField+"";
        }
        // Special handling for SQL of first itemset
        if (aprioriAllFreq.equals("") && customerIDs.equals("")) {
            return  "select " + transactionIDs + ", count(a0."+customerIdField+") as counts from " +
                    tables + " group by " + transactionIDs;
        }
        else {
            customerIDs = customerIDs.substring(4);
            return  "select " + transactionIDs + ", count(a0."+customerIdField+") as counts  from " +
                    tables + " where " + customerIDs + skipDupTransaction + aprioriAllFreq
                    + searchItems + " group by " + transactionIDs;
        }
    }

    /**
     * Find that N th itemsets
     * @param no_i      the N th itemset to find
     * @param pastItemsSet      The previous itemset to limit the search
     * @return      The list contain that N th itemsets
     * @exception Exception
     */
    public List findNthItemSet (int no_i, List pastItemsSet) throws Exception {
        ArrayList itemSet = new ArrayList();
        String sql = getSQL(no_i, pastItemsSet);
    //    System.out.println(sql);
   //     sql="select user from dual";
        PreparedStatement stmt = conn.prepareStatement(sql);
        ResultSet rs = stmt.executeQuery();
        while (rs.next()) {
            // Get distinct transactionID combination to run
            // set perpare statement also
            ArrayList items = new ArrayList();
            for (int i = 0; i < no_i; i++) {
                Integer transactionID = new Integer(rs.getInt(i + 1));
                items.add(transactionID);
            }
            int count = rs.getInt(countField);
            if (count >= getTotalCustomer()*support) {
                itemSet.add(items);
                supportCount.put(items, new Integer(count));
            }
        }
        rs.close();
        stmt.close();
        return  itemSet;
    }

    /**
     * Find all itemSets avaliable for the given support
     * @return  A List array.<br>
     *          First item is the list contains lists of itemsSets according<br>
     *          the the Nth no. e.g.: { {{1,2}, {2,3}}, {{1,2,3},{2,3,4}} }<br>
     *          Second item is the list contains all itemsSets without<br>
     *          separation. e.g.: { {1,2}, {2,3}, {1,2,3},{2,3,4} }<br>
     * @exception Exception
     */
    public List[] findItemSets () throws Exception {
        ArrayList allNthItemSet = new ArrayList();
        ArrayList allItemSets = new ArrayList();

        // Find all frequency itemset from the given support
        List pastItemsSet = null;
        int i = 0;
        while(true) {
            i++;
            List nthItemSet = findNthItemSet(i, pastItemsSet);
            if (nthItemSet.size() > 0) {
                allNthItemSet.add(nthItemSet);
                allItemSets.addAll(nthItemSet);
            }
            else
                break;  //break when no more items find
            pastItemsSet = nthItemSet;
        }
        List[] returnList =  {
            allNthItemSet, allItemSets
        };
        return  returnList;
    }

    /**
     * Find all rules according to the given support and confident
     * @param allNthItemSet     the list contains lists of itemsSets according<br>
     *                          to the Nth no. e.g.: { {{1,2}, {2,3}}, {{1,2,3},{2,3,4}} }<br>
     *
     * @param allItemSets       the list contains all itemsSets without<br>
     *                          separation. e.g.: { {1,2}, {2,3}, {1,2,3},{2,3,4} }<br>
     *
     * @return  A Map array.<br>
     *          First item is the map of rules of that key.<br>
     *          Second item is the map of supports of that key.<br>
     *          Third item is the map of confidence values of that key.<br>
     */
    public Map[] findRules (List allNthItemSet, List allItemSets) {
        HashMap rules = new HashMap();
        HashMap rules_support = new HashMap();
        HashMap rules_confidence = new HashMap();
        // Find all the rules from support
        // For all levels of itemsets
        for (int j = 0; j < allNthItemSet.size(); j++) {
            List nthItemSet = (List)allNthItemSet.get(j);
            // For all items of that level
            for (int k = 0; k < nthItemSet.size(); k++) {
                List thisItemSet = new ArrayList((List)nthItemSet.get(k));
                // Find All subset from all items
                for (int l = 0; l < allItemSets.size(); l++) {
                    List thisSubSet = new ArrayList((List)allItemSets.get(l));
                    List remainSet = new ArrayList((List)thisItemSet);
                    remainSet.removeAll(thisSubSet);
                    // Both SubSet and remaining set must contain in that itemset
                    if (thisItemSet.containsAll(thisSubSet) && thisItemSet.containsAll(remainSet)
                            && remainSet.size() > 0) {
                        int wholeCount = ((Integer)supportCount.get(thisItemSet)).intValue();
                        int baseCount = ((Integer)supportCount.get(thisSubSet)).intValue();
                        // Check if the confident enough
                        if ((float)wholeCount/(float)baseCount >= confident) {
                            // Use list to hold all values because the is more than one rules of that key
                            ArrayList values = (ArrayList)rules.get(thisSubSet);
                            ArrayList supports = (ArrayList)rules_support.get(thisSubSet);
                            ArrayList confidences = (ArrayList)rules_confidence.get(thisSubSet);
                            // Check if that key item found previously
                            if (values != null) {
                                // If that value item found previously, no need to re-add
                                if (!values.contains(remainSet)) {
                                    addRule(values, supports, confidences,
                                            allItemSets, thisSubSet, remainSet,
                                            wholeCount, baseCount);
                                }
                            }
                            else {
                                // Create new list to hold the values, support and confidences if new key item
                                values = new ArrayList();
                                supports = new ArrayList();
                                confidences = new ArrayList();
                                addRule(values, supports, confidences, allItemSets,
                                        thisSubSet, remainSet, wholeCount,
                                        baseCount);
                                rules.put(thisSubSet, values);
                                rules_support.put(thisSubSet, supports);
                                rules_confidence.put(thisSubSet, confidences);
                            }
                        }
                    }
                }
            }
        }
        Map[] returnMap =  {
            rules, rules_support, rules_confidence
        };
        return  returnMap;
    }

    /**
     * The main program to run and print out the rules
     * @param args
     * @exception Exception
     */
    public static void main (String[] args) throws Exception {
        long start = System.currentTimeMillis();
        myApriori dm = init(args);

        List[] itemSets = dm.findItemSets();
        List allNthItemSet = itemSets[0];
        List allItemSets = itemSets[1];

        Map[] rulesContents = dm.findRules(allNthItemSet, allItemSets);
        Map rules = rulesContents[0];
        Map rules_support = rulesContents[1];
        Map rules_confidence = rulesContents[2];

        //print out rules
        Iterator it = rules.keySet().iterator();
        System.out.println("Rules:\t\t\tSupport:\tConfident:");
        System.out.println("------\t\t\t--------\t----------");
        while (it.hasNext()) {
            Object key = it.next();
            List valueList = (List)rules.get(key);
            List valueList_support = (List)rules_support.get(key);
            List valueList_confidence = (List)rules_confidence.get(key);
            for (int x = 0; x < valueList.size(); x++) {
                System.out.println(
                // rules gotten
                key + "->" + valueList.get(x) + "\t\t" +
                // support of that rules
                ((Float)(valueList_support.get(x))).floatValue()*100 + "%\t" +
                // confident of that rules
                ((Float)(valueList_confidence.get(x))).floatValue()*100 + "%");
            }
        }
        System.out.println("time needed: " + (System.currentTimeMillis() -
                start));
    }
}