用C++ 實現(xiàn)的 可以 到下載 不過要注冊扣積分的
專注于為中小企業(yè)提供網(wǎng)站設(shè)計、成都網(wǎng)站制作服務(wù),電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)河曲免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了千余家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。
算法實現(xiàn)
（一）核心類
Apriori算法的核心實現(xiàn)類為AprioriAlgorithm，實現(xiàn)的Java代碼如下所示：
package org.shirdrn.datamining.association;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
/**
* B關(guān)聯(lián)規(guī)則挖掘：Apriori算法/B
*
* P該算法基本上按照Apriori算法的基本思想來實現(xiàn)的。
*
* @author shirdrn
* @date 2009/07/22 22:56:23
* @msn shirdrn#hotmail.com(#→@)
* @qq 187071722
*/
public class AprioriAlgorithm {
private MapInteger, SetString txDatabase; // 事務(wù)數(shù)據(jù)庫
private Float minSup; // 最小支持度
private Float minConf; // 最小置信度
private Integer txDatabaseCount; // 事務(wù)數(shù)據(jù)庫中的事務(wù)數(shù)
private MapInteger, SetSetString freqItemSet; // 頻繁項集集合
private MapSetString, SetSetString assiciationRules; // 頻繁關(guān)聯(lián)規(guī)則集合
public AprioriAlgorithm(
MapInteger, SetString txDatabase,
Float minSup,
Float minConf) {
this.txDatabase = txDatabase;
this.minSup = minSup;
this.minConf = minConf;
this.txDatabaseCount = this.txDatabase.size();
freqItemSet = new TreeMapInteger, SetSetString();
assiciationRules = new HashMapSetString, SetSetString();
}
/**
* 掃描事務(wù)數(shù)據(jù)庫，計算頻繁1-項集
* @return
*/
public MapSetString, Float getFreq1ItemSet() {
MapSetString, Float freq1ItemSetMap = new HashMapSetString, Float();
MapSetString, Integer candFreq1ItemSet = this.getCandFreq1ItemSet();
IteratorMap.EntrySetString, Integer it = candFreq1ItemSet.entrySet().iterator();
while(it.hasNext()) {
Map.EntrySetString, Integer entry = it.next();
// 計算支持度
Float supported = new Float(entry.getValue().toString())/new Float(txDatabaseCount);
if(supported=minSup) {
freq1ItemSetMap.put(entry.getKey(), supported);
}
}
return freq1ItemSetMap;
}
/**
* 計算候選頻繁1-項集
* @return
*/
public MapSetString, Integer getCandFreq1ItemSet() {
MapSetString, Integer candFreq1ItemSetMap = new HashMapSetString, Integer();
IteratorMap.EntryInteger, SetString it = txDatabase.entrySet().iterator();
// 統(tǒng)計支持?jǐn)?shù)，生成候選頻繁1-項集
while(it.hasNext()) {
Map.EntryInteger, SetString entry = it.next();
SetString itemSet = entry.getValue();
for(String item : itemSet) {
SetString key = new HashSetString();
key.add(item.trim());
if(!candFreq1ItemSetMap.containsKey(key)) {
Integer value = 1;
candFreq1ItemSetMap.put(key, value);
}
else {
Integer value = 1+candFreq1ItemSetMap.get(key);
candFreq1ItemSetMap.put(key, value);
}
}
}
return candFreq1ItemSetMap;
}
/**
* 根據(jù)頻繁(k-1)-項集計算候選頻繁k-項集
*
* @param m 其中m=k-1
* @param freqMItemSet 頻繁(k-1)-項集
* @return
*/
public SetSetString aprioriGen(int m, SetSetString freqMItemSet) {
SetSetString candFreqKItemSet = new HashSetSetString();
IteratorSetString it = freqMItemSet.iterator();
SetString originalItemSet = null;
while(it.hasNext()) {
originalItemSet = it.next();
IteratorSetString itr = this.getIterator(originalItemSet, freqMItemSet);
while(itr.hasNext()) {
SetString identicalSet = new HashSetString(); // 兩個項集相同元素的集合(集合的交運算)
identicalSet.addAll(originalItemSet);
SetString set = itr.next();
identicalSet.retainAll(set); // identicalSet中剩下的元素是identicalSet與set集合中公有的元素
if(identicalSet.size() == m-1) { // (k-1)-項集中k-2個相同
SetString differentSet = new HashSetString(); // 兩個項集不同元素的集合(集合的差運算)
differentSet.addAll(originalItemSet);
differentSet.removeAll(set); // 因為有k-2個相同，則differentSet中一定剩下一個元素，即differentSet大小為1
differentSet.addAll(set); // 構(gòu)造候選k-項集的一個元素(set大小為k-1,differentSet大小為k)
candFreqKItemSet.add(differentSet); // 加入候選k-項集集合
}
}
}
return candFreqKItemSet;
}
/**
* 根據(jù)一個頻繁k-項集的元素(集合)，獲取到頻繁k-項集的從該元素開始的迭代器實例
* @param itemSet
* @param freqKItemSet 頻繁k-項集
* @return
*/
private IteratorSetString getIterator(SetString itemSet, SetSetString freqKItemSet) {
IteratorSetString it = freqKItemSet.iterator();
while(it.hasNext()) {
if(itemSet.equals(it.next())) {
break;
}
}
return it;
}
/**
* 根據(jù)頻繁(k-1)-項集，調(diào)用aprioriGen方法，計算頻繁k-項集
*
* @param k
* @param freqMItemSet 頻繁(k-1)-項集
* @return
*/
public MapSetString, Float getFreqKItemSet(int k, SetSetString freqMItemSet) {
MapSetString, Integer candFreqKItemSetMap = new HashMapSetString, Integer();
// 調(diào)用aprioriGen方法，得到候選頻繁k-項集
SetSetString candFreqKItemSet = this.aprioriGen(k-1, freqMItemSet);
// 掃描事務(wù)數(shù)據(jù)庫
IteratorMap.EntryInteger, SetString it = txDatabase.entrySet().iterator();
// 統(tǒng)計支持?jǐn)?shù)
while(it.hasNext()) {
Map.EntryInteger, SetString entry = it.next();
IteratorSetString kit = candFreqKItemSet.iterator();
while(kit.hasNext()) {
SetString kSet = kit.next();
SetString set = new HashSetString();
set.addAll(kSet);
set.removeAll(entry.getValue()); // 候選頻繁k-項集與事務(wù)數(shù)據(jù)庫中元素做差元算
if(set.isEmpty()) { // 如果拷貝set為空，支持?jǐn)?shù)加1
if(candFreqKItemSetMap.get(kSet) == null) {
Integer value = 1;
candFreqKItemSetMap.put(kSet, value);
}
else {
Integer value = 1+candFreqKItemSetMap.get(kSet);
candFreqKItemSetMap.put(kSet, value);
}
}
}
}
// 計算支持度，生成頻繁k-項集，并返回
return support(candFreqKItemSetMap);
}
/**
* 根據(jù)候選頻繁k-項集，得到頻繁k-項集
*
* @param candFreqKItemSetMap 候選k項集(包含支持計數(shù))
*/
public MapSetString, Float support(MapSetString, Integer candFreqKItemSetMap) {
MapSetString, Float freqKItemSetMap = new HashMapSetString, Float();
IteratorMap.EntrySetString, Integer it = candFreqKItemSetMap.entrySet().iterator();
while(it.hasNext()) {
Map.EntrySetString, Integer entry = it.next();
// 計算支持度
Float supportRate = new Float(entry.getValue().toString())/new Float(txDatabaseCount);
if(supportRateminSup) { // 如果不滿足最小支持度，刪除
it.remove();
}
else {
freqKItemSetMap.put(entry.getKey(), supportRate);
}
}
return freqKItemSetMap;
}
/**
* 挖掘全部頻繁項集
*/
public void mineFreqItemSet() {
// 計算頻繁1-項集
SetSetString freqKItemSet = this.getFreq1ItemSet().keySet();
freqItemSet.put(1, freqKItemSet);
// 計算頻繁k-項集(k1)
int k = 2;
while(true) {
MapSetString, Float freqKItemSetMap = this.getFreqKItemSet(k, freqKItemSet);
if(!freqKItemSetMap.isEmpty()) {
this.freqItemSet.put(k, freqKItemSetMap.keySet());
freqKItemSet = freqKItemSetMap.keySet();
}
else {
break;
}
k++;
}
}
/**
* P挖掘頻繁關(guān)聯(lián)規(guī)則
* P首先挖掘出全部的頻繁項集，在此基礎(chǔ)上挖掘頻繁關(guān)聯(lián)規(guī)則
*/
public void mineAssociationRules() {
freqItemSet.remove(1); // 刪除頻繁1-項集
IteratorMap.EntryInteger, SetSetString it = freqItemSet.entrySet().iterator();
while(it.hasNext()) {
Map.EntryInteger, SetSetString entry = it.next();
for(SetString itemSet : entry.getValue()) {
// 對每個頻繁項集進行關(guān)聯(lián)規(guī)則的挖掘
mine(itemSet);
}
}
}
/**
* 對從頻繁項集集合freqItemSet中每迭代出一個頻繁項集元素，執(zhí)行一次關(guān)聯(lián)規(guī)則的挖掘
* @param itemSet 頻繁項集集合freqItemSet中的一個頻繁項集元素
*/
public void mine(SetString itemSet) {
int n = itemSet.size()/2; // 根據(jù)集合的對稱性，只需要得到一半的真子集
for(int i=1; i=n; i++) {
// 得到頻繁項集元素itemSet的作為條件的真子集集合
SetSetString properSubset = ProperSubsetCombination.getProperSubset(i, itemSet);
// 對條件的真子集集合中的每個條件項集，獲取到對應(yīng)的結(jié)論項集，從而進一步挖掘頻繁關(guān)聯(lián)規(guī)則
for(SetString conditionSet : properSubset) {
SetString conclusionSet = new HashSetString();
conclusionSet.addAll(itemSet);
conclusionSet.removeAll(conditionSet); // 刪除條件中存在的頻繁項
confide(conditionSet, conclusionSet); // 調(diào)用計算置信度的方法，并且挖掘出頻繁關(guān)聯(lián)規(guī)則
}
}
}
/**
* 對得到的一個條件項集和對應(yīng)的結(jié)論項集，計算該關(guān)聯(lián)規(guī)則的支持計數(shù)，從而根據(jù)置信度判斷是否是頻繁關(guān)聯(lián)規(guī)則
* @param conditionSet 條件頻繁項集
* @param conclusionSet 結(jié)論頻繁項集
*/
public void confide(SetString conditionSet, SetString conclusionSet) {
// 掃描事務(wù)數(shù)據(jù)庫
IteratorMap.EntryInteger, SetString it = txDatabase.entrySet().iterator();
// 統(tǒng)計關(guān)聯(lián)規(guī)則支持計數(shù)
int conditionToConclusionCnt = 0; // 關(guān)聯(lián)規(guī)則(條件項集推出結(jié)論項集)計數(shù)
int conclusionToConditionCnt = 0; // 關(guān)聯(lián)規(guī)則(結(jié)論項集推出條件項集)計數(shù)
int supCnt = 0; // 關(guān)聯(lián)規(guī)則支持計數(shù)
while(it.hasNext()) {
Map.EntryInteger, SetString entry = it.next();
SetString txSet = entry.getValue();
SetString set1 = new HashSetString();
SetString set2 = new HashSetString();
set1.addAll(conditionSet);
set1.removeAll(txSet); // 集合差運算：set-txSet
if(set1.isEmpty()) { // 如果set為空，說明事務(wù)數(shù)據(jù)庫中包含條件頻繁項conditionSet
// 計數(shù)
conditionToConclusionCnt++;
}
set2.addAll(conclusionSet);
set2.removeAll(txSet); // 集合差運算：set-txSet
if(set2.isEmpty()) { // 如果set為空，說明事務(wù)數(shù)據(jù)庫中包含結(jié)論頻繁項conclusionSet
// 計數(shù)
conclusionToConditionCnt++;
}
if(set1.isEmpty() set2.isEmpty()) {
supCnt++;
}
}
// 計算置信度
Float conditionToConclusionConf = new Float(supCnt)/new Float(conditionToConclusionCnt);
if(conditionToConclusionConf=minConf) {
if(assiciationRules.get(conditionSet) == null) { // 如果不存在以該條件頻繁項集為條件的關(guān)聯(lián)規(guī)則
SetSetString conclusionSetSet = new HashSetSetString();
conclusionSetSet.add(conclusionSet);
assiciationRules.put(conditionSet, conclusionSetSet);
}
else {
assiciationRules.get(conditionSet).add(conclusionSet);
}
}
Float conclusionToConditionConf = new Float(supCnt)/new Float(conclusionToConditionCnt);
if(conclusionToConditionConf=minConf) {
if(assiciationRules.get(conclusionSet) == null) { // 如果不存在以該結(jié)論頻繁項集為條件的關(guān)聯(lián)規(guī)則
SetSetString conclusionSetSet = new HashSetSetString();
conclusionSetSet.add(conditionSet);
assiciationRules.put(conclusionSet, conclusionSetSet);
}
else {
assiciationRules.get(conclusionSet).add(conditionSet);
}
}
}
/**
* 經(jīng)過挖掘得到的頻繁項集Map
*
* @return 挖掘得到的頻繁項集集合
*/
public MapInteger, SetSetString getFreqItemSet() {
return freqItemSet;
}
/**
* 獲取挖掘到的全部的頻繁關(guān)聯(lián)規(guī)則的集合
* @return 頻繁關(guān)聯(lián)規(guī)則集合
*/
public MapSetString, SetSetString getAssiciationRules() {
return assiciationRules;
}
}
（二）輔助類
ProperSubsetCombination類是一個輔助類，在挖掘頻繁關(guān)聯(lián)規(guī)則的過程中，用于生成一個頻繁項集元素的非空真子集，實現(xiàn)代碼如下：
package org.shirdrn.datamining.association;
import java.util.BitSet;
import java.util.HashSet;
import java.util.Set;
/**
* B求頻繁項集元素(集合)的非空真子集集合/B
* P從一個集合（大小為n）中取出m(m屬于2~n/2的閉區(qū)間)個元素的組合實現(xiàn)類，獲取非空真子集的集合
*
* @author shirdrn
* @date 2009/07/22 22:56:23
* @msn shirdrn#hotmail.com(#→@)
* @qq 187071722
*/
public class ProperSubsetCombination {
private static String[] array;
private static BitSet startBitSet; // 比特集合起始狀態(tài)
private static BitSet endBitSet; // 比特集合終止?fàn)顟B(tài)，用來控制循環(huán)
private static SetSetString properSubset; // 真子集集合
/**
* 計算得到一個集合的非空真子集集合
*
* @param n 真子集的大小
* @param itemSet 一個頻繁項集元素
* @return 非空真子集集合
*/
public static SetSetString getProperSubset(int n, SetString itemSet) {
String[] array = new String[itemSet.size()];
ProperSubsetCombination.array = itemSet.toArray(array);
properSubset = new HashSetSetString();
startBitSet = new BitSet();
endBitSet = new BitSet();
// 初始化startBitSet，左側(cè)占滿1
for (int i=0; in; i++) {
startBitSet.set(i, true);
}
// 初始化endBit，右側(cè)占滿1
for (int i=array.length-1; i=array.length-n; i--) {
endBitSet.set(i, true);
}
// 根據(jù)起始startBitSet，將一個組合加入到真子集集合中
get(startBitSet);
while(!startBitSet.equals(endBitSet)) {
int zeroCount = 0; // 統(tǒng)計遇到10后，左邊0的個數(shù)
int oneCount = 0; // 統(tǒng)計遇到10后，左邊1的個數(shù)
int pos = 0; // 記錄當(dāng)前遇到10的索引位置
// 遍歷startBitSet來確定10出現(xiàn)的位置
for (int i=0; iarray.length; i++) {
if (!startBitSet.get(i)) {
zeroCount++;
}
if (startBitSet.get(i) !startBitSet.get(i+1)) {
pos = i;
oneCount = i - zeroCount;
// 將10變?yōu)?1
startBitSet.set(i, false);
startBitSet.set(i+1, true);
break;
}
}
// 將遇到10后，左側(cè)的1全部移動到最左側(cè)
int counter = Math.min(zeroCount, oneCount);
int startIndex = 0;
int endIndex = 0;
if(pos1 counter0) {
pos--;
endIndex = pos;
for (int i=0; icounter; i++) {
startBitSet.set(startIndex, true);
startBitSet.set(endIndex, false);
startIndex = i+1;
pos--;
if(pos0) {
endIndex = pos;
}
}
}
get(startBitSet);
}
return properSubset;
}
/**
* 根據(jù)一次移位操作得到的startBitSet，得到一個真子集
* @param bitSet
*/
private static void get(BitSet bitSet) {
SetString set = new HashSetString();
for(int i=0; iarray.length; i++) {
if(bitSet.get(i)) {
set.add(array[i]);
}
}
properSubset.add(set);
}
}
測試用例
對上述Apriori算法的實現(xiàn)進行了簡單的測試，測試用例如下所示：
package org.shirdrn.datamining.association;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
import org.shirdrn.datamining.association.AprioriAlgorithm;
import junit.framework.TestCase;
/**
* BApriori算法測試類/B
*
* @author shirdrn
* @date 2009/07/22 22:56:23
* @msn shirdrn#hotmail.com(#→@)
* @qq 187071722
*/
public class TestAprioriAlgorithm extends TestCase {
private AprioriAlgorithm apriori;
private MapInteger, SetString txDatabase;
private Float minSup = new Float("0.50");
private Float minConf = new Float("0.70");
@Override
protected void setUp() throws Exception {
create(); // 構(gòu)造事務(wù)數(shù)據(jù)庫
apriori = new AprioriAlgorithm(txDatabase, minSup, minConf);
}
/**
* 構(gòu)造模擬事務(wù)數(shù)據(jù)庫txDatabase
*/
public void create() {
txDatabase = new HashMapInteger, SetString();
SetString set1 = new TreeSetString();
set1.add("A");
set1.add("B");
set1.add("C");
set1.add("E");
txDatabase.put(1, set1);
SetString set2 = new TreeSetString();
set2.add("A");
set2.add("B");
set2.add("C");
txDatabase.put(2, set2);
SetString set3 = new TreeSetString();
set3.add("C");
set3.add("D");
txDatabase.put(3, set3);
SetString set4 = new TreeSetString();
set4.add("A");
set4.add("B");
set4.add("E");
txDatabase.put(4, set4);
}
/**
* 測試挖掘頻繁1-項集
*/
public void testFreq1ItemSet() {
System.out.println("挖掘頻繁1-項集 : " + apriori.getFreq1ItemSet());
}
/**
* 測試aprioriGen方法，生成候選頻繁項集
*/
public void testAprioriGen() {
System.out.println(
"候選頻繁2-項集 ： " +
this.apriori.aprioriGen(1, this.apriori.getFreq1ItemSet().keySet())
);
}
/**
* 測試挖掘頻繁2-項集
*/
public void testGetFreq2ItemSet() {
System.out.println(
"挖掘頻繁2-項集 ：" +
this.apriori.getFreqKItemSet(2, this.apriori.getFreq1ItemSet().keySet())
);
}
/**
* 測試挖掘頻繁3-項集
*/
public void testGetFreq3ItemSet() {
System.out.println(
"挖掘頻繁3-項集 ：" +
this.apriori.getFreqKItemSet(
3,
this.apriori.getFreqKItemSet(2, this.apriori.getFreq1ItemSet().keySet()).keySet()
)
);
}
/**
* 測試挖掘全部頻繁項集
*/
public void testGetFreqItemSet() {
this.apriori.mineFreqItemSet(); // 挖掘頻繁項集
System.out.println("挖掘頻繁項集 ：" + this.apriori.getFreqItemSet());
}
/**
* 測試挖掘全部頻繁關(guān)聯(lián)規(guī)則
*/
public void testMineAssociationRules() {
this.apriori.mineFreqItemSet(); // 挖掘頻繁項集
this.apriori.mineAssociationRules();
System.out.println("挖掘頻繁關(guān)聯(lián)規(guī)則 ：" + this.apriori.getAssiciationRules());
}
}
測試結(jié)果：
挖掘頻繁1-項集 : {[E]=0.5, [A]=0.75, [B]=0.75, [C]=0.75}
候選頻繁2-項集 ： [[E, C], [A, B], [B, C], [A, C], [E, B], [E, A]]
挖掘頻繁2-項集 ：{[A, B]=0.75, [B, C]=0.5, [A, C]=0.5, [E, B]=0.5, [E, A]=0.5}
挖掘頻繁3-項集 ：{[E, A, B]=0.5, [A, B, C]=0.5}
挖掘頻繁項集 ：{1=[[E], [A], [B], [C]], 2=[[A, B], [B, C], [A, C], [E, B], [E, A]], 3=[[E, A, B], [A, B, C]]}
挖掘頻繁關(guān)聯(lián)規(guī)則 ：{[E]=[[A], [B], [A, B]], [A]=[[B]], [B]=[[A]], [B, C]=[[A]], [A, C]=[[B]], [E, B]=[[A]], [E, A]=[[B]]}
從測試結(jié)果看到，使用Apriori算法挖掘得到的全部頻繁項集為：
{1=[[E], [A], [B], [C]], 2=[[A, B], [B, C], [A, C], [E, B], [E, A]], 3=[[E, A, B], [A, B, C]]}
使用Apriori算法挖掘得到的全部頻繁關(guān)聯(lián)規(guī)則為：
{E}→{A}、{E}→{B}、{E}→{A,B}、{A}→{B}、{B}→{A}、{B,C}→{A}、{A,C}→{B}、{B,E}→{A}、{A,E}→{B}。
用C++ 實現(xiàn)的 可以 到下載 不過要注冊扣積分的
算法實現(xiàn)
（一）核心類
Apriori算法的核心實現(xiàn)類為AprioriAlgorithm，實現(xiàn)的Java代碼如下所示：
package org.shirdrn.datamining.association;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
/**
* B關(guān)聯(lián)規(guī)則挖掘：Apriori算法/B
*
* P該算法基本上按照Apriori算法的基本思想來實現(xiàn)的。
*
* @author shirdrn
* @date 2009/07/22 22:56:23
* @msn shirdrn#hotmail.com(#→@)
* @qq 187071722
*/
public class AprioriAlgorithm {
private MapInteger, SetString txDatabase; // 事務(wù)數(shù)據(jù)庫
private Float minSup; // 最小支持度
private Float minConf; // 最小置信度
private Integer txDatabaseCount; // 事務(wù)數(shù)據(jù)庫中的事務(wù)數(shù)
private MapInteger, SetSetString freqItemSet; // 頻繁項集集合
private MapSetString, SetSetString assiciationRules; // 頻繁關(guān)聯(lián)規(guī)則集合
public AprioriAlgorithm(
MapInteger, SetString txDatabase,
Float minSup,
Float minConf) {
this.txDatabase = txDatabase;
this.minSup = minSup;
this.minConf = minConf;
this.txDatabaseCount = this.txDatabase.size();
freqItemSet = new TreeMapInteger, SetSetString();
assiciationRules = new HashMapSetString, SetSetString();
}
/**
* 掃描事務(wù)數(shù)據(jù)庫，計算頻繁1-項集
* @return
*/
public MapSetString, Float getFreq1ItemSet() {
MapSetString, Float freq1ItemSetMap = new HashMapSetString, Float();
MapSetString, Integer candFreq1ItemSet = this.getCandFreq1ItemSet();
IteratorMap.EntrySetString, Integer it = candFreq1ItemSet.entrySet().iterator();
while(it.hasNext()) {
Map.EntrySetString
java中調(diào)用操作系統(tǒng)控制臺（就是命令行），控制臺里運行R腳本（可以在命令行里用Rscript，不一定要在R環(huán)境底下寫）。
實在不行試試weka。
import?java.util.HashMap;
import?java.util.HashSet;
import?java.util.Iterator;
import?java.util.Map;
import?java.util.Set;
import?java.util.TreeMap;
/**
*?B關(guān)聯(lián)規(guī)則挖掘：Apriori算法/B
*?
*?P按照Apriori算法的基本思想來實現(xiàn)
*?
*?@author?king
*?@since?2013/06/27
*?
*/
public?class?Apriori?{
private?MapInteger,?SetString?txDatabase;?//?事務(wù)數(shù)據(jù)庫
private?Float?minSup;?//?最小支持度
private?Float?minConf;?//?最小置信度
private?Integer?txDatabaseCount;?//?事務(wù)數(shù)據(jù)庫中的事務(wù)數(shù)
private?MapInteger,?SetSetString?freqItemSet;?//?頻繁項集集合
private?MapSetString,?SetSetString?assiciationRules;?//?頻繁關(guān)聯(lián)規(guī)則集合
public?Apriori(
MapInteger,?SetString?txDatabase,?
Float?minSup,?
Float?minConf)?{
???this.txDatabase?=?txDatabase;
???this.minSup?=?minSup;
???this.minConf?=?minConf;
???this.txDatabaseCount?=?this.txDatabase.size();
???freqItemSet?=?new?TreeMapInteger,?SetSetString();
???assiciationRules?=?new?HashMapSetString,?SetSetString();
}
/**
*?掃描事務(wù)數(shù)據(jù)庫，計算頻繁1-項集
*?@return
*/
public?MapSetString,?Float?getFreq1ItemSet()?{
???MapSetString,?Float?freq1ItemSetMap?=?new?HashMapSetString,?Float();
???MapSetString,?Integer?candFreq1ItemSet?=?this.getCandFreq1ItemSet();
???IteratorMap.EntrySetString,?Integer?it?=?candFreq1ItemSet.entrySet().iterator();
???while(it.hasNext())?{
Map.EntrySetString,?Integer?entry?=?it.next();
//?計算支持度
Float?supported?=?new?Float(entry.getValue().toString())/new?Float(txDatabaseCount);
if(supported=minSup)?{
?freq1ItemSetMap.put(entry.getKey(),?supported);
}
???}
???return?freq1ItemSetMap;
}
/**
*?計算候選頻繁1-項集
*?@return
*/
public?MapSetString,?Integer?getCandFreq1ItemSet()?{
???MapSetString,?Integer?candFreq1ItemSetMap?=?new?HashMapSetString,?Integer();
???IteratorMap.EntryInteger,?SetString?it?=?txDatabase.entrySet().iterator();
???//?統(tǒng)計支持?jǐn)?shù)，生成候選頻繁1-項集
???while(it.hasNext())?{
Map.EntryInteger,?SetString?entry?=?it.next();
SetString?itemSet?=?entry.getValue();
for(String?item?:?itemSet)?{
?SetString?key?=?new?HashSetString();
?key.add(item.trim());
?if(!candFreq1ItemSetMap.containsKey(key))?{
??Integer?value?=?1;
??candFreq1ItemSetMap.put(key,?value);
?}
?else?{
??Integer?value?=?1+candFreq1ItemSetMap.get(key);
??candFreq1ItemSetMap.put(key,?value);
?}
}
???}
???return?candFreq1ItemSetMap;
}
/**
*?根據(jù)頻繁(k-1)-項集計算候選頻繁k-項集
*?
*?@param?m?其中m=k-1
*?@param?freqMItemSet?頻繁(k-1)-項集
*?@return
*/
public?SetSetString?aprioriGen(int?m,?SetSetString?freqMItemSet)?{
???SetSetString?candFreqKItemSet?=?new?HashSetSetString();
???IteratorSetString?it?=?freqMItemSet.iterator();
???SetString?originalItemSet?=?null;
???while(it.hasNext())?{
originalItemSet?=?it.next();
IteratorSetString?itr?=?this.getIterator(originalItemSet,?freqMItemSet);
while(itr.hasNext())?{
?SetString?identicalSet?=?new?HashSetString();?//?兩個項集相同元素的集合(集合的交運算)????
?identicalSet.addAll(originalItemSet);?
?SetString?set?=?itr.next();?
?identicalSet.retainAll(set);?//?identicalSet中剩下的元素是identicalSet與set集合中公有的元素
?if(identicalSet.size()?==?m-1)?{?//?(k-1)-項集中k-2個相同
??SetString?differentSet?=?new?HashSetString();?//?兩個項集不同元素的集合(集合的差運算)
??differentSet.addAll(originalItemSet);
??differentSet.removeAll(set);?//?因為有k-2個相同，則differentSet中一定剩下一個元素，即differentSet大小為1
??differentSet.addAll(set);?//?構(gòu)造候選k-項集的一個元素(set大小為k-1,differentSet大小為k)
??if(!this.has_infrequent_subset(differentSet,?freqMItemSet))
??candFreqKItemSet.add(differentSet);?//?加入候選k-項集集合
?}
}
???}
???return?candFreqKItemSet;
}
/**
?*?使用先驗知識，剪枝。若候選k項集中存在k-1項子集不是頻繁k-1項集，則刪除該候選k項集
?*?@param?candKItemSet
?*?@param?freqMItemSet
?*?@return
?*/
private?boolean?has_infrequent_subset(SetString?candKItemSet,?SetSetString?freqMItemSet)?{
SetString?tempSet?=?new?HashSetString();
tempSet.addAll(candKItemSet);
IteratorString?itItem?=?candKItemSet.iterator();
while(itItem.hasNext())?{
String?item?=?itItem.next();
tempSet.remove(item);//?該候選去掉一項后變?yōu)閗-1項集
if(!freqMItemSet.contains(tempSet))//?判斷k-1項集是否是頻繁項集
return?true;
tempSet.add(item);//?恢復(fù)
}
return?false;
}
/**
*?根據(jù)一個頻繁k-項集的元素(集合)，獲取到頻繁k-項集的從該元素開始的迭代器實例
*?@param?itemSet
*?@param?freqKItemSet?頻繁k-項集
*?@return
*/
private?IteratorSetString?getIterator(SetString?itemSet,?SetSetString?freqKItemSet)?{
???IteratorSetString?it?=?freqKItemSet.iterator();
???while(it.hasNext())?{
if(itemSet.equals(it.next()))?{
?break;
}
???}
???return?it;
}
/**
*?根據(jù)頻繁(k-1)-項集，調(diào)用aprioriGen方法，計算頻繁k-項集
*?
*?@param?k?
*?@param?freqMItemSet?頻繁(k-1)-項集
*?@return
*/
public?MapSetString,?Float?getFreqKItemSet(int?k,?SetSetString?freqMItemSet)?{
???MapSetString,?Integer?candFreqKItemSetMap?=?new?HashMapSetString,?Integer();
???//?調(diào)用aprioriGen方法，得到候選頻繁k-項集
???SetSetString?candFreqKItemSet?=?this.aprioriGen(k-1,?freqMItemSet);
??
???//?掃描事務(wù)數(shù)據(jù)庫
???IteratorMap.EntryInteger,?SetString?it?=?txDatabase.entrySet().iterator();
???//?統(tǒng)計支持?jǐn)?shù)
???while(it.hasNext())?{
Map.EntryInteger,?SetString?entry?=?it.next();
IteratorSetString?kit?=?candFreqKItemSet.iterator();
while(kit.hasNext())?{
?SetString?kSet?=?kit.next();
?SetString?set?=?new?HashSetString();
?set.addAll(kSet);
?set.removeAll(entry.getValue());?//?候選頻繁k-項集與事務(wù)數(shù)據(jù)庫中元素做差運算
?if(set.isEmpty())?{?//?如果拷貝set為空，支持?jǐn)?shù)加1
??if(candFreqKItemSetMap.get(kSet)?==?null)?{
???Integer?value?=?1;
???candFreqKItemSetMap.put(kSet,?value);
??}
??else?{
???Integer?value?=?1+candFreqKItemSetMap.get(kSet);
???candFreqKItemSetMap.put(kSet,?value);
??}
?}
}
???}??
python3關(guān)聯(lián)規(guī)則Apriori代碼模版
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from numpy import *
def loadDataSet():
return [['a', 'c', 'e'], ['b', 'd'], ['b', 'c'], ['a', 'b', 'c', 'd'], ['a', 'b'], ['b', 'c'], ['a', 'b'],
['a', 'b', 'c', 'e'], ['a', 'b', 'c'], ['a', 'c', 'e']]
def createC1(dataSet):
C1 = []
for transaction in dataSet:
for item in transaction:
if not [item] in C1:
C1.append([item])
C1.sort()
# 映射為frozenset唯?性的，可使?其構(gòu)造字典
return list(map(frozenset, C1))
# 從候選K項集到頻繁K項集（?持度計算）
def scanD(D, Ck, minSupport):
ssCnt = {}
for tid in D:
for can in Ck:
if can.issubset(tid):
if not can in ssCnt:
ssCnt[can] = 1
else:
ssCnt[can] += 1
numItems = float(len(D))
retList = []
supportData = {}
for key in ssCnt:
support = ssCnt[key] / numItems
if support = minSupport:
retList.insert(0, key)
supportData[key] = support
return retList, supportData
def calSupport(D, Ck, min_support):
dict_sup = {}
for i in D:
for j in Ck:
if j.issubset(i):
if not j in dict_sup:
dict_sup[j] = 1
else:
dict_sup[j] += 1
sumCount = float(len(D))
supportData = {}
relist = []
for i in dict_sup:
temp_sup = dict_sup[i] / sumCount
if temp_sup = min_support:
relist.append(i)
supportData[i] = temp_sup # 此處可設(shè)置返回全部的?持度數(shù)據(jù)（或者頻繁項集的?持度數(shù)據(jù)）return relist, supportData
# 改進剪枝算法
def aprioriGen(Lk, k): # 創(chuàng)建候選K項集 ##LK為頻繁K項集
retList = []
lenLk = len(Lk)
for i in range(lenLk):
for j in range(i + 1, lenLk):
L1 = list(Lk[i])[:k - 2]
L2 = list(Lk[j])[:k - 2]
L1.sort()
L2.sort()
if L1 == L2: # 前k-1項相等，則可相乘，這樣可防?重復(fù)項出現(xiàn)
# 進?剪枝（a1為k項集中的?個元素，b為它的所有k-1項?集）
a = Lk[i] | Lk[j] # a為frozenset()集合
a1 = list(a)
b = []
# 遍歷取出每?個元素，轉(zhuǎn)換為set，依次從a1中剔除該元素，并加?到b中
for q in range(len(a1)):
t = [a1[q]]
tt = frozenset(set(a1) - set(t))
b.append(tt)
t = 0
for w in b:
# 當(dāng)b（即所有k-1項?集）都是Lk（頻繁的）的?集，則保留，否則刪除。
if w in Lk:
t += 1
if t == len(b):
retList.append(b[0] | b[1])
return retList
def apriori(dataSet, minSupport=0.2):
C1 = createC1(dataSet)
D = list(map(set, dataSet)) # 使?list()轉(zhuǎn)換為列表
L1, supportData = calSupport(D, C1, minSupport)
L = [L1] # 加列表框，使得1項集為?個單獨元素
k = 2
while (len(L[k - 2]) 0):
Ck = aprioriGen(L[k - 2], k)
Lk, supK = scanD(D, Ck, minSupport) # scan DB to get Lk
supportData.update(supK)
L.append(Lk) # L最后?個值為空集
k += 1
del L[-1] # 刪除最后?個空集
return L, supportData # L為頻繁項集，為?個列表，1，2，3項集分別為?個元素。
# ?成集合的所有?集
def getSubset(fromList, toList):
for i in range(len(fromList)):
t = [fromList[i]]
tt = frozenset(set(fromList) - set(t))
if not tt in toList:
toList.append(tt)
tt = list(tt)
if len(tt) 1:
getSubset(tt, toList)
def calcConf(freqSet, H, supportData, ruleList, minConf=0.7):
for conseq in H:
conf = supportData[freqSet] / supportData[freqSet - conseq] # 計算置信度
# 提升度lift計算lift = p(a b) / p(a)*p(b)
lift = supportData[freqSet] / (supportData[conseq] * supportData[freqSet - conseq]) if conf = minConf and lift 1:
print(freqSet - conseq, '--', conseq, '?持度', round(supportData[freqSet - conseq], 2), '置信度：', conf, 'lift值為：', round(lift, 2))
ruleList.append((freqSet - conseq, conseq, conf))
# ?成規(guī)則
def gen_rule(L, supportData, minConf=0.7):
bigRuleList = []
for i in range(1, len(L)): # 從?項集開始計算
for freqSet in L[i]: # freqSet為所有的k項集
# 求該三項集的所有?空?集，1項集，2項集，直到k-1項集，?H1表?，為list類型,??為frozenset類型，
H1 = list(freqSet)
all_subset = []
getSubset(H1, all_subset) # ?成所有的?集
calcConf(freqSet, all_subset, supportData, bigRuleList, minConf)
return bigRuleList
if__name__ == '__main__':
dataSet = loadDataSet()
L, supportData = apriori(dataSet, minSupport=0.2)
rule = gen_rule(L, supportData, minConf=0.7)
運?結(jié)果：
?錄：
1.關(guān)聯(lián)分析
關(guān)聯(lián)分析是?種在?規(guī)模數(shù)據(jù)集中尋找有趣關(guān)系的任務(wù)。這種關(guān)系表現(xiàn)為兩種形式：
1.頻繁項集(frequency item sets)：經(jīng)常同時出現(xiàn)的?些元素的集合；
2.關(guān)聯(lián)規(guī)則(association rules): 意味著兩種元素之間存在很強的關(guān)系。
下?舉例來說明上?的兩個概念：
表1 ?個來?Hole Foods天?品店的
簡單交易清單
交易號碼商品
0?奶，萵苣
1萵苣，尿布，葡萄酒，甜菜
2萵苣，尿布，葡萄酒，橙汁
3萵苣，?奶，尿布，葡萄酒
4萵苣，?奶，尿布，橙汁
頻繁項集是指經(jīng)常出現(xiàn)在?起的元素的集合，上表中的集合 {葡萄酒，尿布，?奶} 就是頻繁項集的?個例?。同樣可以找到如 “尿布 -- 葡萄酒”的關(guān)聯(lián)規(guī)則，意味著如果有?買了尿布，就很可能也會買葡萄酒。使?頻繁項集和關(guān)聯(lián)規(guī)則，商家可以更好地理解顧客的消費?為，所以?部分關(guān)聯(lián)規(guī)則分析?例來?零售業(yè)。
理解關(guān)聯(lián)分析?先需要搞清楚下?三個問題：
1.如何定義這些有?的關(guān)系？
2.這些關(guān)系的強弱程度?是如何定義？
3.頻繁的定義是什么？
要回答上?的問題，最重要的是理解兩個概念：?持度和可信度。
?持度：?個項集的?持度(support)被定義為數(shù)據(jù)集中包含該項集的記錄占總記錄的?例。從表1 可以看出項集 {?奶} 的?持度為 4/5
可信度或置信度(confidence)：是針對?條諸如尿布??葡萄酒
2. Apriori 原理
假設(shè)經(jīng)營了?家雜貨店，于是我們對那些經(jīng)常在?起購買的商品?常感興趣。假設(shè)我們只有 4 種商品：商品0，商品1，商品 2，商品3. 那么
如何得可能被?起購買的商品的組合？
上圖顯?了物品之間所有可能的組合，從上往下?個集合是 ?
我們的?標(biāo)是找到經(jīng)常在?起購買的物品集合。這?使?集合的?持度來度量其出現(xiàn)的頻率。?個集合出現(xiàn)的?持度是指有多少?例的交易記錄包含該集合。例如，對于上圖，要計算 0,3
為了降低計算時間，研究?員發(fā)現(xiàn)了 Apriori
Apriori
即如果 {0,1} 是頻繁的，那么 {0}, {1} 也?定是頻繁的。
這個原理直觀上沒有什么?，但是反過來看就有?了，也就是說如果?個項集是?頻繁的，那么它的所有超集也是?頻繁的。如下圖所?：
3. 使? Apriori 算法來發(fā)現(xiàn)頻繁集
上?提到，關(guān)聯(lián)分析的兩個?標(biāo)：發(fā)現(xiàn)頻繁項集和發(fā)現(xiàn)關(guān)聯(lián)規(guī)則。?先需要找到頻繁項集，然后根據(jù)頻繁項集獲得關(guān)聯(lián)規(guī)則。?先來討論發(fā)現(xiàn)頻繁項集。Apriori 是發(fā)現(xiàn)頻繁項集的?種?法。
?先會?成所有單個物品的項集列表；
掃描交易記錄來查看哪些項集滿?最??持度要求，那些不滿?最??持度的集合會被去掉；
對剩下的集合進?組合以?成包含兩個元素的項集；
接下來重新掃描交易記錄，去掉不滿?最??持度的項集，重復(fù)進?直到所有項集都被去掉。數(shù)據(jù)集掃描的偽代碼：
對數(shù)據(jù)集中的每條交易記錄tran:
對每個候選項集can:
檢查?下can是否是tran的?集：
如果是，則增加can的計數(shù)值
對每個候選項集：
如果其?持度不低于最低值，則保留
返回所有頻繁項集列表
￥
5.9
百度文庫VIP限時優(yōu)惠現(xiàn)在開通,立享6億+VIP內(nèi)容
立即獲取
python3關(guān)聯(lián)規(guī)則Apriori代碼模版
python3關(guān)聯(lián)規(guī)則Apriori代碼模版
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from numpy import *
def loadDataSet():
return [['a', 'c', 'e'], ['b', 'd'], ['b', 'c'], ['a', 'b', 'c', 'd'], ['a', 'b'], ['b', 'c'], ['a', 'b'],
['a', 'b', 'c', 'e'], ['a', 'b', 'c'], ['a', 'c', 'e']]
def createC1(dataSet):
C1 = []
第 1 頁
for transaction in dataSet:
for item in transaction:
if not [item] in C1:
C1.append([item])
C1.sort()
# 映射為frozenset唯?性的，可使?其構(gòu)造字典
return list(map(frozenset, C1))
# 從候選K項集到頻繁K項集（?持度計算）
def scanD(D, Ck, minSupport):
Apriori算法是一種發(fā)現(xiàn)頻繁項集的基本算法。算法使用頻繁項集性質(zhì)的先驗知識。Apriori算法使用一種稱為逐層搜索的迭代方法，其中K項集用于探索(k+1)項集。首先，通過掃描數(shù)據(jù)庫，累計每個項的計數(shù)，并收集滿足最小支持度的項，找出頻繁1項集的集合。該集合記為L1.然后，使用L1找出頻繁2項集的集合L2，使用L2找到L3，如此下去，直到不能再找到頻繁k項集。Apriori算法的主要步驟如下：(1)掃描事務(wù)數(shù)據(jù)庫中的每個事務(wù)，產(chǎn)生候選1．項集的集合Cl；(2)根據(jù)最小支持度min_sup，由候選l-項集的集合Cl產(chǎn)生頻繁1一項集的集合Ll；(3)對k=l；(4)由Lk執(zhí)行連接和剪枝操作，產(chǎn)生候選(k+1)．項集的集合Ck+l-(5)根據(jù)最小支持度min_sup，由候選(k+1)一項集的集合Ck+l產(chǎn)生頻繁(k+1)-項集的集合Lk+1．(6)若L?≠①，則k．k+1，跳往步驟(4)；否則，跳往步驟(7)；(7)根據(jù)最小置信度min_conf,由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則，結(jié)束。
重慶分公司
重慶分公司
