杂项

启发式搜索与挖掘 (Heuristic Search & Mining): Apriori & PSO

Tip

Apriori 与 粒子群算法 (PSO) 代表了处理高维搜索空间的两种不同范式。

• Apriori 处理的是离散的组合爆炸问题。它利用代数结构上的“反单调性”对搜索树进行确定性的剪枝。
• PSO 处理的是连续的非凸优化问题。它利用概率论与仿生学原理，通过群体信息的交互在解空间中进行随机游走与收敛。

两者的共同元逻辑在于：避免全空间遍历，利用局部信息（子集性质或邻域最优）推导全局解。

1. Apriori 算法：离散空间的剪枝

定义

频繁项集与反单调性 (Anti-monotonicity)

设 $I=\{i_1,\dots ,i_m\}$ 为项的集合，$D$ 为事务数据库。 定义项集 $X\subseteq I$ 的支持度 (Support) 为包含 $X$ 的事务在 $D$ 中出现的频率。

Apriori 原理：若项集 $X$ 是频繁的（即 $Support(X)\ge \min \_sup$），则 $X$ 的所有子集 $Y\subset X$ 必然也是频繁的。

逆否命题（剪枝核心）：若 $X$ 不频繁，则 $X$ 的所有超集 $Z\supset X$ 均不频繁。

他是为了找到两个事务之间的关联规则：https://www.cnblogs.com/pinard/p/6293298.html

1.1 算法流程 (基于格理论的搜索)

Apriori 本质上是在项集的布尔格 (Boolean Lattice) 上进行广度优先搜索 (BFS)。

1. 初始化 ($k=1$)：扫描数据库，统计单个项的支持度，生成频繁 1-项集 $L_1$。
2. 连接步 (Join Step)：利用 $L_k$ 自连接生成候选 $k+1$ 项集 $C_{k+1}$。
   • 条件：两个 $k$-项集仅在最后一个元素不同时才连接。
3. 剪枝步 (Prune Step)：
   • 对于 $C_{k+1}$ 中的每个候选项 $c$，检查其所有 $k$-子集是否都在 $L_k$ 中。
   • 若存在任一子集不在 $L_k$ 中，则根据 Apriori 原理，剔除 $c$。
4. 迭代：重复步骤 2-3，直到 $L_k$ 为空。

---

2. 粒子群算法 (PSO)：连续空间的协同演化

Tip

PSO 将优化问题映射为鸟群觅食行为。其核心动力学方程由三部分组成：惯性 (Inertia) 保持运动趋势，认知 (Cognition) 追溯个体历史最优，社会 (Social) 追随群体全局最优。这是一种在探索 (Exploration) 与 开发 (Exploitation) 之间寻求平衡的随机搜索策略。

定义

粒子状态更新方程

设搜索空间为 $D$ 维，粒子 $i$ 在 $t$ 时刻的位置为 $x_i(t)\in {\mathbb{R}}^D$，速度为 $v_i(t)\in {\mathbb{R}}^D$。

1. 速度更新： $v_i(t+1)=\underset{\text{惯性项}}{\underbrace{\omega v_i(t)}}+\underset{\text{认知项 (个体记忆)}}{\underbrace{c_1{r}_1(p_i-x_i(t))}}+\underset{\text{社会项 (群体智慧)}}{\underbrace{c_2{r}_2(g-x_i(t))}}$
2. 位置更新： $x_i(t+1)=x_i(t)+v_i(t+1)$

其中：

• $\omega$: 惯性权重 (Inertia Weight)。
• $p_i$: 粒子 $i$ 的历史最优位置 (Personal Best)。
• $g$: 整个群体的全局最优位置 (Global Best)。
• $r_1,r_2\sim U(0,1)$: 随机参数，引入随机性以跳出局部最优。

2.1 算法特征

• 无梯度 (Gradient-free)：不需要目标函数可导，适用于黑箱模型。
• 记忆性：不同于模拟退火 (SA) 的无记忆性，PSO 的每个粒子都“记住”了自己的最好位置。

---

3. 比较与归纳

Note

结构化对比

维度	Apriori (关联规则)	PSO (智能优化)
数学空间	离散 (幂集格 $2^I$)	连续 (向量空间 ${\mathbb{R}}^D$)
核心算子	集合运算 ($\cap ,\cup ,\subset$)	线性代数运算 ($+,-,\times$)
收敛机制	确定性 (剪枝排除不可能解)	概率性 (迭代逼近最优解)
主要瓶颈	I/O 开销与组合爆炸	陷入局部最优与收敛速度
建模角色	特征发现 (挖掘变量间的隐式关系)	求解器 (寻找复杂模型的最佳参数)