基于聚类离散化的Dep-Miner函数依赖发现方法_仓敏.pdf

第 卷 第 期 年 月南京理工大学学报 收稿日期：修回日期：作者简介：仓敏（）女，硕士，工程师，主要研究方向：项目评价方法、技术经济，：。引文格式：仓敏，王静怡，吴霜，等 基于聚类离散化的 函数依赖发现方法 南京理工大学学报，（）：投稿网址：基于聚类离散化的 函数依赖发现方法仓 敏，王静怡，吴 霜，翟晓萌，程 曦，诸德律（国网江苏省电力有限公司 经济技术研究院，江苏 南京）摘 要：针对已有函数依赖发现方法直接应用于连续型数据时，易导致依赖关系挖掘失败的问题，该文基于已有 方法，提出基于等间隔离散化的（）和基于聚类离散化的（）函数依赖发现方法。通过数据离散化，将指标的连续型数据合理地转变为类别数据。实现基于类别数据的函数依赖发现，提升函数依赖发现能力。同时，对 中的部分定理给出了基于反证法和枚举法的通俗化证明。该文将提出的 和 与不带有任何离散化操作的原始 和 进行了实验对比。实验结果表明，该文的 和 方法将原始连续型数据转化为离散型分 类，挖 掘 出 了 更 多 潜 在 的 函 数 依 赖 关 系。同 时，的 性 能 要 优 于，解决了等间隔离散化存在的边界值问题。关键词：聚类；离散化；函数依赖发现；等间隔离散化；类别数据；反证法；枚举法；边界值问题中图分类号：文章编号：（）：，（，）：，（）（），总第 期仓 敏 王静怡 吴 霜 翟晓萌 程 曦 诸德律 基于聚类离散化的 函数依赖发现方法 ，：；挖掘复杂对象或系统包含的大量指标间关系有利于更好地开展问题诊断和系统评价，。例如对于电力系统，包含技术性、经济性、社会环境和可持续发展等各种类型的指标。挖掘这些指标间的复杂关系，是开展电网项目评价、配电网评价和输电网评价等不同类型评价的基础。挖掘乳腺疾病病理图像中细胞核的各种特征数据（半径、周长、纹理、凹度、对称性、分形维数等）之间的依赖关系，有利于开展疾病筛查和诊断。同时，如果将多个具有相关性的指标全部用于系统评价，既增加了评价的复杂性又影响评价的准确性，例如共线性会增加某些指标的作用。因此，挖掘出复杂对象指标间潜在的关系是各类诊断评价的基础。已有大部分指标间关系挖掘方法忽略了函数依赖关系。已有方法主要包含基于专家经验的定性分析法和基于模型的定量分析法。在指标较多时，单独使用专家经验，很容易忽略某些指标间的关系。已有定量分析法主要包含单因素方差分析、多因素方差分析、灰关联分析、主成份分析、主变量法、回归分析，、相关性分析，等。单因素方差分析主要通过衡量组内和组间方差的差异判断自变量的不同类别是否使得因变量均值有显著不同。而多因素方差分析是单因素方差分析的拓展，主要分析多个自变量单独或交互作用下对单个因变量影响的显著性，。单因素和多因素方差分析都要求数据分布满足正态性，应用范围受限。相关性分析，、灰关联分析主要考虑指标间数据的正负相关性、几何曲线相似度等。回归分析，的主要思想是建立多个自变量指标到 个因变量指标之间的线性或非线性回归模型。主成分分析主要目的是分离出线性不相关的指标，但是其得到的新指标通常是已有指标的线性组合，不具有显而易见的可解释性，主变量法则是直接找出原指标集合中相关性较小的 组指标。而函数依赖是另外 类描述自变量取相同值时因变量是否也取相同值的关系，即某些属性的值是否由其他单个或者多个属性值的组合唯一决定。例如电缆的截面积是否由电缆的规格型号唯一决定。函数依赖并不关心方差分析中考虑的自变量不同时，因变量值是否显著不同，也没有数据正态性约束，具有良好的适用性。正负相关和几何曲线相似指的是在所有数据范围内具有不变的相同变化趋势，或者不变的相反变化趋势。函数依赖关系则更加灵活，描述的是依赖与被依赖指标间任意的依赖关系，个指标在不同取值范围之间可以存在不同的离散函数依赖关系（不同变化趋势）。函数依赖关系也不需要建立回归分析中的确定性数学模型。因此，函数依赖关系描述的是指标间的一种更加灵活的多样化依赖关系。已有的函数依赖发现方法在处理连续型数据时容易遗漏潜在的函数依赖关系。、和 等是常见的函数依赖发现方法，其中 的特点是对内存需求较低。函数依赖发现可以被用于防止信息泄露，识别具有较高泄露风险的属性集合；函数依赖还可以被用于数据清洗，删除不符合依赖规则的数据记录。函数依赖也常被用于数据不一致性修复和数据库查询优化。函数依赖发现方法在判断属性值是否属于同一个等价类时基于数据是否完全相同进行判断。然而现实情况下，很多系统收集到的原始数据包含大量连续型指标，数据的细微差别会导致数据被分为不同类别，从南京理工大学学报第 卷第 期而无法挖掘出潜在的函数依赖关系。因此，本文基于传统 方法，提出基于数据离散化的函数依赖发现方法。该方法根据数据的分布情况，将连续型数据转变为合适的离散型类别，然后以各属性数据的类别作为 的输入，尽可能降低连续型数据的影响，提高函数依赖发现能力。本文主要贡献包括：提出基于等间隔离散 化 的 （，）和基于聚类离散化 的 （，）函数依赖发现方法，提升应对连续型数据时的函数依赖关系发现能力；在多个数据集上验证了本文方法在不同离散化等级数量和不同离散化属性数量情况下的实际性能；已有文献对传统 相关原理的证明主要基于超图理论，本文对 中涉及的定理采用更加通俗的反证法、枚举法进行了证明。问题描述设，是 个关系模式，是属性集，是数据集。和 为 的 个子集，为 的第 行，。当且仅当对于，存在 时，则称 函数决定，或 函数依赖于（记为）。称为函数依赖左部（，），称为函数依赖右部（，）。例如，表是电网系统项目投产线路信息表中的一部分（数据已经过离散化），属性集 电压等级（），线路总长度（），线路额定容量（），线路最大负荷时刻有功功率（），正向输送电量（），线路损耗电量（）。其中，是表 上当前数据的部分函数依赖。表 电网系统项目投产线路信息表序号 正如前文提到的，各种系统的原始数据通常包含一些连续型属性，传统的函数依赖发现方法直接采用连续型数据作为输入，容易遗漏一些潜在的函数依赖关系。例如，当电缆型号都是时，经济输送功率包含 和 种。如果采用原始数据，则不能得到电缆型号决定经济输送功率这样 个函数依赖关系。但是如果能把类似于 和 这样的数据合理地离散化到相同的类中，把连续型数据转化为离散型数据，则可以挖掘出潜在的依赖关系。不同的离散化结果决定了能挖掘出哪些依赖关系，这是因为从离散化后的数据集上挖掘出函数依赖关系是 个确定性问题。主要原因是函数依赖发现是通过计算 相同时 是否相同来确定的。数据一旦经过离散化，和 之间的关系就确定了，是否存在函数依赖关系也就确定了。也就是说能挖掘出哪些关系是由离散化方法的效果决定的，因此本文的主要目标是提出能够挖掘出更多潜在函数依赖关系的基于数据离散化的函数依赖发现方法。离散化 函数依赖发现针对连续型指标的离散化问题，本文首先提出了 个基于等间隔的数据离散化方法。该方法把连续型指标的数据按照等间隔分成不同的类，大部分只有细微差别的值将被分到同一个类中，从而在很大程度上解决了由于数据存在细微差别而导致的自变量相同、离散函数值不同的问题。但是在等间隔离散化的分类边界点处，即使函数值只有细微差别，也依然会被分到不同类中（边界值问题）。针对边界值问题，本文又提出了基于聚类的数据离散化方法。在基于聚类的离散化方法中，不再存在固定间隔的分类边界，而是根据数据本身的分布情况确定属于哪些类别。数据越接近则越有可能被分到相同类中，从而不受等间隔离散化中固定间隔边界的影响。本文将不同的数据离散化方法和传统 结合，分别提出了基于等间隔、聚类离散化的 和 函数依赖发现方法。与传统 的不同之处在于，基于离散化的 以聚类或等间隔离散化处理后数据的类别编号作为生成精简划分和最大等价类的输入，而传统 直接以原始实数型数据作为输入。如图 所示，提出的方法主要包含：总第 期仓 敏 王静怡 吴 霜 翟晓萌 程 曦 诸德律 基于聚类离散化的 函数依赖发现方法（）对数据进行等间隔或聚类离散化，将每个连续型属性列转换为离散化的数据列，数据列中相同颜色数据属于同一个类别，将原始实数型数据替换为对应类别的编号；（）生成精简划分和最大等价类；（）生成标识符集，用于表示每行数据出现在哪些属性的第几个等价类；（）通过计算标识符集合的交集，生成一致集；（）计算每个属性的最大集和补集，从数据集一致集中删除包含当前属性的元素并删除子集，则可以得到最大集，属性 的最大集代表不能决定 的最大属性集合，计算最大集每个元素相对于全体属性集合的补集，可以得到最大集补集；（）采用层次法计算最小函数依赖。图 离散化 架构图 数据离散化方法本文首先提出基于归一化和等间隔的离散化方法，降低连续型属性对函数依赖发现的影响。然后，针对等间隔离散化存在的边界值问题，提出了基于聚类的离散化方法。等间隔离散化为了进行等间隔离散化，首先对需要离散化的属性进行归一化。对于属性，归一化结果为（）（）（）式中：（）、（）表示属性 的最小、最大值。将 平均划分成 个等级。遵循左闭右开原则，将归一化后数据替换为所属等级的索引，就可以将相似的数据划分到同一个等级，尽量避免连续数据微小误差导致的无法挖掘出潜在函数依赖关系的问题。对数据进行离散化时，需要根据属性值的具体分布情况调整。以某电网项目投产线路信息表中 年“电网最大负荷时刻有功功率”属性部分数据记录为例，将 设为 时，每 为 个等级。表 第 列是归一化结果，第 列是等间隔离散化结果。表 电网最大负荷时刻有功功率属性离散化结果电网最大负荷时刻有功功率 归一化等间隔离散化聚类离散化 聚类离散化由于等间隔离散化在不同等级边缘容易导致具有相似值的记录被分为不同类别（边界值问题）。例如 个记录在同一个属性上的值为 和 时，有可能被分为 类，影响函数依赖发现。因此，本文提出基于 均值聚类的离散化方法。采用 均值聚类将每个属性上的值根据数据分布情况聚成不同的类。可以有效避免上述边界值问题。例如表 中加黑体的 行数据本身较为接近，但是在等间隔离散化时被分为 和 类，而在 均值聚类时被归为同一个类别。当在 行黑体数据上具有相同值的某个属性 作为，电网最大负荷时刻有功功率作为 时，如果采用等间隔离散化，由于右部数据不一致，依赖关系挖掘失败；反之，采用聚类离散化，则可以成功挖掘出该依赖关系。算法 是提出的基于聚类离散化的算法描述。算法 基于聚类的离散化方法输入：数据集，属性集 输出：离散化后数据 属性：属于连续型属性：根据该属性数据分布情况，采用观察法、南京理工大学学报第 卷第 期手肘法等选择离散化数量；随机选中 个数据作为质心；计算属性 的每个值距离 个质心的距离，并将每个值分类到最近质心的类；重新计算每个类的质心；质心和原来质心差别小于给定阈值：完成聚类；：跳转到步骤；对于每个属性，采用聚类后的类别编号替换原始数据，并返回。均值聚类的聚类数量对函数依赖发现的结果具有较大影响。例如，图 显示 个属性列 和 在限定不同最大聚类数量 时数据所属类别情况。从图 中可以看出，当聚类类别数量 为 时、属于 个类别，但是对应的、分属 个类别，因此不能得出 决定；此时由于聚类类别数量太小，把差别较大的、限定到了同一个类别；当 增加到 时，、被分到 个不同的类别，而对应的、也正好属于对应的 个类别，因此可以得出 决定；但是当 再继续增加到 时，和、和 虽然分别只有细微的差别，但是也被分到了不同的类别，使得 和、和分别属于相同类别，但是对应的 和、和类别不同，无法得出 决定。因此，聚类的数量 需要采用观察法、手肘法等确定。图 不同离散化等级数量下属性数据类别分布情况示例 函数依赖发现方法本节将结合表，以具体示例的方式介绍 函数依赖发现方法。同时，已有文献关于 相关定理的证明主要从超图角度展开，本文则基于反证法、枚举法给出了更加通俗的证明。生成精简划分数据库和最大等价类对于 个属性集，如果 行记录 和 在任意 个属性 上都存在相同的值，即，则称 和 在属性集 上是等价的。条数据记录 关于属性集 的等价类是在 中所有属性上都有相同值的所有数据记录的集合。如表 中，是关于属性