One of the practical applications of Artificial Neural Networks (ANN), is the classification of data, understood as a process of searching for properties common to a number of objects a domain of knowledge, depending on the values \u200b\u200bof certain attributes. Within the issue of automatic qualification, while the alternative process of more general processes encompassed within what is known as "machine learning", one of the learning algorithms known, based on "examples", is called ID3, or "Iterative dichotomized (version) 3" (JR Quinlan, 1979). Work with symbolic data, as opposed numerical data, and is based on obtaining a decision tree (see Annex
Based on a conceptual level of abstraction higher, the so-called "machine learning" or learning machine, it is possible to distinguish two types of learning: rote learning
- (or rote learning) and
- cognitive learning. The former refers to processes of memorizing a) facts b) sequences of actions or procedures, the type of learning being easier to implement in a system computational "smart." The second type of learning, cognitive, is making use of reasoning procedures from a basic knowledge so that it is possible to obtain "class descriptions, generalizations are derived from the observation n concrete examples. It is therefore a kind of learning based on inductive reasoning in nature, one that allows the formulation of general principles from specific individual cases, unlike deductive reasoning, that from generalizations and through logic (syllogisms), infer conclusions particular character and concrete. In inductive reasoning, is the accumulation of observations which allows to draw conclusions of universal validity. However, it is not uncommon in machine learning systems, find the two worlds of reasoning, since the generalizations are obtained by inductive reasoning, from a relatively small group of "examples" or observations ( pre-training phase), will then drawing conclusions for individuals through a process of deductive reasoning.
- Decision trees or classification consists of an inductive technique used widely in the field of machine learning. Graphically, consist of nodes and branches. The first identifier representing a particular attribute. The terminal nodes or leaves represent the values \u200b\u200bassociated with that attribute, while branches. Each of these values \u200b\u200bare accessed through a branch of the node. The cases are directed toward one or another branch based on the values \u200b\u200bof its attributes. Classification trees are a method valid learner in situations in which the starting examples can be represented by a finite set of attributes and values. Classification trees can also be conceived from an algorithmic standpoint, as a set of if-then rules .
Most of the heuristics used for the determination of decision trees through learning algorithms, are based on the mathematical theory of information ( C .
Shannon, W. Weaver, Bell Laboratories, 1948) [1- ] [ 2]. Heuristics are criteria, methods or principles for deciding, from among several alternative courses of action, which will be most effective to achieve certain goal. Restrict the number of evaluations, and therefore impact on improving the search time for solutions. Entropíay amount of information are two concepts that come together in the field of heuristics. About Entropíay amount of information, see Uncle Petros
- : [1 ] [ 2 ] [
]. ID3 algorithm
generates what is called the rules "hard", ie those who only see two possible states (true or false, positive-negative, 0-1, etc.), And which are both a bivalent character, unlike the rules "fuzzy", which can represent an infinite range of values \u200b\u200bbetween two ends of a scale as those obtained using algorithms ID3"extended" (ID4, ID5, ID5R , C4.5, C5, etc.).
ID3 Algorithm Pseudocode
:If all examples belong to E same class C, then arbol1 \u0026lt;- node labeled with C
ButIf a = f, then C \u0026lt;- class majority of the examples of E arbol1 \u0026lt;- node labeled with C But A \u0026lt;- best attribute of a arbol1 \u0026lt;- node labeling with A For each v belonging to the values \u200b\u200bof A, do VAS \u0026lt;- examples of E with the value v for attribute A If Eav = f, then ; arbol2 \u0026lt;- node labeled with the majority class in E But arbol2 \u0026lt;- ID3 (VAS, a-{A}) arbol1 \u0026lt;- add to the arbol2 arbol1 through a branch labeled with v arbol1 Return Another representation in pseudocode algorithm ID3 :
-Decision-Tree Learning (Examples, Attributes ,
Default)returns a decision tree
IF there
Examples
, Default
return
ELSE IF
if all examples have the same classification
,
return
classification,
ELSE IF s = Attribute
return Majority ( Examples
) ELSE best-atr \u0026lt;- choose-attribute (Attributes , Examples
)
tree \u0026lt;- new decision tree rooted in best-atr
FOR EACH value v [i] best-atr DO Examples
[i] \u0026lt;- Examples { items with better-atr = v [i]} Subar \u0026lt;--Decision-Tree Learning (examples [i], Attributes
- best-atr, Majority ( Examples ))
add branch the tree with label v [i] and subtree Subar OD return tree learning processes that make use of the classification of data by discovery of patterns, are widely used in what is known as "Data Mining", Castilian data mining, data mining or knowledge discovery in databases, terminological diversity about which there is discussion.
Maximiliano del Rio is the author of a version written in Prolog language learning algorithm ID3
. The files for this implementation (library Ratings ) can be located either in the source code section of
programacion.com
(compressed into a "zip"), or personal space that the author has the "Wiki " of SWI-Prolog
. In " guia.txt " describes the management of this implementation
ID3 algorithm in Prolog, which uses the ODBC
interface to query the tables of the database selected, the examples are obtained for the generation of production rules. Is also attached file " clasif.pl " program "Data Mining" that uses the ID3 algorithm
endowed GUI using the native library XPCE
"[...]
program that uses the above library [...] helps generate the rules and displays the textual and graphical rules obtained, also shows a trace of how the algorithm works. " SourceThis GUI is opened releasing the target "? - Main." on the command line SWI-Prolog, once compiled the program. Finally, the library " compila.pl " contains predicates that allow generate an executable for Windows from the results, using SWI-Prolog. For a rather wide on the Prolog implementation of automatic learning processes in general and inductive learning by decision trees in particular (data classification) is highly recommended reading Chapter 18, "Machine Learning", the (now classic) work of Ivan Bratko, "Prolog: Programming for Artificial Intelligence" (2 nd ed. Addison-Wesley, 1994, ISBN: 0-201-41606 - 9). On decision trees specifically point is 18.6, "Induction of decision trees." There is thus itself a repository of machine learning algorithms written in Prolog, Prolog library of machine learning algorithms , albeit somewhat outdated, since the last update seems to date from 1994, maintained by Thomas Hoppe (Fraunhofer-Gesellschaft , Technical University of Berlin ). The programs are written using the syntax and, in most cases, the predefined predicates (built-in predicates ) specified in Prolog by Clocksin and Mellish described, known as standard Edinburgh, based in turn on the DECSYSTEM-10 (D. Warren, F. Pereira and L. Pereira), to thus ensure the greatest possible degree of compatibility between versions of the language. algorithm implementations ID3 are located in the " RTD" (see in any case the file "Readme " for more information). More information:
ID3 algorithm JR Quinlan(document translated by JA Fernandez,
PDF, compressed in a zip). Basics of Symbolic Learning (JG Boticario).
Learning classifiers (Berzal F. Galiano, in PDF). ART: An alternative method for constructing decision trees (Berzal F. Galiano, in PDF). ART: An alternative method for constructing decision trees (Berzal F. Galiano, 2002; doctoral thesis in PDF). RTD Torgos ID3-like system based on the gain-ratio measure ( ID3 algorithm written in Edinburgh Prolog syntax.) This code is located in the directory on Machine Learning
- the CMU Artificial Intelligence Repository
- (see description , in each of the directories there are three files, "0.html", "0. doc "and" readme.txt ", which contain a description of its contents). The board devoted to general Prolog is located this link.
- Induction of Decision Trees.
- Trees, Graphs (in
- Data Structures, algoritmia.net ).
-
Árboles
de Clasificación ( - PDF ;
tema de los apuntes de la asignatura " Métodos
Matemáticos en Ciencias de la Computación ", UPV ).
Sistemas
de Inducción de árboles de decisión .
Decision Tree for
Optimization Software .
- Artificial
Intelligence Lecture Notes : a) Problem
Solving in Prolog ; b) - Induction
of Decision Trees .
Algoritmo ID3 written in Prolog. " - ID3" in "The Machine Learning Dictionary ." " RTD Torgos ID3-like system based on the gain-ratio measure " in CMU Artificial Intelligence Repository. Is part of the program directory "
- Machine Learning Algorithms Implemented in Prolog ." Thesis: Induction of Knowledge
- with Uncertainty in Fuzzy Relational Databases (AJ Flechoso Gómez, 1998). In relation to the matters discussed in this "post" see
- Chapter 2 in general and in particular paragraphs 2.1 (Introduction), 2.2 (Knowledge discovery and data mining), 2.3 (Mining Methods used data), and 2.4
- (Inductive Logic Programming). mlnet (Machine Learning network) Online Information Service.
- Annex -
- Decision Trees Decision trees are a representation of processes involved in classification tasks. They consist of: Nodes: names or identifiers of the attributes. Branches: possible attribute values \u200b\u200bassociated with the node. Leaves: set examples classified and labeled with the name of a class.
- nodes reflect properties of domain objects, arcs or branches are the different values \u200b\u200bof these attributes and the leaves are the possible classifications. [The decision trees] is particularly well suited to cases in which: Examples may described as attribute-value pairs. The objective function takes discrete values. We can take hypotheses disjunctions. Possible presence of noise in the training set. values \u200b\u200bof some attributes in the examples of the training set may be unknown.
- [Source: Induction of Decision Trees: ID3
En
] [Back to text
]
Taxonomy The classification of natural species comprises the following steps: UK - Type - Class - Order - Family - Genus - Species. This sequence is recalled in reverse order, with the phrase: "A species was classified families overall rates of the kingdom."