Incompatibility graphs in data mining

doi:10.1007/s11750-026-00717-6

2026-01-01

Endre Boros

Federica Ricca *

Vincenzo Spinelli

DOI：10.1007/s11750-026-00717-6

原文链接

原文求助

摘要

En 中文

本文提出了一类新的“不相容图”(IG)用于数据挖掘。它们被用于监督学习中的盒聚类问题，其中实例由一个训练集的观测值给出，分类为正例和负例，目标是预测任何新观测值的类别。盒聚类算法输出一组对应于标记超矩形（同质盒子）的簇。在IG中，顶点对应正例观测值（R-d空间中的点），当两个顶点无法被聚在一起时，即包含它们的任何盒子也包含一些负例点时，它们之间存在边。本文形式化了IG的概念，并解释了如何使用不相容图对盒聚类问题进行建模。我们还从理论角度证明IG具有内在意义，因为可以证明其与其他已知图类的关系，例如可比较图。特别地，对于平面上的IG，我们证明了其强结构性质，并提供了一个禁止诱导子图的列表。此外，我们表明不相容图可用于解决与盒聚类相关的某些关键问题，如“最大盒子”和“盒子最小覆盖”。事实上，我们证明这两个问题可以分别表述为在不相容图上的顶点填充和顶点着色问题，并且前者可以在多项式时间内解决，而对于两个重要的实例子类，后者也可以在多项式时间内解决。

Keyword:

Box clustering

Incompatibility graphs

Forbidden graphs

Vertex packing

Vertex coloring