20.3. Построение дерева решений и порождающих правил

Правила являются не единственно возможным способом представления информации о концептах в виде пар- "атрибут-значение" для целей классификации. Альтернативный метод структурирования такой информации — использование дерева решения. Существуют эффективные алгоритмы конструирования таких деревьев из исходных данных. Мы обсудим их в разделе 20.3.1.

За последние 30 лет создано довольно много систем обучения, в которых использована эта методика. Среди них системы CLS [Hunt et al., 1966], ID3 [Quinlan, 1979], ACLS [Paterson and Niblett, 1982], ASSISTANT [Kononenko et al., 1984] и IND [Buntine, 1990]. Система ACLS (развитие системы ID3) стала базовой для множества коммерческих экспертных систем, таких как Expert-Ease и RuleMaster, которые нашли широкое применение в промышленности. Несколько подробнее об алгоритме работы системы ID3 будет рассказано в разделе 20.3.2.

Программный комплекс С4.5 [Quinlan, 1993] использует алгоритмы ЮЗ и включает программу C4.5Rules. Этот модуль формирует порождающие правила, используя в качестве входной информации описание дерева решений. Подробное описание этой программы имеется в технической литературе, а потому мы не будем останавливаться на ней в данной книге. В последней версии этой системы, С5.0, реализована еще более тесная интеграция форматов представления деревьев решений и правил.