没有合适的资源?快使用搜索试试~ 我知道了~
基尼杂质最小化问题的NP完全性与近似性
可在www.sciencedirect.com在线获取理论计算机科学电子笔记346(2019)567-576www.elsevier.com/locate/entcsGini杂质最小化问题的NP完全性和近似性算法通过连接与k-均值问题Eduardo Laber,1Lucas Murtinho2PUC-Rio巴西里约热内卢摘要在决策树构造中,基尼不纯性是一种非常流行的属性选择准则。在寻找具有最小加权基尼杂质(PMWGP)的分区的问题中,在构造决策树期间所面临的问题中,一组向量必须被划分为k个不同的聚类,使得分区我们表明,PMWGP是APX硬的任意k,并承认一个随机PTAS时,集群的数量是固定的。 这些结果大大提高了目前对这个问题的认识。 关键的想法为了得到这些结果,我们探索了PMWGP和几何k-均值聚类问题之间的联系。保留字:杂质,基尼系数,k-均值,NP-完全性,近似。1引言决策树和随机森林是分类任务中最流行的方法之一众所周知,决策树,特别是小的决策树,很容易解释,而随机森林通常会产生更稳定/准确的分类。在构造这些结构的过程中,一个关键的决策是选择用于在每个节点处分支的属性。这种选择的标准方法是评估每个属性生成“纯”分区的能力,即每个分支相对于其示例的类分布非常均匀的分区。为了测量每个分支有多不纯,经常采取措施1电子邮件地址:laber@inf.puc-rio.br2电子邮件:lucas. gmail.comhttps://doi.org/10.1016/j.entcs.2019.08.0501571-0661/© 2019作者。出版社:Elsevier B.V.这是CC BY许可下的开放获取文章(http://creativecommons.org/licenses/by/4.0/)。568E. 拉伯湖Murtinho/理论计算机科学电子笔记346(2019)567DΣΣ成本(P)=v−ciKM1−ui=1 u1杂质测度映射向量u =(u1,...,ud),计算我们在节点(分支)中有多少个每个类的示例,并将其转换为非负标量3。可以说,最经典的杂质度量之一是基尼杂质i基尼,它测量当一个对象以概率u i被分配到类i时错误分类的概率。它被定义为:乌鲁河科鲁岛乌伊河Gini杂质在CART包中用于分类和回归决策树[3]。因此,重要的是要了解找到最佳分区w.r.t.问题的复杂性。基尼不纯,并为这项任务建立数学模型和算法问题定义。 对于所有分量都非负的向量v,加权基尼杂质Gini(v)定义为Gini(v)=v1·iGini(v)。假设A是可以取n个可能值a1,...,一个;最小加权基尼系数k元划分问题(k-PMWGP)可以抽象地描述如下.我们给出一个n个非空向量V∈Zd的集合,其中第j个向量的第i个分量计数第i类中属性A具有值aj的示例的数量。我们的目标是找到一个分区P的V到k组,以尽量减少加权基尼杂质的总和K基尼系数(P)=i=1基尼.v∈Viv.(一)从最优性的角度来看,与上述问题等价的一个问题(但从近似的角度来看是不同的)是找到将V划分为k个组的划分P,基尼系数(P)−基尼系数(v)。(二)v∈V利用基尼系数的非负性质,可以证明上述表达式总是非负的。关于目标(2)的α-近似意味着关于目标(1)的α-近似,但反过来不一定正确,因此关于目标(2)的近似更强[7]。为了正确解释我们的工作,我们将回顾经典k均值聚类的定义。在几何k-均值问题中,我们给定一组向量V∈Rd,目标是找到V的一个划分P,将V划分为k个组V1,.,Vk和一组k个中心c1,...,ck在Rd中,使得K22i=1v∈Vi[3]在最初的定义中,杂质测度将概率向量映射为非负标量。i基尼(u)=.E. 拉伯湖Murtinho/理论计算机科学电子笔记346(2019)5675692被最小化。众所周知,如果你 是一组向量,那么向量c,v∈U(v−c)v∈U (五)|U|.我们的成果。我们证明了PMWGP对任意k都是APX-困难的,并且当聚类数k固定时,它允许一个随机PTAS这些结果大大提高了目前对这个问题的认识获得这些结果的关键思想是探索PMWGP和k均值聚类问题之间的联系。事实上,PMWGP的硬度依赖于减少从顶点覆盖问题在三角形的自由图的k-均值聚类问题,由于Awasthi等人。[2]的文件。此外,我们的随机PTASPMWGP是一个简单的适应随机PTAS的k-means问题库马尔等人。[9]并由Ackermann et al.进一步探索[1]的文件。相关工作。 已经有理论研究的方法来计算最好的分裂有效的杂质措施,如基尼杂质。为d=k= 2,Breiman[3]提出了一个简单的算法,该算法在O(nlogn)时间内找到包含Gini的某类中杂质测度的最佳二进制划分。该算法的正确性依赖于一个定理,该定理也在[3]中得到证明,该定理在Chou[5],Burshtein et al.[4]和Coppermith等人[7]。基本上,这些定理提供了具有最小杂质的划分的必要条件,并且可以用于限制需要考虑的划分的集合。我们在这里探讨的基尼系数和k-均值采用的平方l2距离之间的联系,在Chou的附录中提到[5]。本文所呈现的结果属于第一作者及其合作者的研究项目,其目标是从近似算法的角度更好地理解基于杂质测量/Bregman分歧的聚类。在[10]中,提出了新的分裂过程,该过程可证明地实现了基于包括基尼杂质和熵杂质的在文献[6]中,给出了更一般的k元划分问题中同一测度族的逼近算法对于欧几里德k均值问题,大量文献是可用的,并且从近似算法的角度很好地理解该问题,因为最佳可用近似因子与由硬度结果给出的阈值之间的差距很小(参见[2]和其中的参考文献纸组织。 在第二节中,我们提出了最小加权基尼系数问题(PMWGP)和k-均值聚类问题之间的联系。此外,我们使用这些连接来证明PMWGP的硬度。第3节分析了一个算法,对于固定的k和恒定的概率,在多项式时间内提供了PMWGP的(1 +n)-近似。我们在结论部分讨论了结果并提出了进一步的研究方向570E. 拉伯湖Murtinho/理论计算机科学电子笔记346(2019)567DDD2-是的.Σv∈Xv∈XLv∈X21−u1− vui−L×n−ui+L=L×−D2基尼系数最小化和k均值聚类之间的联系在本节中,我们认为,以下连接之间的k-PMWGP和k-表示问题保持:命题2.1设V是k-均值的一个实例,其中所有向量具有相同的l1范数。如果P是k -均值的实例V的最优划分,则P也是k -PMWGP的实例V的最优划分。命题2.2存在一个伪多项式时间约简,PMWGP的几何k均值问题。建立这两个命题的关键观察是下面的引理。引理2.3设X是n个向量的集合,所有向量的l1范数都等于L。然后,吉尼。 vΣǁv − cǁ2Σ,其中c是X中向量集的质心。是的。 设u=v∈Xv,d e是X中向量的维数. 我们有一个有一个好吧 你好。v∈Xi=1u乌伊河1好吧vi.v∈Xi=1vvi1- 是的(ui)2个月。(vi)2个月另一方面,在一项研究中,=i=1ui−L×nD−i=1v∈Xvi−L。Σǁv−cǁ2=ΣΣ(vi−ci)2.v∈X i=1v∈X因此,它表面上表明,对于任何i,(ui)2ui−L×n−vi−v∈X(vi)2L=1个Lv∈X(vi−ci) .(三)(3)的左边等于(ui)2n∈X(vi)Σ基尼系数(u)−基尼(v)=基尼系数1−v(vi).2ΣE. 拉伯湖Murtinho/理论计算机科学电子笔记346(2019)5675711 .一、Σv∈X2(ui)2n572E. 拉伯湖Murtinho/理论计算机科学电子笔记346(2019)567ΣLΣ我我我我v∈Xv∈Xv∈X此外,(3)的右侧等于1×。(v)2− 2 c1=L× .v∈X(vi)2(ui)22 +nn(ui)2n21=L× .v∈X(vi)2−(ui)2、n这就建立了引理。Q命题2.1是引理2.3的直接结果,因为它意味着,对于V的所有k-划分P,1基尼系数(P)=L·成本KM(P) +基尼系数(五)。v∈V关于命题2.2,设V是k-PMWGP的一个实例,VJ是从V得到的k-均值的实例,如下:对于每个向量v ∈ V,我们将向量v j = v /v/v的精确的<$v<$1个拷贝添加到实例集V j。使用引理2.3以及在k-均值相同向量的任何最优解中都在同一分区中的事实,我们得出结论,V和v∈VGini(v)使V j注意,实例VJ是在伪多项式时间内从V从命题2.1和[2]中建立的几何k-均值的硬度,我们得到:定理2.4最小加权基尼分割问题(PMWGP)对于目标(1)是NP完全的,对于目标(2)是APX困难的。证据[2]的定理1.1指出存在一个常数λ,使得将k-均值问题近似到比(1 +λ)更好的因子是NP困难的。在用于证明[2]中的定理的例子中,所有向量的l1范数为2;从我们的引理2.3可以得出,目标(2)和k-均值的目标函数恰好相差2倍。目标(1)的NP完全性是因为目标(1)和目标(2)通过一个可加常数而不同。Q3近似最优基尼分配命题2.2给出的约简使我们能够得到具有可证明逼近因子的k-PMWGP作为一个例子,我们讨论了如何获得一个随机PTAS为k-PMWGP关于目标函数(2)时,k是固定的。为此,我们运行Kumar等人提出的k均值问题的随机PTAS实例VJ。[9]。算法1(CLUSTER)是[1]的图1所示算法的略微修改版本。在下文中,我们将解释算法1是如何工作的,以及我们如何使其适应我们的目的。然而,我们没有详细分析它的近似,因为它是没有必要建立我们的结果。我们建议读者参考[1],以获得完整的ΣΣ−E. 拉伯湖Murtinho/理论计算机科学电子笔记346(2019)567573αγδ8:C ←,v∈S′ v |S·J·S,|SJ|= 1,//中值候选集2在[9]中提出的PTAS介绍。本演示文稿包括其近似因子的简化证明以及如何推广到其他目标函数的讨论。算法1CLUSTER(R,l,Cluster)输入:R:剩余输入点的集合l:要找到的中值的数量C:已经找到的中值的集合1:如果l=0,则返回C2:其他3:如果l≥|R|然后返回CR4:其他5:C(c)={}6:/* 采样阶段 */7:从R中采样大小为2的多重集S|S′|γδ9:对于所有c∈C,10:C(c)←C(c)C光泽(R,l−1,C{c})11:/* 修剪阶段 */12:设N为具有1|R|极小点p∈ R w.r.t.最小值||p−c||2c∈C213:C(c)←C(c)C光泽(R\N,l,C)14:以最小代价返回C∈C(c)C LUSTER将待聚类的剩余对象的集合R、待找到的中值的数量l以及已找到的中值的集合Cloud作为输入。(初始y,R=V,l=k,C=k。)此外,它还使用了3个参数:γ,用于控制近似因子;δ,用于控制在近似方面返回一个好的集群;以及α,一个影响运行时间和近似因子的正常数。CLUSTER返回包含k个中位数的集合Cluster。V的点然后可以根据它们在集合C中的最接近的点被聚类。如果没有找到中位数(l= 0),则算法返回集合C.在另一种基本情况下,当l≥|R|R中的点的位置成为一个新的中值。否则,该算法考虑下面给出的策略(i)和(ii)来对R中的点进行聚类,并返回由以下公式构建的那些聚类中的最佳聚类:这些战略。(i) 该算法建立了一个集合C,其中包含S的所有大小为1/γδ的子集的质心,其中S是R的大小为2/αγδ的随机多集。将每个质心c∈C分别加到C∈ C上,|C|递归调用参数为(R,l−1,Cc)。 该策略对应于第7- 10行。574E. 拉伯湖Murtinho/理论计算机科学电子笔记346(2019)567˜⎩4K−拉吉ΣO(ii) 出租人建立一个集合N,|R|R中 最接近C中中位数的点。然后,使用参数(R\N,l,C)递归调用该过程。该策略对应于第12-13行。因此,我们可以将CLUSTER调用的次数定义为:T的(|R|,l)=0如果l = 0,则为1,或者|R| ≤ lC++=(|R|, l−1)+T(|R|/2,l)+1,否则(四)其中c是集合C的基数。一个重要的事实是,c是常数,2相对于|V|和k,因为它只依赖于γ,δ和α。事 实 上, k1,并假设引理对所有WJ,kJ成立,其中WJ 0和固定的k,C簇在多项式时间内以≥ 1 − δ的概率提供了k −PMWGP的(1 + δ)-近似。证据直接来自引理3.1和3.2 :因为对于固定的k,对算法1的调用最多为O(nk),每次执行最多O(nlgn)操作,所以CLUSTER(VJ,k,{})的总运行时间为O(nk+1lgn)。Q四、结论我们在本文中展示了如何最小化分区的基尼不纯性和几何k均值问题之间的联系,提供了新的工具,以更好地理解和处理前一个问题。特别是,这些连接使我们能够建立PMWGP的硬度结果,并找到一个多项式时间,概率(1+1)近似算法的问题时,k是固定的。一个自然的问题是,其他算法是否可以通过这里提出的连接来适应PMWGP。由于从PMWGP实例构建的k-均值实例的大小可以是PMWGP实例大小的伪多项式,因此可能的情况是,某些算法在通过该连接使用时不保持多项式,或者k-均值问题的某些已知结果不适用于PMWGP。作为一个例子,[8]的算法,k-均值问题的常数近似算法,依赖于基数为O(n)的一组n目前尚不清楚上面提出的伪多项式变换是否允许PMWGP通过该算法在多项式时间内(近似)求解引用[1] A ckermann,M. R., J. B l?omer和C. 孙文,度量和非度量数据集的聚类分析,北京: 计算机 科学出版社。Algorithms6(2010),pp.59:1-59:26。URLhttp://doi.acm.org/10.1145/1824777.1824779[2] Awasthi,P.,M.恰里卡尔河Krishnaswamy和A. K. Sinop,欧氏k-均值,在:L。Arge和J.Pach,编辑,第31届计算几何国际研讨会,莱布尼茨国际信息学会议记录(LIPIcs)34(2015),pp.754- 767。URLhttp://drops.dagstuhl.de/opus/volltexte/2015/5117[3] 布莱曼湖,“Classification and regression trees,” Routledge, 网址https://www.taylorfrancis.com/books/9781351460491E. 拉伯湖Murtinho/理论计算机科学电子笔记346(2019)567579[4] Burshtein,D.,诉Della Pietra,D.Kanevsky,A.Nadas等人,最小杂质分配,《统计年鉴》20(1992),pp.1637-1646年。URLhttps://projecteuclid.org/euclid.aos/1176348789[5] Chou,P.一、分类和回归树的最优划分,IEEE模式分析机器智能交易(1991),pp。340-354URLhttps://www.computer.org/csdl/trans/tp/1991/04/i0340.pdf[6] Cicalese , F. 和 E. Laber , Approximationalgorithmsforclusteringviaweightedimpuritymeasures,arXiv preprint arXiv:1807.05241(2018).URLhttps://arxiv.org/abs/1807.05241[7] Coppersmith,D.,S. J.Hong和J.R. Hosking,Partitioning nominal attributes in decision trees,DataMining and Knowledge Discovery3(1999),pp.197-217URLhttps://link.springer.com/article/10.1023/A:1009869804967[8] Kanungo,T.,D. M.芒特,N. S.内塔尼亚胡角D.皮亚特科河Silverman和A. Y. Wu,A local searchapproximation algorithm for k-means clustering,Computational Geometry28(2004),pp.89比112URLhttps://www.sciencedirect.com/science/article/pii/S0925772104000215[9] 库马尔,A.,Y. Sabharwal和S. Sen,A simple linear time(1+ n)-approximation algorithm for k-means clustering in any dimensions,in:Foundations of Computer Science,2004。诉讼第45届IEEE年度研讨会,IEEE,2004年,pp。454-462.URLhttps://ieeexplore.ieee.org/abstract/document/1366265[10] Laber,E.美国,M. Molinaro和F. A. M. Pereira,具有近似最小杂质的,在:国际机器学习会议,2018年,pp.2860-2868。URLhttp://proceedings.mlr.press/v80/laber18a.html
下载后可阅读完整内容,剩余1页未读,立即下载
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功