关联规则挖掘算法的深入解析

### 关联规则挖掘算法的深入解析 #### 1. FP - growth 方法优势 FP - growth 方法在频繁模式挖掘方面展现出高效且可扩展的特性。它大幅降低了搜索成本，速度比 Apriori 算法快约一个数量级。 #### 2. CFP - Tree 算法 ##### 2.1 CFP - Tree 与 FP - Tree 的结构差异 在 FP - growth 算法里，FP - tree 节点有六个字段，分别为项名、计数、父链接、子链接、兄弟链接和下一个链接（指向具有相同项名的下一个节点）。不过，子链接和兄弟链接仅在 FP - tree 构建过程中使用，父链接和下一个链接仅在挖掘过程中使用。 CFP - tree（紧凑 FP - tree）与 FP - tree 结构相似，但存在以下差异： - 每个 CFP - tree 节点有四个字段，即项编号（频繁 1 - 项集中项按频率降序排列的序号）、计数、cp - link 和 sn - link。因此，CFP - tree 仅需 FP - tree 2/3 的内存空间。 - FP - tree 是双向的，而 CFP - tree 是单向的。构建完成后，CFP - tree 仅存在从叶子到根的路径。 ##### 2.2 CFP - Tree 构建算法 算法 12.4（CFP - tree 构建）： 输入：DB，事务数据库；minsup，最小支持计数阈值。 输出：CFP - tree，紧凑频繁模式树。 方法： 1. 扫描事务数据库 DB 一次。收集频繁项集 F 及其支持度。将 F 按支持度降序排序为 L，即频繁项列表。 2. 创建 FP - tree 的根节点 T，并标记为“null”。对于 DB 中的每个事务，执行以下操作：选择频繁项，用它们在 L 中的顺序替换，并排序为 Is。设排序后的 Is 为 [p|P]，其中 p 是第一个元素，P 是剩余列表。调用 insert_tree([p|P], T)。 ```plaintext Procedure: insert_tree([p|P], T). 1. If T has no child or cannot find a child in which its item - no = p, then create a new node N. N.item - no = p, N.count = 1, N.cp - link = T; Insert N before the first node in which item - no is greater than p. 2. If T has a child N such that N.item - no = p, then increment N.count by 1. 3. If P is not empty, then call insert_tree(P, N) recursively. ``` 构建 CFP - tree 后，需将 sn - link 从兄弟链接改为下一个链接，并反转 cp - link。处理过程如下：从根节点遍历树。将当前节点 CN 作为最后一个节点添加到 header[CN.item - no] 的链接中。若 CN 没有子节点或其所有子节点和兄弟节点都已处理，则令 CN.cp - link = CN 的父节点，否则递归处理其子节点和兄弟节点。 以下是 CFP - tree 构建流程的 mermaid 流程图： ```mermaid graph TD; A[扫描数据库收集频繁项] --> B[创建 FP - tree 根节点]; B --> C[遍历事务]; C --> D[选择频繁项并排序]; D --> E[调用 insert_tree]; E --> F{是否有子节点且 item - no 匹配}; F -- 否 --> G[创建新节点]; F -- 是 --> H[增加节点计数]; G --> I{剩余列表是否为空}; H --> I; I -- 否 --> J[递归调用 insert_tree]; I -- 是 --> K[构建完成]; K --> L[修改链接]; ``` ##### 2.3 CFP - Tree 挖掘算法 算法 12.5（CFP - tree 挖掘算法）： 输入：一个 CFP - tree T 输出：与 T 对应的完整频繁项集 方法： ```plaintext 1. patlen = 1; 2. for (k = flen - 1; k >= 0; k--) { // flen 是频繁项集的长度 3. pat[0] = fitem[k]; 4. output {pat[0]} with support count[k]; 5. generate ST(k).EndArray[]; 6. mine(ST(k)); 7. } ``` ```plaintext Procedure mine(ST(ik, ..., i2, i1)) { 1. generate ST(ik, ..., i2, i1).fitem[] and ST(ik, ..., i2, i1).count[], let the length be listlen; 2. if (listlen == 0 ) then return; 3. if (listlen == 1) then { pat[patlen] = ST(ik, ..., i2, i1).fitem[0]; output pat with support ST(ik, ..., i2, i1).count[0]; return} 4. if ST(ik, ..., i2, ```