基于数据库的高效数据挖掘算法研究

### 基于数据库的高效数据挖掘算法研究 在数据挖掘领域，处理多维数据和频繁项集挖掘是两个重要的研究方向。本文将介绍两种有效的算法：ADenTS和Ppropad，它们分别在多维数据聚合查询和频繁项集挖掘方面展现出了出色的性能。 #### 1. ADenTS：自适应密度二叉树结构 ADenTS是一种用于多维数据立方体中聚合查询的有效树结构，其核心目标是在不损失准确性的前提下支持各种类型的聚合查询。 ##### 1.1 双凸峰去除算法 当具有相同父节点的子节点比其相邻网格更密集时，会出现相邻高凸峰之间的干扰问题。为了最小化这个问题，ADenTS采用了“双凸峰去除”的方法，具体步骤如下： ```plaintext Input: 密度二叉树TR, 数据集D(n, d), 最大网格大小S; Output: 更新后的树TR; Method: ADTreeUpdate-Double(TR, D(n, d), S) 1: level ← 树的底层; 2: 将TR中的所有节点标记为“单”; 3: REPEAT 4: 对于TR中当前层的每对节点N1和N2 5: p1 ← Area(N1)中的密度; 6: p2 ← Area(N2)中的密度; 7: q ← Area(N1) ∪ Area(N2)邻域中的密度; 8: IF p1 > q AND p2 > q // 双凸峰去除 9: PSet(N1) ← 从Area(N)中随机移除(p1 - q)个点的集合; 10: 根据PSet(N1)更新Count(N1), Max(N1), Min(N1), Distrb(N1); 11: PSet(N2) ← 从Area(N)中随机移除(p2 - q)个点的集合; 12: 根据PSet(N2)更新Count(N2), Max(N2), Min(N2), Distrb(N2); 13: 将N1和N2标记为“双”; 14: 对于TR中当前层标记为“单”的每个节点N 15: IF N比其邻居更密集 16: 移除高凸峰并更新N 17: level ← level - 1; 18: UNTIL (当前层的网格大小 > S 或 level = 0); 19: 通过移除剩余点更新当前层; 20: RETURN TR; ``` 例如，假设有一个数据集，其密度分布如图所示。设N1和N2是具有相同父节点的两个节点，原始算法计算得到Count(N1) = 750，Count(N2) = 331，而采用启发式方法后，结果更好，Count(N1) = 800，Count(N2) = 400。 ##### 1.2 实验评估 - **实验方法**：将ADenTS应用于美国森林覆盖类型的真实数据库和合成查询工作负载。在IBM 1.5GHz CPU、256MB DDR主内存、Windows XP和Microsoft Visual C++ 6.0环境下实现算法。生成3到5维的数据集，为每个投影数据集和每种支持的查询类型创建1000个平均选择性为1%的随机查询，形成查询工作负载。忽略数据点选择性小于0.1%的查询，因为小选择性会严重降低所有算法的有效性。通过相对误差来衡量准确性，其中MIN、MAX查询的相对误差计算公式为：RelativeError = |CorrectAnswer - ApproximatedAnswer| / |RangeofValueDimension|。 - **与MRA - Tree和GENHIST的比较**： - **支持的查询类型**：根据三种算法可支持的查询类型差异，将实验结果分为三组：仅ADenTS能回答的查询；ADenTS和MRA - Tree都能回答的查询；ADenTS和GE