3.13 使用伪代码或您喜欢的编程语言提出以下算法：

（a）对于标称数据，基于给定模式中属性的不同值的个数，自动产生概念分层。

（b）对于数值数据，基于等宽划分规则，自动产生概念分层。

（c）对于数值数据，基于等额划分规则，自动产生概念分层。

（a）对于标称数据，基于给定模式中属性的不同值的个数，自动产生概念分层。

用于根据给定架构中属性的不同值的数量自动生成分类数据的概念层次结构的伪代码：

begin

// 数组以保存名称和属性的不同值计数

// 用于生成概念层次结构

array count_ary[];  // 属性值计数

string count_ary[].name; // 属性名称

int count_ary[].count; //唯一值计数

// 表示概念层次结构的数组（作为值的有序列表）

array concept_hierarchy[];

for each attribute ’A’ in schema {

    distinct_count = count distinct ’A’;

    insert (’A’, ’distinct_count’) into count_ary[];

}

//按count升序对ary []进行排序；

sort count_ary[] ascending by count;

for (i = 0; i < count_ary[].length; i++) {

// 生成概念层次结构节点

    concept_hierarchy[i] = count_ary[i].name;

}

//为了指示在概念层次结构中生成另一个级别所需的最小计数阈值，用户可以指定一个附加参数。

（b）对于数值数据，基于等宽划分规则，自动产生概念分层。

用于根据等额划分规则自动生成数字数据的概念层次结构的伪代码：

begin

// 用于生成概念层次结构的数值属性

string concept_attb;

// //表示概念层次结构（作为值的有序列表）

array concept_hierarchy[];

string concept_hierarchy[].name; // 属性名称

int concept_hierarchy[].max; // 箱的最大值

int concept_hierarchy[].min; // 箱的最小值

int concept_hierarchy[].mean; // 箱的平均值

int concept_hierarchy[].sum; // 箱的总和

int concept_hierarchy[].count; // 箱的元组计数

int range_min; // 用户指定的最小数据值

int range_max; // 用户指定的最大数据值

int step; // 用户指定的箱的宽度

int j=0;

// 初始化概念层次结构数组

for (i=0; i < range_max; i+=step) {

    concept_hierarchy[j].name = ’level_’ + j;

    concept_hierarchy[j].min = i;

    concept_hierarchy[j].max = i + step − 1;

    j++;

}

// 必要时初始化最终最大值

if (i >=range_max) {

    concept_hierarchy[j].max = i + step − 1;

}

// 通过增加适当的总和和计数值，将每个值分配给箱

for each tuple T in task relevant data set { //遍历目标数组

    int k=0;

    while (T.concept_attb > concept_hierarchy[k].max) {

        k++;

    }

    concept_hierarchy[k].sum += T.concept_attb; //每个箱的总和

    concept_hierarchy[k].count++; //每个箱的计数值

}

// 计算用于表示每个级别值的箱度量

// 在概念层次结构中

for （i=0; i < concept_hierarchy[].length; i++) {

    //计算每个箱的平均值

    concept_hierarchy[i].mean = concept_hierarchy[i].sum / concept_hierarchy[i].count;

} end

//用户可以针对有关数据的背景知识（即，将标签年轻人，中年人和老人分配给三级层次结构），为通过查看垃圾箱的最大值和最小值而生成的概念层次结构级别指定更有意义的名称 此外，可以实现一种替代的合并方法，例如通过合并模式进行平滑。

（c）对于数值数据，基于等额划分规则，自动产生概念分层。

用于根据等频划分规则自动生成数字数据的概念层次结构的伪代码：

begin

// 用于生成概念层次结构的数值属性

string concept_attb;

// //表示概念层次结构（作为值的有序列表）

array concept_hierarchy[];

string concept_hierarchy[].name; // 属性名称

int concept_hierarchy[].max; // 箱的最大值

int concept_hierarchy[].min; // 箱的最小值

int concept_hierarchy[].mean; // 箱的平均值

int concept_hierarchy[].sum; // 箱的总和

int concept_hierarchy[].count; // 箱的元组计数

int bin_depth; // 用户指定的箱深度

int range_max; // 用户指定的最大数据值

int step; // 用户指定的箱的宽度

// 初始化概念层次结构数组

for (i=0; i < (range max/bin depth); i++) {

    concept_hierarchy[j].name = ’level_’ + j;

    concept_hierarchy[j].min = 0;

    concept_hierarchy[j].max = 0;

}

//对与任务相关的数据集进行排序，对按概念attb升序排列的数据集进行排序；

int j=1;

int k=0;

// 通过增加适当的总和和计数值，将每个值分配给箱

//必要时的最小值和最大值

for each tuple T in task relevant data set {

    concept_hierarchy[k].sum += T.concept_attb; //每个箱的总和

    concept_hierarchy[k].count++; //每个箱的计数值

    //判断每个箱的最小值

    if (T.concept_attb <= concept_hierarchy[k].min) {

        concept_hierarchy[k].min = T.concept_attb;

    }

    //判断每个箱的最大值

    if (T.concept_attb >= concept_hierarchy[k].max) {

        concept_hierarchy[k].max = T.concept_attb;

    }; 

    j++;

    if (j > bin_depth) {

        k++;

        j=1;

    }

}

// 计算用于表示每个级别值的箱度量

// 在概念层次结构中

for （i=0; i < concept_hierarchy[].length; i++) {

    //计算每个箱的平均值

    concept_hierarchy[i].mean = concept_hierarchy[i].sum / concept_hierarchy[i].count;

} end

//该算法不会尝试在多个分箱中分配数据值，以消除最终分箱的实际深度与要实现的所需深度之间的任何差异。 用户可以再次为概念层次结构级别指定更有意义的名称，这些概念层次结构级别是通过查看有关数据背景知识的箱的最大值和最小值来生成的。

小结：

离散化和概念分层产生

通过将属性域划分为区间，离散化技术可以用来减少给定连续属性值的个数。区间的标号可以替代实际的数据值。如果使用基于判定树的分类挖掘方法，减少属性值的数量特别有好处。通常，这种方法是递归的，大量的时间花在每一步的数据排序上。因此，待排序的不同值越少，这种方法就应当越快。许多离散化技术都可以使用，以便提供属性值的分层或多维划分——概念分层

对于给定的数值属性，概念分层定义了该属性的一个离散化。通过收集并用较高层的概念（对

于年龄属性，如young, middle-age 和senior）替换较低层的概念（如，年龄的数值值），概念分层可以用来归约数据。通过这种泛化，尽管细节丢失了，但泛化后的数据更有意义、更容易解释，并且所需的空间比原数据少。在归约的数据上进行挖掘，与在大的、未泛化的数据上挖掘相比，所需的I/O 操作更少，并且更有效

对于用户或领域专家，人工地定义概念分层可能是一项令人乏味、耗时的任务。幸而，许多分层蕴涵在数据库模式中，并且可以在模式定义级定义。概念分层常常自动地产生，或根据数据分布的统计分析动态地加以提炼。

数值属性的概念分层可以根据数据分布分析自动地构造。五种数值概念分层产生方法：分

箱、直方图分析、聚类分析、基于熵的离散化和通过“自然划分”的数据分段。