事务数据匿名化与新兴模式隐藏技术解析

### 事务数据匿名化与新兴模式隐藏技术解析 在数据挖掘领域，事务数据的匿名化以及新兴模式的隐藏是重要的研究方向。事务数据包含大量个人敏感信息，在发布前必须进行匿名化处理；同时，在处理数据集时，也需要在隐藏新兴模式的同时尽可能保留频繁项集。下面将详细介绍相关技术及其实验评估。 #### 1. 新兴模式隐藏的局部重编码算法 在隐藏新兴模式时，采用了局部重编码的启发式算法。该算法通过对属性的等价类进行操作，以实现新兴模式的隐藏和频繁项集的保留。 - **等价类处理与局部重编码**：利用属性的等价类进行泛化，使用第 5 节定义的效用增益来确定局部重编码的优劣。由于可能存在许多等价类，这成为运行时间的一个瓶颈。为了加速这一步骤，采取了以下措施： - 使用哈希表缓存计算的效用增益值。 - 对等价类应用两个过滤器： - 忽略会导致频繁项集缺失的等价类，可通过局部重编码对频繁项集支持度的变化来计算。 - 丢弃会产生新的单属性新兴模式的局部重编码，可通过确定等价类与属性 e 的增长率来计算。 - **搜索策略**：使用模拟退火搜索（get - next - step - sa）来获取下一个局部重编码。 - **复杂度分析**：在最坏情况下，可能的重编码数量为 O(D × H)，局部重编码允许按元组进行重编码，最坏情况下可进行 |D1| + |D2| 次重编码操作。因此，寻找最优重编码的搜索空间为 O((|D1| + |D2|) × D × H)。mine - eps 和效用增益的计算是运行时间的瓶颈，效用增益计算的时间复杂度为 O(|Ae|×D×H×|F|)，其中 e ∈ E，|Ae| × D × H 是可能的等价类数量，对于每个类，分别使用 O(|E|) 和 O(|F|) 来计算 RGlocal 和 RDlocal。 #### 2. 实验评估 为了验证算法的有效性和效率，在 Adult 数据集上进行了一系列实验。 - **实验设置**：使用 Java SDK 1.61 实现算法，在配备 2.4GHz 四核 CPU 和 3.25GB RAM 的 Windows XP 系统 PC 上运行实验。使用系统调用调用相关实现来确定新兴模式和频繁项集。简化的 Adult 数据集包含 8 个属性，去除了包含缺失值的记录，并将记录分为年收入超过 50k 美元和未超过 50k 美元两类。 - **参数 θp 和 θq 的影响**： - 实验中不应用过滤器和模拟退火搜索，使用贪心搜索。性能以“频繁项集的失真度 / 缺失频繁项集的数量”表示。 - 当 σ 和 ρ 分别设置为 40% 和 5 时，得到的频繁项集如：{(Husband, Married - civ - spouse, Male), (Married - civ - spouse, White), (Married - civ - spouse, United - States), (Male, Private, White), (Male, Private, United - States), (Male, White, United - States), (Private, White, United - States)}。 - 当将频繁项集中的所有属性重编码为 All 时，得到 Adult 频繁项集的最大失真度为 623.1。 - 当 θp 和 θq 都设置为 0.8 时，应用贪心搜索后得到的频繁项集如：{(Relationship, United - States), (Married, White, United - States), (Male, Private, White), (Male, Private, United - States), (Male, White, United - States), Private, White, United - States)}，失真度为 21.5（在 623.1 中）。 - 改变 θp 和 θq 的值并测量贪心搜索的性能，结果如下表所示： | θp\θq | 0.0 | 0.2 | 0.4 | 0.6 | 0.8 | 1.0 | | --- | --- | --- | --- | --- | --- | --- | | 0 | 73.3/1 | 50.0/1 | 50.0/1 | 50.0/1 | 50.0/3 | 50.0/1 | | 0.2 | 73.3/1 | 59.7/1 | 38.2/1 | 38.2/1 | 46.5/1 | 11.5/4 | | 0.4 | 73.3/1 | 59.7/1 | 38.2/1 | 21.5/1 | 46.5/1 | 11.5/4 | | 0.6 | 73.3/1 | 59.7/1 | 21.5/1 | 38.2/1 | 46.5/1 | 11.5/4 | | 0.8 | 73.3/1 | 59.7/1 | 21.5/1 | 21.5/1 | 38.2/1 | 0/5 | | 1.0 | 11.5/3 | 11.5/3 | 11.5/3 | 11.5/3 | 11.5/