关联规则挖掘的核心目标是从大量事务数据中找出项与项之间的关联关系，其中Apriori算法是最经典的实现方案，其核心思想是通过逐层搜索的迭代方式，先找出所有的频繁项集，再从频繁项集中生成关联规则。下面我们将一步步用C#实现完整的关联规则挖掘流程。
一、基础概念与数据结构定义
在实现算法前，我们先明确几个核心概念：事务是单条数据记录，项集是若干项的集合，支持度是项集在所有事务中出现的频率，置信度是衡量关联规则可靠性的指标。首先定义基础的数据结构：
using System;
using System.Collections.Generic;
using System.Linq;
// 定义事务类，每个事务包含一个事务ID和项列表
public class Transaction
{
public int Id { get; set; }
public List<string> Items { get; set; }
}
// 定义项集类，包含项集本身和支持度计数
public class ItemSet
{
public List<string> Items { get; set; }
public int SupportCount { get; set; }
// 重写Equals和GetHashCode，方便项集去重和比较
public override bool Equals(object obj)
{
if (obj is ItemSet other)
{
return Items.OrderBy(x => x).SequenceEqual(other.Items.OrderBy(x => x));
}
return false;
}
public override int GetHashCode()
{
return string.Join(",", Items.OrderBy(x => x)).GetHashCode();
}
}
二、Apriori算法核心实现步骤
1. 生成候选1项集
第一步是统计所有单个项的出现次数，筛选出满足最小支持度计数的1项频繁项集：
public class Apriori
{
private List<Transaction> _transactions;
private int _minSupportCount;
public Apriori(List<Transaction> transactions, int minSupportCount)
{
_transactions = transactions;
_minSupportCount = minSupportCount;
}
// 生成候选1项集并筛选频繁1项集
public List<ItemSet> GenerateFrequent1ItemSets()
{
// 统计所有单个项的支持度计数
Dictionary<string, int> itemCounts = new Dictionary<string, int>();
foreach (var transaction in _transactions)
{
foreach (var item in transaction.Items)
{
if (itemCounts.ContainsKey(item))
{
itemCounts[item]++;
}
else
{
itemCounts[item] = 1;
}
}
}
// 筛选满足最小支持度计数的项，生成频繁1项集
List<ItemSet> frequent1ItemSets = new List<ItemSet>();
foreach (var kv in itemCounts)
{
if (kv.Value >= _minSupportCount)
{
frequent1ItemSets.Add(new ItemSet
{
Items = new List<string> { kv.Key },
SupportCount = kv.Value
});
}
}
return frequent1ItemSets;
}
}
2. 生成候选k项集并筛选频繁k项集
基于频繁k-1项集生成候选k项集，然后扫描事务集统计支持度，筛选出频繁k项集，直到无法生成更高阶的频繁项集：
// 生成候选k项集
private List<ItemSet> GenerateCandidateItemSets(List<ItemSet> prevFrequentItemSets, int k)
{
List<ItemSet> candidates = new List<ItemSet>();
// 连接步：将频繁k-1项集两两连接，生成候选k项集
for (int i = 0; i < prevFrequentItemSets.Count; i++)
{
for (int j = i + 1; j < prevFrequentItemSets.Count; j++)
{
var itemSet1 = prevFrequentItemSets[i].Items.OrderBy(x => x).ToList();
var itemSet2 = prevFrequentItemSets[j].Items.OrderBy(x => x).ToList();
// 前k-2项相同才连接
bool canJoin = true;
for (int m = 0; m < k - 2; m++)
{
if (itemSet1[m] != itemSet2[m])
{
canJoin = false;
break;
}
}
if (canJoin)
{
// 取两个项集的并集，去重后得到候选k项集
List<string> newItems = itemSet1.Union(itemSet2).OrderBy(x => x).ToList();
if (newItems.Count == k)
{
// 剪枝步：检查候选k项集的所有k-1子集是否都是频繁的
bool allSubsetsFrequent = true;
// 生成所有k-1子集
for (int m = 0; m < newItems.Count; m++)
{
var subset = newItems.Where((_, index) => index != m).ToList();
if (!prevFrequentItemSets.Any(itemSet => itemSet.Items.OrderBy(x => x).SequenceEqual(subset.OrderBy(x => x))))
{
allSubsetsFrequent = false;
break;
}
}
if (allSubsetsFrequent)
{
candidates.Add(new ItemSet { Items = newItems });
}
}
}
}
}
return candidates;
}
// 筛选频繁k项集
private List<ItemSet> FilterFrequentItemSets(List<ItemSet> candidateItemSets)
{
foreach (var candidate in candidateItemSets)
{
// 统计候选集在所有事务中的出现次数
foreach (var transaction in _transactions)
{
// 检查事务是否包含候选集的所有项
bool containsAll = true;
foreach (var item in candidate.Items)
{
if (!transaction.Items.Contains(item))
{
containsAll = false;
break;
}
}
if (containsAll)
{
candidate.SupportCount++;
}
}
}
// 筛选满足最小支持度计数的候选集
return candidateItemSets.Where(itemSet => itemSet.SupportCount >= _minSupportCount).ToList();
}
// 获取所有频繁项集
public List<ItemSet> GetAllFrequentItemSets()
{
List<ItemSet> allFrequentItemSets = new List<ItemSet>();
// 获取频繁1项集
var frequent1 = GenerateFrequent1ItemSets();
allFrequentItemSets.AddRange(frequent1);
List<ItemSet> prevFrequent = frequent1;
int k = 2;
while (prevFrequent.Count > 0)
{
// 生成候选k项集
var candidates = GenerateCandidateItemSets(prevFrequent, k);
if (candidates.Count == 0)
{
break;
}
// 筛选频繁k项集
var frequentK = FilterFrequentItemSets(candidates);
allFrequentItemSets.AddRange(frequentK);
prevFrequent = frequentK;
k++;
}
return allFrequentItemSets;
}
3. 从频繁项集生成关联规则
得到所有频繁项集后，就可以从中提取关联规则，计算规则的置信度，筛选出满足最小置信度的规则：
// 定义关联规则类
public class AssociationRule
{
public List<string> Antecedent { get; set; } // 前件
public List<string> Consequent { get; set; } // 后件
public double Confidence { get; set; } // 置信度
}
// 生成关联规则
public List<AssociationRule> GenerateAssociationRules(List<ItemSet> allFrequentItemSets, double minConfidence)
{
List<AssociationRule> rules = new List<AssociationRule>();
// 遍历所有频繁项集，项集长度至少为2才能生成规则
foreach (var itemSet in allFrequentItemSets.Where(itemSet => itemSet.Items.Count >= 2))
{
// 生成所有非空真子集作为前件
var subsets = GenerateNonEmptySubsets(itemSet.Items);
foreach (var subset in subsets)
{
// 后件 = 项集 - 前件
var consequent = itemSet.Items.Except(subset).ToList();
if (consequent.Count == 0)
{
continue;
}
// 获取前件对应的频繁项集的支持度计数
var antecedentItemSet = allFrequentItemSets.FirstOrDefault(f => f.Items.OrderBy(x => x).SequenceEqual(subset.OrderBy(x => x)));
if (antecedentItemSet == null)
{
continue;
}
// 计算置信度 = 项集支持度计数 / 前件支持度计数
double confidence = (double)itemSet.SupportCount / antecedentItemSet.SupportCount;
if (confidence >= minConfidence)
{
rules.Add(new AssociationRule
{
Antecedent = subset,
Consequent = consequent,
Confidence = confidence
});
}
}
}
return rules;
}
// 生成项集的所有非空真子集
private List<List<string>> GenerateNonEmptySubsets(List<string> items)
{
List<List<string>> subsets = new List<List<string>>();
int n = items.Count;
// 遍历所有非空子集，排除全集
for (int i = 1; i < (1 << n); i++)
{
List<string> subset = new List<string>();
for (int j = 0; j < n; j++)
{
if ((i & (1 << j)) != 0)
{
subset.Add(items[j]);
}
}
if (subset.Count < n)
{
subsets.Add(subset);
}
}
return subsets;
}
三、完整调用示例
下面我们构造一组测试事务数据，调用上述实现完成关联规则挖掘：
class Program
{
static void Main(string[] args)
{
// 构造测试事务数据
List<Transaction> transactions = new List<Transaction>
{
new Transaction { Id = 1, Items = new List<string> { "牛奶", "面包", "黄油" } },
new Transaction { Id = 2, Items = new List<string> { "牛奶", "面包" } },
new Transaction { Id = 3, Items = new List<string> { "面包", "黄油" } },
new Transaction { Id = 4, Items = new List<string> { "牛奶", "黄油" } },
new Transaction { Id = 5, Items = new List<string> { "牛奶", "面包", "黄油" } }
};
// 最小支持度计数为2，最小置信度为0.5
Apriori apriori = new Apriori(transactions, 2);
// 获取所有频繁项集
var frequentItemSets = apriori.GetAllFrequentItemSets();
Console.WriteLine("所有频繁项集：");
foreach (var itemSet in frequentItemSets)
{
Console.WriteLine($"项集：{string.Join(",", itemSet.Items)}，支持度计数：{itemSet.SupportCount}");
}
// 生成关联规则
var rules = apriori.GenerateAssociationRules(frequentItemSets, 0.5);
Console.WriteLine("n关联规则：");
foreach (var rule in rules)
{
Console.WriteLine($"{string.Join(",", rule.Antecedent)} => {string.Join(",", rule.Consequent)}，置信度：{rule.Confidence:F2}");
}
}
}
四、注意事项
上述实现是基础版本的Apriori算法，实际使用中可以根据需求优化：比如使用哈希表存储事务项提升子集判断效率，针对大规模数据可以引入FP-Growth算法减少扫描次数。另外需要注意，项集的比较需要统一排序，避免因为项顺序不同导致重复判断，同时支持度计数和置信度的计算要符合算法定义，保证结果准确性。