lnu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Decisions: Algebra, Implementation, and First Experiments
Linnéuniversitetet, Fakulteten för teknik (FTK), Institutionen för datavetenskap (DV).
Linnéuniversitetet, Fakulteten för teknik (FTK), Institutionen för datavetenskap (DV).ORCID-id: 0000-0001-9775-4594
Linnéuniversitetet, Fakulteten för teknik (FTK), Institutionen för datavetenskap (DV).ORCID-id: 0000-0002-7565-3714
2014 (Engelska)Ingår i: Journal of universal computer science (Online), ISSN 0948-695X, E-ISSN 0948-6968, Vol. 20, nr 9, s. 1174-1231Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Classification is a constitutive part in many different fields of Computer Science. There exist several approaches that capture and manipulate classification information in order to construct a specific classification model. These approaches are often tightly coupled to certain learning strategies, special data structures for capturing the models, and to how common problems, e.g. fragmentation, replication and model overfitting, are addressed. In order to unify these different classification approaches, we define a Decision Algebra which defines models for classification as higher order decision functions abstracting from their implementations using decision trees (or similar), decision rules, decision tables, etc. Decision Algebra defines operations for learning, applying, storing, merging, approximating, and manipulating models for classification, along with some general algebraic laws regardless of the implementation used. The Decision Algebra abstraction has several advantages. First, several useful Decision Algebra operations (e.g., learning and deciding) can be derived based on the implementation of a few core operations (including merging and approximating). Second, applications using classification can be defined regardless of the different approaches. Third, certain properties of Decision Algebra operations can be proved regardless of the actual implementation. For instance, we show that the merger of a series of probably accurate decision functions is even more accurate, which can be exploited for efficient and general online learning. As a proof of the Decision Algebra concept, we compare decision trees with decision graphs, an efficient implementation of the Decision Algebra core operations, which capture classification models in a non-redundant way. Compared to classical decision tree implementations, decision graphs are 20% faster in learning and classification without accuracy loss and reduce memory consumption by 44%. This is the result of experiments on a number of standard benchmark data sets comparing accuracy, access time, and size of decision graphs and trees as constructed by the standard C4.5 algorithm. Finally, in order to test our hypothesis about increased accuracy when merging decision functions, we merged a series of decision graphs constructed over the data sets. The result shows that on each step the accuracy of the merged decision graph increases with the final accuracy growth of up to 16%.

Ort, förlag, år, upplaga, sidor
2014. Vol. 20, nr 9, s. 1174-1231
Nyckelord [en]
decision algebra, decision function, decision graph, decision tree, classification
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Data- och informationsvetenskap, Datavetenskap
Identifikatorer
URN: urn:nbn:se:lnu:diva-38560ISI: 000344576300003Scopus ID: 2-s2.0-84908464423OAI: oai:DiVA.org:lnu-38560DiVA, id: diva2:769935
Tillgänglig från: 2014-12-09 Skapad: 2014-12-09 Senast uppdaterad: 2018-05-17Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Scopus

Personposter BETA

Danylenko, AntoninaLundberg, JonasLöwe, Welf

Sök vidare i DiVA

Av författaren/redaktören
Danylenko, AntoninaLundberg, JonasLöwe, Welf
Av organisationen
Institutionen för datavetenskap (DV)
I samma tidskrift
Journal of universal computer science (Online)
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 396 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf