Vi presenterar DL8, en exakt algoritm för att hitta ett beslut träd som optimerar en ranking funktion under storlek, djup, noggrannhet och blad begränsningar. Eftersom upptäckten av optimala träd har hög teoretisk komplexitet, hittills har få ansträngningar gjorts för att beräkna sådana träd för verkliga dataset. En exakt algoritm är av både vetenskapligt och praktiskt intresse. Ur vetenskaplig synvinkel kan det användas som en guldstandard för att utvärdera utförandet av heuristiska begränsningar-baserade beslut trädinlärare och för att få ny insikt i traditionella beslut trädinlärare. Ur tillämpningssynpunkt kan den användas för att upptäcka träd som inte kan hittas av heuristiska beslutsträdslärare. Nyckeltanken bakom vår algoritm är att det finns ett samband mellan begränsningar på beslutsträd och begränsningar på objektet. Vi visar att optimala beslut träd kan extraheras från gitter av artiklar i linjär tid. Vi ger flera strategier för att effektivt bygga dessa gitter. Experiment visar att DL8 under samma begränsningar uppnår bättre resultat än C4.5, vilket bekräftar att en uttömmande sökning inte alltid innebär att man överanstränger sig. Resultaten visar också att DL8 är ett användbart och intressant verktyg för att lära sig beslutsträd under begränsningar.
REF presenterade DL8, en exakt algoritm för att hitta ett beslut träd som optimerar en rankning funktion under storlek, djup, noggrannhet och blad begränsningar.
Mining optimal decision trees from itemset lattices
{'venue': "KDD '07", 'journal': None, 'mag_field_of_study': ['Computer Science']}