ID3 algorithm (original) (raw)
L'algorisme ID3 (acrònim anglès d'Iterative Dichotomiser 3), en l'àmbit de la intel·ligència artificial, és un algorisme inventat per l'any 1975 emprat per a generar un arbre de decisió a partir d'un conjunt de dades. ID3 és el precursor de l'algorisme C4.5 i s'utilitza en l'aprenentatge automàtic i el processament de llenguatge natural.
| Property | Value |
|---|---|
| dbo:abstract | L'algorisme ID3 (acrònim anglès d'Iterative Dichotomiser 3), en l'àmbit de la intel·ligència artificial, és un algorisme inventat per l'any 1975 emprat per a generar un arbre de decisió a partir d'un conjunt de dades. ID3 és el precursor de l'algorisme C4.5 i s'utilitza en l'aprenentatge automàtic i el processament de llenguatge natural. (ca) Iterative Dichotomiser 3 (ID3) ist ein Algorithmus, der zur Entscheidungsfindung dient. Er wird bei Entscheidungsbäumen eingesetzt. Der australische Forscher publizierte diesen Algorithmus erstmals im Jahr 1986. ID3 war in seinen ersten Jahren sehr einflussreich. Er findet auch heute noch in einigen Produkten Verwendung. ID3 gilt als Vorgänger des C4.5-Algorithmus. ID3 wird verwendet, wenn bei großer Datenmenge viele verschiedene Attribute von Bedeutung sind und deshalb ein Entscheidungsbaum ohne große Berechnungen generiert werden soll. Somit entstehen meist einfache Entscheidungsbäume. Es kann aber nicht garantiert werden, dass keine besseren Bäume möglich wären. Die Basisstruktur von ID3 ist iterativ. Es werden zu jedem noch nicht benutzten Attribut Entropien bezüglich der Trainingsmenge berechnet. Das Attribut mit dem höchsten Informationsgewinn (englisch: information gain) bzw. der kleinsten Entropie, wird gewählt und daraus ein neuer Baum-Knoten generiert. Das Verfahren terminiert, wenn alle Trainingsinstanzen klassifiziert wurden, d. h. wenn jedem Blattknoten eine Klassifikation zugeordnet ist. (de) Ο ID3 (Iterative Dichotomiser 3) είναι ένας αλγόριθμος, ο οποίος χρησιμοποιείται για να παραγάγει ένα . Ο αλγόριθμος είναι βασισμένος στο Ξυράφι του Όκαμ: προτιμά τα μικρότερα δέντρα απόφασης (απλούστερες θεωρίες) από μεγαλύτερες. Εντούτοις, δεν παράγει πάντα το μικρότερο δέντρο, και για αυτό τον λόγο είναι ευρετικός. Το Ξυράφι του Όκαμ τυποποιείται χρησιμοποιώντας την έννοια της εντροπίας πληροφοριών: Ο αλγόριθμος ID3 μπορεί να συνοψιστεί ως εξής: 1. * Πάρτε όλες τις αχρησιμοποίητες ιδιότητες και υπολογίστε την εντροπία τους λαμβάνοντας υπόψη δείγματα δοκιμής 2. * Επιλέξτε την ιδιότητα για την οποία η εντροπία είναι ελάχιστη 3. * Δημιουργήστε έναν κόμβο που να περιέχει αυτή την ιδιότητα Μια εξήγηση της υλοποίησης του ID3 μπορεί να βρεθεί στον , ο οποίος είναι μια επέκταση του ID3. (el) El algoritmo ID3 es utilizado dentro del ámbito de la inteligencia artificial.Su uso se engloba en la búsqueda de hipótesis o reglas en él, dado un conjunto de ejemplos. El conjunto de ejemplos deberá estar conformado por una serie de tuplas de valores, cada uno de ellos denominados atributos, en el que uno de ellos, ( el atributo a clasificar ) es el objetivo, el cual es de tipo binario ( positivo o negativo, sí o no, válido o inválido, etc. ). De esta forma el algoritmo trata de obtener las hipótesis que clasifiquen ante nuevas instancias, si dicho ejemplo va a ser positivo o negativo. ID3 realiza esta labor mediante la construcción de un árbol de decisión. Los elementos son: * Nodos: Los cuales contendrán atributos. * Arcos: Los cuales contienen valores posibles del nodo padre. * Hojas: Nodos que clasifican el ejemplo como positivo o negativo. (es) In decision tree learning, ID3 (Iterative Dichotomiser 3) is an algorithm invented by Ross Quinlan used to generate a decision tree from a dataset. ID3 is the precursor to the C4.5 algorithm, and is typically used in the machine learning and natural language processing domains. (en) L’algorithme ID3 a été développé à l’origine par Ross Quinlan. C’est un algorithme de classification supervisé, c’est-à-dire qu'il se base sur des exemples déjà classés dans un ensemble de classes pour déterminer un modèle de classification. Le modèle que produit ID3 est un arbre de décision. Cet arbre servira à classer de nouveaux échantillons. L'algorithme C4.5 est une amélioration d'ID3, notamment du point de vue de la facilité d'implémentation. (fr) ID3 (Iterative Dichotomiser 3) è un algoritmo greedy per l'induzione di alberi di decisione. (it) ID3は汎用目的で設計された教師あり学習アルゴリズムの一種である。その学習効率の高さと出力が決定的であることなどから、エキスパートシステムの知識獲得部分にしばしば用いられる。 (ja) Het ID3-algoritme is een algoritme dat kan worden gebruikt om een beslissingsboom te genereren. De methode werd door Ross Quinlan uitgevonden in 1986. ID3 is de voorloper van het C4.5-algoritme. Het algoritme is gebaseerd op Ockhams scheermes: een voorkeur voor kleinere bomen boven grotere bomen. Echter, het genereert niet altijd de kleinste boom en is daarom een heuristiek. Geformulariseerd geldt het concept van Entropiemaximalisatie. Bij de start van het algoritme wordt voor elk attribuut berekend waar de meeste 'winst' kan worden bepaald om als knoop te dienen. . Dit wordt herhaald voor de overige data punten en attributen. Het resultaat is een beslissingsboom in de vorm van if-then regels. (nl) Алгоритм ID3 — один из алгоритмов для построения дерева принятия решений. Разработан Джоном Р. Квинланом (англ. John R. Quinlan). Впоследствии Квинлан создал усовершенствованную версию — алгоритм C4.5. (ru) ID3 (Iterative Dichotomiser 3) — це алгоритм, розроблений , який використовується для генерації дерев рішень у машинному навчанні з деякого набору даних. ID3 є попередником алгоритму C4.5 та зазвичай використовується в областях машинного навчання і обробки природної мови. (uk) ID3算法（Iterative Dichotomiser 3 迭代二叉树3代）是一个由发明的用于决策树的算法。 这个算法是建立在奥卡姆剃刀的基础上：越是小型的决策树越优于大的决策树（简单理论）。尽管如此，该算法也不是总是生成最小的树形结构。而是一个启发式算法。奥卡姆剃刀阐述了一个信息熵的概念： 这个ID3算法可以归纳为以下几点： 1. * 使用所有没有使用的属性并计算与之相关的样本熵值 2. * 选取其中熵值最小的属性 3. * 生成包含该属性的节点 关于ID3算法的实现可以参考C4.5算法，它同时也是ID3的升级版。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/ID3_algorithm_decision_tree.png?width=300 |
| dbo:wikiPageExternalLink | http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html https://people.eecs.ku.edu/~jerzygb/j24-sel.pdf%7Cjournal=Fundamenta http://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm http://jeremykun.com/2012/10/08/decision-trees-and-political-party-classification/ http://www2.cs.uregina.ca/~hamilton/courses/831/notes/ml/dtrees/4_dtrees1.html https://archive.org/details/machinelearning00mitc_087%7Curl-access=limited%7Clast=Mitchell%7Cfirst=Tom https://archive.org/details/machinelearning00mitc_087/page/n66 |
| dbo:wikiPageID | 1966797 (xsd:integer) |
| dbo:wikiPageLength | 11460 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1111083600 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probability_distribution dbr:Root_node dbr:Sampling_(signal_processing) dbr:Natural_language_processing dbr:Base_case_(recursion) dbr:Algorithm dbr:Best-first_search dbr:Decision_tree dbr:Decision_tree_learning dbr:Decision_tree_model dbr:Ross_Quinlan dbc:Classification_algorithms dbr:Constant_(mathematics) dbr:Continuous_uniform_distribution dbr:Maximum dbr:Run_time_(program_lifecycle_phase) dbr:Node_(computer_science) dbr:Entropy_(information_theory) dbr:Mode_(statistics) dbr:Machine_learning dbr:Complete_information dbr:Computer_memory dbr:Empty_set dbr:Feature_(machine_learning) dbc:Articles_with_example_pseudocode dbr:Tree_traversal dbr:Data_set dbr:Classification_and_regression_tree dbr:Feature_vector dbr:Leaf_node dbr:Local_optimum dbr:Local_variable dbc:Decision_trees dbr:Expected_value dbr:Partition_of_a_set dbr:Cardinality dbr:Discrete_uniform_distribution dbr:Iteration dbr:Random_variable dbr:Backtracking dbr:Child_node dbr:Heuristic_(computer_science) dbr:C4.5_algorithm dbr:Greedy_algorithm dbr:Information_gain_in_decision_trees dbr:Information_theory dbr:Internal_node dbr:Minimum dbr:Recursion_(computer_science) dbr:Statistical_classification dbr:Overfitting dbr:Subset dbr:Proportion_(mathematics) dbr:Continuous_variable dbr:Population_(statistics) dbr:Posterior_distribution dbr:Algorithm's_optimality dbr:Locally_optimal dbr:File:ID3_algorithm_decision_tree.png dbr:File:ID3_decision_tree-_splicing.png |
| dbp:date | October 2018 (en) |
| dbp:reason | Why are they preferred? (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Explain dbt:Math dbt:Short_description |
| dct:subject | dbc:Classification_algorithms dbc:Articles_with_example_pseudocode dbc:Decision_trees |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatClassificationAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms |
| rdfs:comment | L'algorisme ID3 (acrònim anglès d'Iterative Dichotomiser 3), en l'àmbit de la intel·ligència artificial, és un algorisme inventat per l'any 1975 emprat per a generar un arbre de decisió a partir d'un conjunt de dades. ID3 és el precursor de l'algorisme C4.5 i s'utilitza en l'aprenentatge automàtic i el processament de llenguatge natural. (ca) In decision tree learning, ID3 (Iterative Dichotomiser 3) is an algorithm invented by Ross Quinlan used to generate a decision tree from a dataset. ID3 is the precursor to the C4.5 algorithm, and is typically used in the machine learning and natural language processing domains. (en) L’algorithme ID3 a été développé à l’origine par Ross Quinlan. C’est un algorithme de classification supervisé, c’est-à-dire qu'il se base sur des exemples déjà classés dans un ensemble de classes pour déterminer un modèle de classification. Le modèle que produit ID3 est un arbre de décision. Cet arbre servira à classer de nouveaux échantillons. L'algorithme C4.5 est une amélioration d'ID3, notamment du point de vue de la facilité d'implémentation. (fr) ID3 (Iterative Dichotomiser 3) è un algoritmo greedy per l'induzione di alberi di decisione. (it) ID3は汎用目的で設計された教師あり学習アルゴリズムの一種である。その学習効率の高さと出力が決定的であることなどから、エキスパートシステムの知識獲得部分にしばしば用いられる。 (ja) Алгоритм ID3 — один из алгоритмов для построения дерева принятия решений. Разработан Джоном Р. Квинланом (англ. John R. Quinlan). Впоследствии Квинлан создал усовершенствованную версию — алгоритм C4.5. (ru) ID3 (Iterative Dichotomiser 3) — це алгоритм, розроблений , який використовується для генерації дерев рішень у машинному навчанні з деякого набору даних. ID3 є попередником алгоритму C4.5 та зазвичай використовується в областях машинного навчання і обробки природної мови. (uk) ID3算法（Iterative Dichotomiser 3 迭代二叉树3代）是一个由发明的用于决策树的算法。 这个算法是建立在奥卡姆剃刀的基础上：越是小型的决策树越优于大的决策树（简单理论）。尽管如此，该算法也不是总是生成最小的树形结构。而是一个启发式算法。奥卡姆剃刀阐述了一个信息熵的概念： 这个ID3算法可以归纳为以下几点： 1. * 使用所有没有使用的属性并计算与之相关的样本熵值 2. * 选取其中熵值最小的属性 3. * 生成包含该属性的节点 关于ID3算法的实现可以参考C4.5算法，它同时也是ID3的升级版。 (zh) Ο ID3 (Iterative Dichotomiser 3) είναι ένας αλγόριθμος, ο οποίος χρησιμοποιείται για να παραγάγει ένα . Ο αλγόριθμος είναι βασισμένος στο Ξυράφι του Όκαμ: προτιμά τα μικρότερα δέντρα απόφασης (απλούστερες θεωρίες) από μεγαλύτερες. Εντούτοις, δεν παράγει πάντα το μικρότερο δέντρο, και για αυτό τον λόγο είναι ευρετικός. Το Ξυράφι του Όκαμ τυποποιείται χρησιμοποιώντας την έννοια της εντροπίας πληροφοριών: Ο αλγόριθμος ID3 μπορεί να συνοψιστεί ως εξής: Μια εξήγηση της υλοποίησης του ID3 μπορεί να βρεθεί στον , ο οποίος είναι μια επέκταση του ID3. (el) Iterative Dichotomiser 3 (ID3) ist ein Algorithmus, der zur Entscheidungsfindung dient. Er wird bei Entscheidungsbäumen eingesetzt. Der australische Forscher publizierte diesen Algorithmus erstmals im Jahr 1986. ID3 war in seinen ersten Jahren sehr einflussreich. Er findet auch heute noch in einigen Produkten Verwendung. ID3 gilt als Vorgänger des C4.5-Algorithmus. (de) El algoritmo ID3 es utilizado dentro del ámbito de la inteligencia artificial.Su uso se engloba en la búsqueda de hipótesis o reglas en él, dado un conjunto de ejemplos. El conjunto de ejemplos deberá estar conformado por una serie de tuplas de valores, cada uno de ellos denominados atributos, en el que uno de ellos, ( el atributo a clasificar ) es el objetivo, el cual es de tipo binario ( positivo o negativo, sí o no, válido o inválido, etc. ). De esta forma el algoritmo trata de obtener las hipótesis que clasifiquen ante nuevas instancias, si dicho ejemplo va a ser positivo o negativo. (es) Het ID3-algoritme is een algoritme dat kan worden gebruikt om een beslissingsboom te genereren. De methode werd door Ross Quinlan uitgevonden in 1986. ID3 is de voorloper van het C4.5-algoritme. Het algoritme is gebaseerd op Ockhams scheermes: een voorkeur voor kleinere bomen boven grotere bomen. Echter, het genereert niet altijd de kleinste boom en is daarom een heuristiek. Geformulariseerd geldt het concept van Entropiemaximalisatie. Bij de start van het algoritme wordt voor elk attribuut berekend waar de meeste 'winst' kan worden bepaald om als knoop te dienen. . (nl) |
| rdfs:label | Algorisme ID3 (ca) Iterative Dichotomiser 3 (de) Αλγόριθμος ID3 (el) Algoritmo ID3 (es) Algorithme ID3 (fr) ID3 algorithm (en) Algoritmo ID3 (it) ID3 (ja) ID3 (algoritme) (nl) ID3 (алгоритм) (ru) ID3算法 (zh) ID3 (алгоритм) (uk) |
| owl:sameAs | freebase:ID3 algorithm yago-res:ID3 algorithm wikidata:ID3 algorithm dbpedia-ca:ID3 algorithm dbpedia-de:ID3 algorithm dbpedia-el:ID3 algorithm dbpedia-es:ID3 algorithm dbpedia-fa:ID3 algorithm dbpedia-fr:ID3 algorithm dbpedia-it:ID3 algorithm dbpedia-ja:ID3 algorithm dbpedia-nl:ID3 algorithm dbpedia-ru:ID3 algorithm dbpedia-uk:ID3 algorithm dbpedia-zh:ID3 algorithm https://global.dbpedia.org/id/dHLQ |
| prov:wasDerivedFrom | wikipedia-en:ID3_algorithm?oldid=1111083600&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/ID3_algorithm_decision_tree.png wiki-commons:Special:FilePath/ID3_decision_tree-_splicing.png |
| foaf:isPrimaryTopicOf | wikipedia-en:ID3_algorithm |
| is dbo:wikiPageRedirects of | dbr:Iterative_Dichotomiser_3 |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Decision_tree dbr:Decision_tree_learning dbr:Incremental_decision_tree dbr:Rule_induction dbr:Ross_Quinlan dbr:Timeline_of_algorithms dbr:Corner_detection dbr:Features_from_accelerated_segment_test dbr:Machine_ethics dbr:Document_classification dbr:Symbolic_artificial_intelligence dbr:Recursive_partitioning dbr:C4.5_algorithm dbr:CN2_algorithm dbr:Greedy_algorithm dbr:ID3_(disambiguation) dbr:Information_gain_(decision_tree) dbr:Structure_mining dbr:Ethics_of_artificial_intelligence dbr:First-order_inductive_learner dbr:Outline_of_machine_learning dbr:Iterative_Dichotomiser_3 |
| is foaf:primaryTopic of | wikipedia-en:ID3_algorithm |
