Управление качеством - Мазур И.И.
ISBN 5-06-004364-9
Скачать (прямая ссылка):
Деревья решений. Деревья решений являются одним из наиболее популярных подходов к решению задач Data Mining. Они создают иерархическую структуру классифицирующих правил типа «ЕСЛИ..., ТО...», имеющую вид дерева (это похоже на определитель видов из ботаники или зоологии). Для того чтобы решить, к какому классу отнести некоторый объект или ситуацию, требуется ответить на вопросы, стоящие в узлах этого дерева, начиная с его корня. Вопросы имеют вид: «Значение параметра А больше X?». Если ответ пололштель-ный, осуществляется переход к правому узлу следующего уровня, если отрицательный, то к левому узлу; затем снова следует вопрос, связанный с соответствующим узлом.
278
Глава 7. Менеджмент как средство повышения качества
Популярность подхода связана с наглядностью и понятностью. Но очень остро для деревьев решений стоит проблема значимости. Дело в том, что отдельным узлам на каждом новом построенном уровне дерева соответствует все меньшее и меньшее число записей данных. Дерево дробит данные на большое количество частных случаев. Чем больше этих частных случаев, чем меньше обучающих примеров попадает в каждый такой частный случай, тем менее уверенной становится их классификация. Если построенное дерево слишком «кустистое», состоит из неоправданно большого числа мелких веточек, то оно не будет давать статистически обоснованных ответов. Как показывает практика, в большинстве систем, использующих деревья решений, эта проблема не находит удовлетворительного решения. Кроме того, общеизвестно, и это легко показать, что деревья решений дают полезные результаты только в случае независимых признаков. В противном они лишь создают иллюзию логического вывода.
Довольно много систем используют этот метод. Самыми распространенными являются See5/C5.0 (RuleQuest, Австралия), Clementine (Integral Solutions, Великобритания), SIPINA (University of Lyon, Франция), IDIS (Information Discovery, США) [5].
Эволюционное программирование. Проиллюстрируем современное состояние данного подхода на примере системы Poly Analyst. В данной системе гипотезы о виде зависимости целевой переменной от других переменных формулируются в виде программ на некотором внутреннем языке программирования. Процесс построения программ строится как эволюция в мире программ (этим подход немного похож на генетические алгоритмы). Когда система находит программу, достаточно точно выражающую искомую зависимость, она начинает вносить в нее небольшие модификации и отбирает среди построенных таким образом дочерних программ те, которые повышают точность. Таким образом, система «выращивает» несколько генетических линий программ, которые конкурируют между собой в точности выражения искомой зависимости. Специальный транслирующий модуль системы PolyAnalyst переводит найденные зависимости с внутреннего языка системы на понятный пользователю язык (математические формулы, таблицы и пр.), делая их легкодоступными. Для того чтобы сделать полученные результаты еще понятнее для пользовате-ля-нематематика, имеется богатый арсенал разных средств визуализации обнаруживаемых зависимостей. Для контроля статистической значимости выводимых зависимостей применяется набор современных методов, например рандомизированное тестирование.
Другое направление эволюционного программирования связано с поиском зависимости целевых переменных от остальных в форме функций какого-то определенного вида. Например, в одном из наиболее удачных алгоритмов этого типа — методе группового учета аргументов (МГУА) зависимость ищут в форме полиномов.
Тенетические алгоритмы. Строго говоря, Data Mining — далеко не основная область применения генетических алгоритмов. Их нужно
279
И. И. Мазур, В. Д. Шапиро. Управление качеством
рассматривать скорее как мощное средство решения разнообразных комбинаторных задач и задач оптимизации. Тем не менее, генетические алгоритмы вошли в стандартный инструментарий методов Data Mining и поэтому включены в данный обзор.
Пусть нужно найти решение задачи, оптимальное с точки зрения некоторого критерия. Пусть каждое решение полностью описывается некоторым набором чисел или величин нечисловой природы. Скажем, если нужно выбрать совокупность фиксированного числа параметров рынка, наиболее выраженно влияющих на его динамику, это будет набор имен этих параметров. Об этом наборе можно говорить как о совокупности хромосом, определяющих качества индивида — данного решения поставленной задачи. Значения параметров, определяющих решение, будут тогда называться генами. Поиск оптимального решения при этом похож на эволюцию популяции индивидов, представленных их наборами хромосом. В этой эволюции действуют три механизма: отбор сильнейших — наборов хромосом, которым соответствуют наиболее оптимальные решения; скрещивание - производство новых индивидов при помощи смешивания хромосомных наборов отобрагогых индивидов; мутации — случайные изменения генов у некоторых индивидов популяции. В результате смены поколений в конце концов вырабатывается такое решение поставленной задачи, которое уже не может быть далее улучшено.
