Глава 7. Менеджмент как средство повышения качества

П опулярность подхода связана с наглядностью и понятностью. Но очень остро для деревьев решений стоит проблема значимости. Дело в том, что отдельным узлам на каждом новом построенном уровне дерева соответствует все меньшее и меньшее число записей данных. Дерево дробит данные на большое количество частных случаев. Чем больше этих частных случаев, чем меньше обучающих примеров по­падает в каждый такой частный случай, тем менее уверенной стано­вится их классификация. Если построенное дерево слишком «кусти­стое», состоит из неоправданно большого числа мелких веточек, то оно не будет давать статистически обоснованных ответов. Как пока­зывает практика, в большинстве систем, использующих деревья ре­шений, эта проблема не находит удовлетворительного решения. Кро­ме того, общеизвестно, и это легко показать, что деревья решений дают полезные результаты только в случае независимых признаков. В противном они лишь создают иллюзию логического вывода.

Довольно много систем используют этот метод. Самыми распро­страненными являются See5/C5.0 (RuleQuest, Австралия), Clementine (Integral Solutions, Великобритания), SIPINA (University of Lyon, Франция), IDIS (Information Discovery, США) [5].

Эволюционное программирование. Проиллюстрируем современное состояние данного подхода на примере системы PolyAnalyst. В дан­ной системе гипотезы о виде зависимости целевой переменной от других переменных формулируются в виде программ на некотором внутреннем языке программирования. Процесс построения программ строится как эволюция в мире программ (этим подход немного по­хож на генетические алгоритмы). Когда система находит программу, достаточно точно выражающую искомую зависимость, она начинает вносить в нее небольшие модификации и отбирает среди построен­ных таким образом дочерних программ те, которые повышают точ­ность. Таким образом, система «выращивает» несколько генетических линий программ, которые конкурируют между собой в точности вы­ражения искомой зависимости. Специальный транслирующий модуль системы PolyAnalyst переводит найденные зависимости с внутреннего языка системы на понятный пользователю язык (математические формулы, таблицы и пр.), делая их легкодоступными. Для того что­бы сделать полученные результаты еще понятнее для пользовате-ля-нематематика, имеется богатый арсенал разных средств визуализа­ции обнаруживаемых зависимостей. Для контроля статистической значимости выводимых зависимостей применяется набор современ­ных методов, например рандомизированное тестирование.

Другое направление эволюционного программирования связано с поиском зависимости целевых переменных от остальных в форме функций какого-то определенного вида. Например, в одном из наи­более удачных алгоритмов этого типа — методе группового учета ар­гументов (МГУА) зависимость ищут в форме полиномов.

Тенетические алгоритмы. Строго говоря, Data Mining — далеко не основная область применения генетических алгоритмов. Их нужно

279

И. И. Мазур, В. Д. Шапиро. Управление качеством

р ассматривать скорее как мощное средство решения разнообразных комбинаторных задач и задач оптимизации. Тем не менее, генетиче­ские алгоритмы вошли в стандартный инструментарий методов Data Mining и поэтому включены в данный обзор.

Пусть нужно найти решение задачи, оптимальное с точки зрения не­которого критерия. Пусть каждое решение полностью описывается некото­рым набором чисел или величин нечисловой природы. Скажем, если нуж­но выбрать совокупность фиксированного числа параметров рьшка, наибо­лее выраженно влияющих на его динамику, это будет набор имен этих параметров. Об этом наборе можно говорить как о совокупности хромо­сом, определяющих качества индивида — данного решения поставленной задачи. Значения параметров, определяющих решение, будут тогда назы­ваться генами. Поиск оптимального решения при этом похож на эволю­цию популяции индивидов, представленных их наборами хромосом. В этой эволюции действуют три механизма: отбор сильнейших — наборов хромосом, которым соответствуют наиболее оптимальные решения; скре­щивание — производство новых индивидов при помощи смешивания хро­мосомных наборов отобранных индивидов; мутации — случайные измене­ния генов у некоторых индивидов популяции. В результате смены поко­лений в конце концов вырабатывается такое решение поставленной задачи, которое уже не может быть далее улучшено.

Генетические алгоритмы имеют ряд недостатков. Критерий отбора хромосом и сама процедура являются эвристическими и далеко не гарантируют нахождения лучшего решения. Как и в реальной жиз­ни, эволюцию может «заклинить» на какой-либо непродуктивной вет­ви. И, наоборот, можно привести примеры, как два неперспективных родителя, которые будут исключены из эволюции генетическим алго­ритмом, оказываются способными произвести высокоэффективного потомка. Это особенно становится заметно при решении высокораз­мерных задач со сложными внутренними связями. Примером может служить система GeneHunter фирмы Ward Systems Group.

Алгоритмы ограниченного перебора. Алгоритмы ограниченного перебора были предложены в середине 70-х годов XX в. М.М. Бон-гардом для поиска логических закономерностей в данных. С тех пор они продемонстрировали свою эффективность при решении множест­ва задач из самых разных областей.

Эти алгоритмы вычисляют частоты комбинаций простых логиче­ских событий в подгруппах данных. Примеры простых логических событий: Х = а; Х<а; Х> а; а < X > b и др., где X — какой-либо параметр, а и b — константы. Ограничением служит длина комбина­ции простых логических событий. На основании анализа вычислен­ных частот делается заключение о полезности той или иной комбина­ции для установления ассоциации в данных, для классификации, прогнозирования и пр.

Наиболее яркий современный представитель этого подхода — сис­тема WizWhy предприятия WizSoft, являющаяся одним из лидеров на рынке продуктов Data Mining. Это связано с тем, что система по-

280