（计算机科学与技术专业论文）基于非平衡数据的适应性采样集成分类器的研究.pdf

i f i | | 川| j i i i | | i i i f | i | i | | i j 舢 y 171812 2 a n a d a p t i v es a m p l i n ge n s e m b l e c l a s s i f i e rf o rl e a r n i n g f r o mi m b a l a n c e dd a t as e t s s p e c i a l t y ：一c o m p u t e ra p p l i e dt e c h n o l o g y m a s t e r d e g r e ec a n d i d a t e ：j o ng e i l e ro r d o n e zp a n t o i a s u p e r v i s o r ： 里芏q l ih q 堕g s c h o o lo fi n f o r m a t i o ns c i e n c ea n de n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h a ，h u n a n ，p r c h i n a 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的 同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：冱薹丝丝笙每乡_ 日期：垒生年丛l 月兰生日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学 位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以 采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络 向社会公众提供信息服务。 作者签名：石益蟛师签名丝日期：g , , o 盟月丝日 a b s t r a c t n o w a d a y se v e r yd a yd a t ai sa v a i l a b l ef o re x t r a c t i n ga n da n a l y s i s ，t h eu s e o fd a t am i n i n gt e c h n i q u e sh a v es h o w ng r e a ts u c c e s si nm a n yr e a l w o r l d a p p l i c a t i o n s ，c l a s s i f i c a t i o n m o d e l s h a v e b e e nu s e dw i d e l yo nm a n y a p p l i c a t i o n sa so i ls p l i td e t e c t i o n ，c r e d i tc a r dd e t e c t i o n ，m e d i c a ld i a g n o s i s ，a s w e l lo t h e r s t h eo v e r a l l o b j e c t i v eo ft h i sr e s e a r c hi st oa n a l y z eat e c h n i q u et o i n c r e a s et h e a c c u r a c y o fc l a s s i f i e r sb u i l tf r o mi m b a l a n c e dd a t a s e t s ， i m b a l a n c e dd a t a s e t sw h e r eo n ec l a s si sr e p r e s e n t e db yal a r g e rn u m b e ro f i n s t a n c e st h a no t h e rc l a s s e sa r ec o m m o no nd a t am i n i n gp r o b l e m s t r a d i t i o n a lm a c h i n e1 e a r n i n gi ss e n s i t i v et ot h e s et y p e so fd a t aa n dt e n d st o v a l u ep r e d o m i n a n tc l a s s e sa n di g n o r et h el o w e rf r e q u e n c yc a s e s m o d e l s g e n e r a t e df o rd a t a b a s ew i t hi m b a l a n c e dc l a s st e n dt og e n e r a t el o wa c c u r a c y f o rm i n o r i t yc l a s s e s ，i nm a n yc a s e st h i sc l a s s e sc a nb et h em o s ti n t e r e s tc l a s s i no r d e rt o c o p ew i t h t h ei m b a l a n c e dp r o b l e ma ne n s e m b l e b a s e a l g o r i t h mi sp r e s e n t e db yc r e a t i n gn e wb a l a n c e dt r a i n i n gs e t sw i t ha l lt h e m i n o r i t yc l a s sa n du n d e r s a m p l i n gm a j o r i t yc l a s s i ne a c hr o u n d ，a l g o r i t h m i d e n t i f i e dh a r de x a m p l e so nm a j o r i t yc l a s sa n dg e n e r a t e ds y n t h e t i ce x a m p l e s f o rt h en e x tr o u n d f o re a c ht r a i n i n gs e taw e a kl e a r n e ra sb a s ec l a s s i f i e ri s u s e d f i n a lp r e d i c t i o n sw i l lb ea c h i e v e db yc a s t i n gam a j o r i t yv o t e e - a d s a m p l i n g i se v a l u a t e du s i n g6d a t a s e t sf r o mu c ir e p o s i t o r y ，t a k i n g o nc o n s i d e r a t i o nf m e a s u r e s ，g - m e a n ，o v e r a l la c c u r a c y ，a n da u c ( a r e a u n d e rr o cc u r v e ) a n dc o m p a r e dw i t hs o m e k n o w n a l g o r i t h m s e x p e r i m e n t a lr e s u l t sd e m o n s t r a t e t h ee f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m a n dg o o dr e s u l t so na l lt h em e a s u r e s k e yw o r d sd a t am i n i n g ，e n s e m b l ea l g o r i t h m ，i m b a l a n c e dd a t as e t s ， s y n t h e t i cs a m p l e s 现在每天都有大量数据需要提取和分析，数据挖掘技术在许多实际 应用中获得巨大成功，分类模型已经在许多应用场合得到广泛应用，如 原油泄漏检测、信用卡检测、医疗检测等等。由于这个课题的重要性， 许多研究者开展了许多卓有成效的工作。 本论文的研究总体目标是探讨一种分类方法用于提高非平衡数据集 结构的分类器的准确率。非平衡数据集指的是某一类别的样本数多于其 他类别的样本数。传统机器学习对这些类型的数据比较敏感，往往倾向 于重视占主导地位的高频样本而忽视低频样本。为极少类样本的数据集 生成的模型仅得到对这些类别样本较低的分类准确率。然而，在许多情 形下，这个类别可能是人们最感兴趣的。 例如：信用卡诈骗的误判可能导致银行声誉的毁灭，业务的流失以 及客户的不满意。然而，一个欺诈交易的错误分类往往只需要一个呼叫 客户端。同样，在原油泄漏检测中，一个未被发现的裂口将导致几千美 元的损失。训练数据集的分类的改变，可以改变多数类和少数类的错误 分布。这个非平衡问题是一个相对问题，依赖于：类的不平衡度，数据 所表示的复杂性以及集合和类的总体规模。为了处理这个问题，已经提 出了许多方法。这些方法被分为数据层和分析层。 数据层对少数类进行处理，最常见的方法是过采样和欠采样。欠采 样将导致少数类的信息的丢失，而且是在进行分类时不允许删除一些样 本。随机的过采样使研究者选择的范围更小更专业，因此可能过度拟合。 对于可选择的过采样，c h a w l ae ta l 提出一种叫做s m o t e 的方法来合 成少数类的样本。s m o t e 的优点在于它使研究者的选择范围更小更专 业。c h a w l a e ta l 提出了一种更先进的s m o t e b o o s t 方法，给出一系列的迭 代t 环，每一个迭代t 环，d t 是时时更新的。因此少数类的过采样样本是 通过合成少数类的样本得到的。d a t a b o o s t i m 是由g u o 矛i v i k t o r 提出的 a d a b o o s t m 2 的修改版，它鉴别原有的本并为多数类和少数类合成样本。 算法层面上的这些方法操纵的是算法，而不是数据集。最常见的集 成算法是b a g g i n g 算法币l a d a b o o s t 算法，它们提高了分类性能，它们是综 合了其它方法的例子，对模型进行整合的方法，b a g g i n g 是由l e ob r e i m a n 在1 9 9 4 年提出的，通过将随机生成的训练数据集的分类整合起来 b o o s t i n g 是训练“弱”学习者的一种机制，通过综合由“弱 学习者的假设 得到总体假设，它有很高的正确率。a d a b o o s t 是由f r e u n d $ 1 1 s c h a p i r e 提 高了随机分类样本的权重，降低了均衡分类的比例，在不考虑非平衡数 据集的情况下，传统的b o o s t i n g 方法不能很好的适用于少数类的情况。 根据s u ne ta l 的成本敏感分类方法，考虑到不同类型的分类会需要不 同的成本。一个分类的成本矩阵编码反映了这个分类方法的好坏。为了 处理非平衡数据集问题，正面样本的识别重要性比负面的要高。因此， 非平衡分类中，正面样本的成本要比负面样本的成本更加重要。 为了处理这个问题，文中提出一种集成算法，该算法建立了包含所 有少数类和欠采样多数类的新平衡训练集。在每轮迭代中，算法确认在 多数类上的原来样本并为下一次迭代生成合成样本。实验中为每个训练 集设置弱学习器作为基分类器。最后的预测结果通过多数投票方法获 得。 e a d s a m p l i n g 适合用来处理不平衡数据集，因为：首先，平衡每一 个要训练的数据，然后，处理多数类的欠采样的信息丢失，通过寻找原 有的样本并且为这些样本创建新的合成样本，最后，通过汇总所有的分 类，创建一种集成算法。 e a d s a m p l i n g 是从u c i 数据集中选取六个数据集进行评测的，并分 别与其他已知算法进行了比较，评价指标有f 度量、g 平均值、总体准 确率、a u c 等。 和一种传统的机器学习算法相比，我们介绍两种合成算法和两种成 本敏感算法。 w e k a3 6 0 中的c 4 5 树被用来作基分类器，a d a t a b o s t m l ，b a g g i n g ， a d a c o s t ，c s b 2 ，和e a d s a m p l i n g 分别集成了1 0 种迭代法。除了a d u l t 矛1 m o n k 2 ，它们不但提供测试数据集，而且运用1 0 倍的交叉验证。 在衡量t p 率方面，对比无成本损失算法，e a d s a m p l i n g 算法在少数 类预测中减少了错误。例如h e p a t i t i s 数据集，c 4 5 和e a d s a m p l i n g 的差 别表明，1 3 个错误的归类( 归类于少数类) 是错误的，它们不能归类于 少数类。 根据少数类的f 度量指标，与成本敏感算法和非成本敏感算法相 比，e a d s a m p l i n g 算法的进步是很明显的。 g 平均值被认为是处理不平衡数据集的最重要评价指标， e a d s a m p l i n g 方法，在几乎所有的数据集中，能得到最高的g 平均值； 除了a d u l t 矛1 o z o n e 方法，一些成本敏感算法能得到更好的结果。 e a d s a m p l i n g 算法在处理少数类时，计算t p 率和f 度量上能得到好 的结果，能够保持恒定或有轻微的上升，并且能够保证整体正确率。 然而，有一些成本敏感算法在计算t p 率时能得到更好的结果，在处 理多数类和少数类时，e a d s a m p l i n g 算法通过得到好的f 度量指标从而 得到得到更好的结果，在任何情况下都能保证正确率。 每一个数据集的r o c 曲线图形化地表明了e a d s a m p l i n g 的结果。 f m e a s u r e 方法在任何数据集上处理少数类时最好的 f m e a s u r e 在处理多数类时，4 个到6 个数据集时是最好的 g 平均值方法在处理4 个到6 个数据集时是最好的 a u c 在处理4 个到6 个数据集时是最好的 整体正确率在处理4 到6 个数据集时能得到最好的值 这些结果证明了之前提到的算法的有效性。 为了提高e a d s a m p l i n g 方法，自动地集合邻近数据用来合成样本是 很有必要的，并且合成样本的百分比是根据数据集得到的，运用 e a d s a m p l i n g 方法来提高数据集的不平衡( 达到1 ：1 0 0 0 0 或者更多) 是 不是一个很好的方法? 使用更多的类实施这种方法是否有必要? 为了 提高计算速率，为多数类采用另外一种欠采样技术会不会更好? 这些问 题都是未来需进一步要探讨的问题，在测量准确率方面，用成本曲线将 是一种很好的办法。 关键词数据挖掘，集成算法，非平衡数据集，合成样本 i v c o n t e n t s a b s t r a c t i 摘要i i c h a p t e r1 i n t r o d u c t i o n 1 1 1d e f i n i t i o no f t h ep r o b l e m 1 1 2 o b j e c t i v e 2 1 3 o r g a n i z a t i o no f t h i sd i s s e r t a t i o n 3 c h a p t e r2 i m b a l a n c ed a t a s e t s ：t a c k l i n gt h ep r o b l e m 4 2 1 s a m p l i n gm e t h o d sf o ri m b a l a n c e d a t a s e t s 4 2 1 1 u n d e r - s a m p l i n g 4 2 1 2 o v e r - s a m p l i n g 4 2 2e n s e m b l em e t a - l e a r n i n ga l g o r i t h m s 5 2 2 1 b a g g i n g 6 2 2 2a d a b o o s t 7 2 3c o s ts e n s i t i v ea l g o r i t h m s 8 2 3 1a d a c o s t 8 2 3 2c s b 2 1 0 2 4s m o t e 1 0 2 5o t h e ra p p r o a c h e s 1 4 2 6c o n c l u s i o n 15 c h a p t e r3e a d s a m p l i n ga l g o r i t h m 1 6 3 1 g e n e r a t i n gs y n t h e t i ce x a m p l e s 。1 7 3 2 s a m p l i n gt r a i n i n g d a t a s e t s 19 3 3 c o n c l u s i o n 2 0 c h a p t e r4 e v a l u a t i o n 21 4 1m e a s u r e su s e 21 4 2t h er e c e i v e ro p e r a t i o nc h a r a c t e r i s t i cc u r v e 2 2 4 3k f o l dc r o s sv a l i d a t i o n 2 4 4 4d a t a s e t s 2 5 4 5r e s u l t sa n dd i s c u s s i o n 2 7 v 4 6t h er e c e i v e ro p e r a t i o nc h a r a c t e r i s t i cc u r v ef o re a c hd a t a s e t 2 9 4 7c o n c l u s i o n 3 3 c h a p t e r5 c o n c l u s i o n 3 4 5 1f u t u r ew o r k ：；! ； a p p e n d i xa c l a s s i f y i n g w i t hd e c i s i o nt r e e s 3 6 a p p e n d i x b e u c l i d e a nd i s t a n c e 3 9 a p p e n d i xc a b o u t w e k a 9 0 a p p e n d i xd e - a d s a m p l i n gw e k ai n t e g r a t i o n 4 1 v i l i s to fg r a p h s f i g 三! - 1e n s e m b l em e t a - l e a r n i n ga l g o r i t h m 5 f i g2 - 2e x a m p l eo fg e n e r a t i o no fs y n t h e t i ce x a m p l e sf o rn u m e r i cd a t a 13 f i g2 - 3e x a m p l eo f g e n e r a t i o no f s y n t h e t i ce x a m p l e sf o rn o m i n a l d a t a 1 3 f i g2 - 4ag r a p h i co fs y n t h e t i ce x a m p l eg e n e r a t i o n 1 4 f i g4 - 1r o cc u r v e sf o rt w od i f f e r e n tc l a s s i f i e r s 2 2 f i g4 - 2r o cc u r v eo f t h eh e p a t i t i sd a t as e t 3 0 f i g4 - 3r o c c u r v eo f t h eo z o n ed a t as e t 3 0 f i g4 - 4r o cc u r v eo ft h ea d u l td a t as e t 31 f i g4 - 5r o c c u r v eo f t h ep i m ad a t as e t 31 f i g4 - 6r o cc u r v e o f t h em o n k sd a t as e t 3 2 f i g4 - 7r o cc u r v eo ft h ey e a s td a t as e t 3 2 f i ga 一1d e c i s i o nt r e ee x a m p l e 3 6 f i gd - 2s e l e c c i o no fe a d s a m p l i n go nw e k a 4 1 f i gd - 3o p t i o n so fe a d s a m p l i n gi n s i d ew e k a 4 2 v i i l i s to f t a b l e s t a b l e3 - 1i n s t a n c e se r r o n e o u sc l a s s i f i cf o rp i m ad a t a s e tu s ef o rs m o t e 1 7 t a b l e3 - 2e x a m p l eo fc a l c u l a t i o no fe c l u d i a nd i s t a n c e 18 t a b l e3 - 3e x a m p l eo fc r e a t i o no fs y n t h e t i ce x a m p l e s 18 t a b l e3 - 4g e n e r a t i n gt r a i n i n gd a t a s e t sr o u n d sf o ro z o n ed a t a s e t 2 0 t a b l e4 1t w oc l a s s e sc o n f u s i o nm a t r i x 2 1 t a b l e4 2d a t a s e t su s e di nt h ee x p e r i m e n t s 2 5 t a b l e4 - 3c o s tm a t r i xu s eo ne x p e r i m e n t s 2 6 t a b l e4 - 4r e s u l tf o rf - m e a s u r e s ，t pr a t em i n ，a c c u r a c y ，a n dg - m e a n u s i n gc 4 5 c l a s s i f i e r , a d a b o o s t m1 ，b a g g i n g ，a d a c o s t ，c s b 2 ，a n de a d s a m p l i n g e n s e m b l e s ：1 7 l i s to fa l g o r i t h m s a l g o r i t h m ：z - 1a d a b o o s ta l g o r i t h m 7 a l g o r i t h m 2 2a d a c o s ta l g o r i t h m 10 a l g o r i t h m2 - 3s m o t ea l g o r i t h m 1 2 a l g o r i t h m3 1e - a d s a m p l i n ga l g o r i t h m 16 i x l i s to fa b b r e v i a t i o n s a u c a r e au n d e rc u r v e t p r t r u ep o s i t i v er a d i o f p r f a l s ep o s i t i v er a d i o x c h a p t e r ii n t r o d u c t i o n o nt h i sc h a p t e rw ep r e s e n tt h eg e n e r a ld e s c r i p t i o no ft h ep r o b l e ma sw e l lt h e o b j e c t i v e so ft h i sd i s s e r t a t i o n j 1 d e f i n i t i o no f t h ep r o b l e m i m b a l a n c ed a t a s e t sf o rw h i c ho n ec l a s si s r e p r e s e n t e db yal a r g e rn u m b e ro f i n s t a n c e st h a no t h e rc l a s s e sa r ec o m m o no n f r a u d d e t e c t i o n 1 2 3 ，t e x t c l a s s i f i c a t i o n 4 ，a n dm e d i c a ld i a g n o s i s 5 ，o nt h i sd o m a i n sa sw e l lo t h e r se x a m p l e s ， m i n o r i t yc l a s sc a nb et h el e s st o l e r a n tt oc l a s s i f i c a t i o nf a i la n dv e r yi m p o r t a n tf o r c o s ts e n s i t i v e f o re x a m p l e ，m i s c l a s s i f i c a t i o no f ac r e d i tc a r df r a u dm a y c a u s e ab a n k r e p u t a t i o nd e p l o r e d ，c o s to ft r a n s a c t i o n ，a n dd i s s a t i s f i e dc l i e n t h o w e v e r ，a m i s c l a s s i f i c a t i o nn o tf r a u dt r a n s a c t i o no n l yc o s t sac a l lt oc l i e n t l i k e w i s ei na no i l s p l i td e t e c t i o n 6 ，a nu n d e t e c t e ds p l i tm a yc o s tt h o u s a n d so fd o l l a r s ，b u tc l a s s i f y i n ga n o ts p l i ts a m p l ea sa s p l i tj u s tc o s ta ni n s p e c t i o n d u ei m b a l a n c ep r o b l e mt r a d i t i o n a l m a c h i n el e a r n i n gc a na c h i e v eb e t t e rr e s u l t so nm a j o r i t yc l a s sb u tm a yp r e d i c tp o o r l y t h em i n o r i t yc l a s se x a m p l e s t h e c h a n g e do nc l a s sd i s t r i b u t i o no f t h et r a i n i n gs e tc a n c h a n g e t h ed i s t r i b u t i o no fe r r o r s b e t w e e nt h e m i n o r i t y c l a s sa n dt h e m a j o r i t y c l a s s 7 t h ei m b a l a n c ep r o b l e mi sar e l a t i v ep r o b l e mt h a td e p e n d so n ：t h e d e g r e eo f c l a s si m b a l a n c e ，t h ec o m p l e x i t yo ft h er e p r e s e n t e db yt h ed a t a ，t h eo v e r a l l s i z eo f t h e t r a i n i n gs e t ，a n dt h ec l a s s i f i e ri n v o l v e d 8 i no r d e rt ot a c k l et h i sp r o b l e m m a n ys o l u t i o n sh a v eb e e np r e s e n t e d 【9 10 】【1 1 】w e i s s 【12 ，i n t r o d u c e dag o o d s u r v e yo f t h el i t e r a t u r eo nr a r i t yi nd a t a m i n i n g ，h i sa r t i c l ea l s od e m o n s t r a t e st h a tr a r e c l a s s e sa n dr a r ec a s e sa r ev e r ys i m i l a rp h e n o m e n a - - b o t hf o r m so f r a r i t ya r es h o w n t oc a u s es i m i l a rp r o b l e m sd u r i n gd a t am i n i n ga n db e n e f i tf r o mt h es a m er e m e d i a t i o n m e t h o d s t h e s es o l u t i o n sa r ed i v i d e do nd a t al e v e la n da l g o r i t h ml e v e l o nd a t al e v e l ，m o s tc o m m o nw a y st ot a c k l er a r i t ya r e o v e r - s a m p l i n ga n d u n d e r - s a m p l i n g u n d e r s a m p l i n gm a yc a u s eal o s so fi n f o r m a t i o no nm a j o r i t yc l a s s ， 丛垒墨! 曼! b 星墨i 墨 h 垒p ! 皇! ! n 鱼囤亟坠垡! i q n a n dd e p l o r eo ni t sc l a s s i f i c a t i o nd u et or e m o v es o m ee x a m p l e so nt h i sc l a s s r a n d o mo v e r - s a m p l i n gm a ym a k et h ed e c i s i o nr e g i o n so ft h el e a r n e rs m a l l e ra n d m o r es p e c i f i c ，t h u sm a yc a u s et h el e a r n e rt oo v e r - f i t a sa na l t e r n a t i v eo f o v e r - s a m p l i n g ，s m o t e 13 】w a sp r o p o s e da sm e t h o d t og e n e r a t es y n t h e t i cs a m p l e s o nm i n o r i t yc l a s s ，t h ea d v a n t a g eo fs m o t ei st h a ti tm a k e st h ed e c i s i o nr e g i o n s l a r g e ra n dl e s ss p e c i f i c c h a w l a 14 】i n v e s t i g a t e dt h ee f f e c to fs a m p l i n gm e t h o d s ， c o n c l u d i n gt h a ts m o t e o na na v e r a g ei m p r o v e st h ea u c so v e rt h eo t h e rs a m p l i n g s c h e m e s ，a l s oo b s e r v e dt h a tu n d e r - s a m p l i n gi su s u a l l yb e t t e rt h a no v e r - s a m p l i n g w i t hr e p l i c a t i o n t h em e t h o d sa ta l g o r i t h ml e v e lo p e r a t eo nt h ea l g o r i t h m so t h e rt h a nt h ed a t as e t s b a g g i n ga n db o o s t i n ga r et w oa l g o r i t h m st oi m p r o v et h ep e r f o r m a n c eo fc l a s s i f i e r t h e ya r ee x a m p l e so fe n s e m b l em e t h o d s ，o rm e t h o d st h a tu s eac o m b i n a t i o no f m o d e l s b a g g i n g ( b o o t s t r a pa g g r e g a t i n g ) w a sp r o p o s e db yl e ob r e i m a ni n19 9 4t o i m p r o v et h ec l a s s i f i c a t i o nb yc o m b i n i n gc l a s s i f i c a t i o n so fr a n d o m l yg e n e r a t e d t r a i n i n gs e t s 15 b o o s t i n gi s am e c h a n i s mf o rt r a i n i n gas e q u e n c eo f w e a k l e a r n e r sa n d c o m b i n i n gt h eh y p o t h e s e sg e n e r a t e db yt h e s ew e a kl e a r n e r ss oa st oo b t a i na n a g g r e g a t eh y p o t h e s i sw h i c hi sh i g h l ya c c u r a t e a d a b o o s t 16 ，i n c r e a s e st h ew e i g h t s o fm i s c l a s s i f i e de x a m p l e sa n dd e c r e a s e st h o s ec o r r e c t l yc l a s s i f i e du s i n gt h es a m e p r o p o r t i o n ，w i t h o u tc o n s i d e r i n gt h ei m b a l a n c eo ft h ed a t as e t s t h u s ，t r a d i t i o n a l b o o s t i n ga l g o r i t h m sd on o tp e r f o r mw e l lo nt h em i n o r i t yc l a s s a sb o o s t i n g a l t e m a t i v ea r es m o t e b o o s t 17 】w h i c hp r o c e e d si nas e r i e so ftr o u n d sw h e r e e v e r yr o u n dt h ed i s t r i b u t i o nd ti