2þ¼ ðÞ阵列10（2021）100060关于无限1-齐次二元信息系统上决策树的深度米哈伊尔·莫什科夫计算机、电气和数学科学与工程系，阿卜杜拉国王科技大学（KAUST），Thuwal，23955-6900，沙特阿拉伯A R T I C L E I N F O关键词：信息系统决策树A B S T R A C T在本文中，我们研究了决策树，它解决了无限信息系统的一个特定子类上定义的问题，即：1-齐次二进制信息系统。证明了决策树的最小深度（定义为问题描述中属性数量的函数）在最坏的情况下对于该类中的每个信息系统都是几何或线性增长的我们考虑无限1-齐次二进制信息系统的一些例子，包括一个密切相关的决策树构造的CART算法。1. 介绍决策树已被广泛应用于解决知识表示、分类、组合优化、计算几何等领域的问题，例如参考文献。[7、17、21]。因此，决策树的时间复杂度和用于其优化的算法也已被广泛地研究参考文献[7，8，14，17，21]，包括可以为中型决策表构建最佳决策树的算法[1大多数与决策树相关的结果都是针对有限属性集上的决策树，实际上是针对决策表。然而，无限属性集上的决策树，特别是线性[10，15，17]，拟线性[17]，代数决策树[12，23]以及与之相关的代数计算树[5，11]已经作为组合优化和计算几何中的算法进行了深入研究。特别地，对于n≥4个城市的旅行商问题，存在一个深度至多为n7=2的线性决策树来解决这个问题[15]。有两种方法来研究无限属性集上的决策树：局部方法，其中决策树仅使用来自问题描述的属性，以及全局方法，其中决策树使用来自所考虑的有限属性集中的任意属性[3，17，18]。我们在本文中考虑的结果是在全球性的方法框架，一个更复杂的计算要求的任务比本地的方法。然而，它通常可以构建更好的决策树。在我们以前对决策树全局方法的研究中[16]，我们研究了任意k值属性的无限集合，它们被解释为信息系统U A;F，其中A是对象（输入）的无限集合，F是属性的无限集合，每个属性是从A到集合f0; 1;...; k - 1 g，k ≥ 2的U上的问题的概念定义如下。属性f1;...; f n从F划分的集合A到domains，其中这些属性的值是常数。域被标记为决策。对于任意对象A，需要识别附加到包含A的域的决策。 为了解决这个问题，使用具有来自F的属性的决策树。 对于一个任意的无限信息系统，在最坏的情况下，决策树的最小深度（作为问题描述中属性数量的函数）要么从下到上由对数1 ε的幂来限制，其中ε是一个任意的正常数或线性增长。附加的ε并不能保证所考虑的决策树中的节点数量是问题描述中的属性数量的多项式有趣的是，在决策树的最小深度的上界中没有附加常数ε的情况下，描述无限信息系统的类别一个著名的例子是信息系统中的超平面，其中R是实数的集合，N是自然数的集合，Ld是与Rd中的超平面对应的三值属性的集合[10]。其他例子可以在参考文献中找到[17 ]第10段。在本文中，我们考虑这样的另一类：无限1-齐次二进制信息系统U<$A;F<$。“二进制“一词意味着k 1/4 2，即，来自F的所有属性具有来自集合f0; 1g的值。“1-齐次”一词的电子邮件地址：mikhail. kaust.edu.sa。https://doi.org/10.1016/j.array.2021.100060接收日期：2020年7月9日;接收日期：2021年3月10日;接受日期：2021年3月22日2021年4月1日网上发售2590-0056/©2021由Elsevier Inc.发布这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表阵列期刊主页：www.elsevier.com/journals/array/2590-0056/open-access-journalM. 莫什科夫阵列10（2021）1000602ð Þ ¼g/ml22ð Þð Þ2¼1/2fg¼ ðÞ¼ ðÞ一致方程组ff1x1 δ1;...; f n x 1 δ n g，f 1 ;...; f n ; f 2 F和δ 1 ;...; δ n ; δ 2 f 0 ; 1 g的结果，则存在来自所考虑系统的方程fi x 1 δ i，使得fi x 1 δ i和δ δ i的结果。我们证明了，对于每个无限1-齐次二进制信息系统，在最坏的情况下，决策树的最小深度（作为问题描述中属性数量的函数）以几何方式或线性方式增长。我们定义了无限1-齐次二进制信息系统U<$A;F<$A的属性集F上的偏序：对任意f1;f22F，f1f2当且仅当方程f2<$x<$<$0是方程f1x0的一个结果。设F中的反链的基数从上到下是无然后，我们证明，在最坏的情况下，决策树的最小深度设F中反链的基数是上有界的在这种情况下，通过Dilworth在每个链中，任何两个属性都是可比较的。为了从一个链中找到有限个属性的值，我们可以使用类似于二分搜索算法的方法。我们证明了，在最坏的情况下，决策树的最小深度在问题的描述中的属性的数量上呈几何增长我们在第3节考虑无限1-齐次二元信息系统的例子。 其中最有趣的是信息系统VnRn; Fn，其中Fn是对应于Rn中的超平面的属性集，由形式为xib的方程给出，其中i1;...; n和bR。由CART [7]构造的决策树使用来自该系统的属性，用于不具有分类属性和具有n个连续属性的决策表在决策树的工作过程中，我们计算一些属性的值，并得到“属性值”形式的方程。然后，我们得出结论的基础上获得的方程和方程的结果，他们的决定。本文的主要创新之处是考虑了后果推理的机制我们可以像本文一样研究具有特殊推理机制的信息系统（另见结论中描述的另一种机制）。我们可以限制推理机制，只考虑由一个方程或最多两个方程导出的结果，等等。本文在对结果推理机制研究的基础上，提出了一个与决策树相关的新的研究方向本文的其余部分组织如下。在第2节中，我们讨论了主要的概念。在第3节中，我们考虑无限1-齐次二进制信息系统的例子第四节研究了有限1-齐次二元信息系统上决策树的深度。第五节是简短的结论。2. 主要概念在本节中，我们定义了主要概念：有限1-齐次二元信息系统，此类系统上的问题，解决此问题的决策树，与信息系统相关的Shannon函数，以及信息系统的宽度。定义1.一个无限二进制信息系统[20]是一个对U<$A;F<$，其中A是一个无限集，F是一个无限属性集，每个属性都是从A到f0; 1g的非常数函数。定义2. 关于信息系统U的问题是元组zv;f;其中终端节点用来自N的数字标记，非终端节点用来自F的属性标记。 每个非终结节点都有两条左边，分别用数字0和1标记。对于给定的a A，树Γ以如下方式工作我们从根开始如果所考虑的节点是一个终端节点，那么从N开始的附加到这个节点的数是Γ功的结果假设所考虑的节点用属性f F标记。然后，我们计算值f a，并沿着离开所考虑的节点的边传递，并标记为数字fa。定义4.我们可以说决策树Γ解决了问题z如果对任何a 2 A，Γ功的结果等于z<$a<$。我们用hr表示决策树r的深度，它等于r中从根到终端节点的路径的最大长度我们用hU z表示解决问题z的U上的决策树的最小深度。第五章. 功能SUn最大值fh U z：z 2PU; dimzn g定义在集合N上的函数称为信息系统U的香农函数。函数SU描述了决策树的最小深度在最坏的情况下，解决问题的能力随着问题维度的增长而增长设f1;我们会说ff1xδ1;是U上的方程组这个系统是相容的，如果它至少有一个解来自A。方程f∈x∈δ是相容系统（1）的一个推论，如果对（1）的任意解a2A，f∈a∈δ.第六章.我们说U是1-齐次的，如果对于U上的任何相容方程组（1）和它的任何推论fxδ，存在来自（1）的方程fixδi，使得fxδ是系统fixδig（实际上，fxδ是方程fixδi）和δiδ的推论。设f1，f22F.注意，当且仅当方程f2x1是方程f1x 1的结果时，方程f 1x0是方程f 2 x0的结果定义7.我们说集合F的子集G是独立的，如果没有不同的属性f1;f22G使得方程f1x^0是方程f2x^^0的结果。定义8.我们说集合F具有无限宽，如果对于任意自然数m，存在集合F的一个子集，其基数等于m，并且是一个独立的集合。否则，F的宽度是有限的，并且等于F的子集的最大基数，这是一个独立集。信息系统U A;F的宽度是集合F的宽度。3. 无限1-齐次二进制信息系统的例子在本节中，我们考虑无限1-齐次二进制信息系统的四个例子在前三种情况下，属性具有清晰的几何解释，这使示例更加清晰。1N例1. 表示U01/2R2;F01，其中F0是无限属性集。其中n2N，f1;对于给定的a 2 A，需要识别值za vf1a;...; f n a。数字dim z ¼n将被称为问题z的维数。我们用P<$U <$来表示U上的问题集。解决问题，我们使用U上的决策树。定义3.U上的决策树Γ是一个有向树，其根在但对应于R2中所有垂直直线。对于每一条垂直直线，对应的属性在直线上和直线左边的点上的值为0，而在直线右边的点上的值为1（见图1）。①的人。很容易证明U0是一个无限的1-齐次二进制信息系统。这个系统的宽度等于1。M. 莫什科夫阵列10（2021）1000603nb;tFGb;t¼ ðÞ;2<<1个;如果at>b：是一致的，但方程组图1.一、 信息系统U0.实施例2. 设n≥2为自然数。对于b2R和t2 f1;f n a;.; a。0的整数倍;如果at≤b;图3. 信息系统W.4. Shannon函数下面的定理给出了香农函数的线性和对数增长依赖于所考虑的无限1-齐次二进制信息系统的宽度的准则b; t1N1个;如果 at> b：定理1.设U^A;F^是无限1-齐次二元信息，记为Vn <$$>Rn;Fn<$，其中Fn<$f fn：b2 R;t2 f 1;图2示出了信息系统V2。 我们可以证明V n是一个无限1-齐次二元信息系统。这个系统的宽度等于n。实施例3.让我们考虑两个无限系统的同心圆（见图。 3）。对于每个圆圈，我们对应一个定义在R2上的属性，其值为0; 1。对应于左侧系统中的圆c的属性在圆c上和圆c内的值为0（见图11）。 3）。对应于右侧系统中的圆c的属性在圆c外的值为0（见图2）。 3）。我们用Q表示对应于左系统和右系统的所有圆的属性集表示W. R2;Q.我们可以证明W是无限1-齐次二元信息系统。这个系统的宽度等于1。实施例4.记RN为所有序列的集合，其中an2R对于每个n2N.对于b2R和t2N，我们定义一个属性（一个函数）系统。(a) 如果U有无限宽，则对于任何自然数n，SU n n。(b) 如果U有有限的宽度，则S U nθ。P屋顶。（a）设U有无限宽，n是自然数，zv;f1;是U上的一个问题，使得f1;现在我们证明hU≥n。为此，我们证明，对于任何元组<$δ1;我们假设相反的情况：存在一个元组<$δ1;因为函数f1是非常数的，所以方程组ff1δ1g是相容的。因此，存在fbt从RN到f0; 1g如下：对于任意的n∈n∈2RN，i2 f1;;fbtan2N快看。0的整数倍;如果at≤b;ff1xδ1;表示VN<$RN;FN<$，其中FN<$f fb;t：b2R;t2 Ng。人们可以证明fx δ fx δf x δVN是一个无限1-齐次二进制信息系统。这f1磅/升;...; i磅/ 升i ; i磅/升1磅/升i磅系统具有无限宽度。图二、 信息系统V2.不一致。因此，方程fi1x1：δi1是系统（2）的结论 因为U是1-齐次的，所以存在j 2 f 1;...; i g使 得fi ：δ i δ j 和 ：δ i δ j的 结 果。这意味着集合ff1;因此，我们得到函数z有2n个不同的值。设Γ是U上的决策树，求解问题z。 则Γ至少包含2n个终端节点。 可以证明，在Γ中的终端节点的数目至多为2 h<$Γ。从这里可 以 得 出 ， Γ 的 深 度 至 少 是 n 。 因 此 ， hU≥n 且 SU≥n 。 显 然 ，SU<$n<$≤n。因此，SUnn。(b)设U有有限宽度m。我们用下面的方法定义集合F上的二元关系<。对任何f1;f22F，f1f2当且仅当方程f2x0是方程f1x0的推论 我们可以证明这个关系<是自反的（对于任何f2 F，f
下载后可阅读完整内容，剩余1页未读，立即下载
