Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Алгоритм дерева решений
Decision tree algorithm
В обучении деревьев решений, ID3 (Итеративный дихотомизатор 3) — это алгоритм, разработанный Россом Куинланом для построения дерева решений на основе набора данных. ID3 является предшественником алгоритма C4.5 и обычно применяется в области машинного обучения и обработки естественного языка.
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 domain
Резюме
Рассчитайте энтропию каждого атрибута набора данных. Разделите ("разбейте") набор на подмножества, используя атрибут, для которого результирующая энтропия после разбиения минимальна, или, что эквивалентно, прирост информации максимален. Создайте узел дерева решений, содержащий этот атрибут. Рекурсивно примените процедуру к подмножествам, используя оставшиеся атрибуты.
Calculate the entropy of every attribute of the data set Partition ("split") the set into subsets using the attribute for which the resulting entropy after splitting is minimized; or, equivalently, information gain is maximum. Make a decision tree node containing that attribute. Recurse on subsets using the remaining attributes.
Свойства
ID3 не гарантирует нахождение оптимального решения. Алгоритм может сходиться к локальному оптимуму. Он использует жадный подход, выбирая локально лучший атрибут для разделения набора данных на каждой итерации. Оптимальность алгоритма можно повысить, используя метод возврата (backtracking) при поиске оптимального дерева решений, но это может потребовать больше времени. ID3 склонен к переобучению на тренировочных данных. Чтобы избежать переобучения, предпочтительнее использовать деревья решений меньшего размера. Этот алгоритм обычно строит небольшие деревья, но не всегда находит самое маленькое возможное дерево решений. ID3 сложнее применять к непрерывным данным, чем к дискретным (дискретные данные имеют конечное число возможных значений, что уменьшает количество потенциальных точек ветвления). Если значения какого-либо атрибута непрерывны, то существует гораздо больше вариантов разделения данных по этому атрибуту, и поиск наилучшего значения для разделения может быть ресурсоемким.
ID3 does not guarantee an optimal solution. It can converge upon local optima. It uses a greedy strategy by selecting the locally best attribute to split the dataset on each iteration. The algorithm's optimality can be improved by using backtracking during the search for the optimal decision tree at the cost of possibly taking longer. ID3 can overfit the training data. To avoid overfitting, smaller decision trees should be preferred over larger ones. This algorithm usually produces small trees, but it does not always produce the smallest possible decision tree. ID3 is harder to use on continuous data than on factored data (factored data has a discrete number of possible values, thus reducing the possible branch points). If the values of any given attribute are continuous, then there are many more places to split the data on this attribute, and searching for the best value to split by can be time consuming.
Использование
Алгоритм ID3 используется для обучения на наборе данных с целью построения дерева решений, которое хранится в памяти. Во время работы это дерево решений используется для классификации новых тестовых примеров (векторов признаков) путем прохода по дереву решений, используя признаки объекта, чтобы достичь листового узла.
The ID3 algorithm is used by training on a data set to produce a decision tree which is stored in memory. At runtime, this decision tree is used to classify new test cases (feature vectors) by traversing the decision tree using the features of the datum to arrive at a leaf node.