Содержание к диссертации
Введение
ГЛАВА 1. CRM-стратегия в телекоммуникациях 10
1.1. Применение CRM для персонификации клиентов 10
1.2. Биллинговая система: описание, назначение, функции 14
1.2.1. Процедуры тарификации и биллинга 14
1.2.2. Структура и функции биллинговой системы 15
1.2.3. История развития биллимговых систем 16
1.2.4. Тенденции и перспективы развития биллинговых систем 18
1.2.5. Требования, предъявляемые к современным биллинговым системам 19
1.2.6. Характеристика современного рынка биллинговых систем 20
1.3. Выводы 20
ГЛАВА 2. Технология data mining - аналитический инструментарий CRM-систем 22
2.1. Определение Data Mining 22
2.2. Процесс обнаружения новых знаний с помощью технологии Data Mining 25
2.3. Классы систем Data Mining 27
2.4. Модели Data Mining 37
2.5. Задачи Data Mining 37
2.6. Классификация и регрессия 39
2.6.1 Постановка задачи 39
2.6.2. Представление результатов 40
2.6.3. Деревья решений 42
2.7. Кластеризация 43
2.7.1. Алгоритмы кластеризации 44
2.8. Поиск ассоциативных правил (ограниченный перебор) 45
2.8.1. Постановка задачи 45
2.8.2. Алгоритмы поиска ассоциативных правил 48
2.8.3. Сиквенциальный анализ 49
2.9. Примеры практического применения Data Mining 50
2.10. Data Mining в телекоммуникациях 51
2.11. Выводы 54
ГЛАВА 3. Анализ перспективности использования алгоритмов деревьев решений и ассоциативных правил для прогнозирования оттока клиентов 56
3.1. Постановка задачи 56
3.2. Моделирование базы данных персонифицированного трафика клиентов 56
3.3. Краткое описание программы моделирования баз данных персонифицированного трафика
(«Генератор») 65
3.3.1. Рабочее окно программы 65
3.3.2. Алгоритм работы программы «Генератор» 66
3.4. Прогноз лояльности потенциального клиента при помощи алгоритма поиска ассоциативных правил (алгоритм Apriori - система WizWhy) 67
3.5. Прогноз лояльности потенциального клиента при помощи алгоритма деревьев решений 76
3.5.1. Выбор типа алгоритма деревьев решений 77
3.5.2. Бинарное дерево решений (алгоритм CART) 78
3.5.3. Не бинарное дерево решений (алгоритмы ЮЗ и С4.5) 87
3.5.4. Прогноз лояльности потенциального клиента 97
3.6. Выводы 101
ГЛАВА 4. Разработка системы поддержки принятия решений для прогнозирования оттока клиентов на основе технологии Data Mining 103
4.1. Описание разработанного алгоритма и системы «Forecaster» 103
4.2. Структура рабочего окна системы Forecaster 107
4.3. Пример прогнозирования лояльности потенциального клиента системой Forecaster
4.4. Сравнение систем WizWhy и Forecaster 112
4.5. Выводы 114
Заключение 116
Библиографический список использованной литературы 167
- Применение CRM для персонификации клиентов
- Определение Data Mining
- Моделирование базы данных персонифицированного трафика клиентов
- Описание разработанного алгоритма и системы «Forecaster»
Введение к работе
В настоящее время наблюдается интенсивное развитие телекоммуникационных систем, сопровождающееся жёсткой конкурентной борьбой за клиента. При таком состоянии рынка телекоммуникационных услуг, одной из главных проблем компаний-операторов является отток клиентов (churn) [66]. Традиционные способы предотвращения вышеуказанного явления (ценовые войны и массовая реклама) уже не эффективны. Поэтому, в последние годы для привлечения и удержания клиентов всё чаще используется концепция CRM (Customer Relationship Management - Управление Взаимоотношениями с Клиентами; её основателями являются Д. Пепперс, М. Роджерс и Ф. Райчхелд).
Вероятность того, что клиент откажется от услуг компании определяется его лояльностью (loyalty) компании [34]. Чтобы спрогнозировать этот показатель необходимо выявить скрытые закономерности между лояльностью и персонифицированным трафиком, который содержит личностные характеристики клиента. В CRM, анализ данных, направленный на выявление скрытых закономерностей, реализуется при помощи методов современной информационной технологии Data Mining (Интеллектуальный Анализ Данных). Одним из её основателей является Г. Пиатецкий-Шапиро. Data Mining является мультидисциплинарной областью, возникшей и развивающейся на основе достижений статистики, распознавания образов, методов искусственного интеллекта, теории баз данных и др. Большой вклад в развитие внесли работы М. Бонгарда, Ф. Розенблатта, Мак-Каллока, Питса, Е.Фикса, Д. Ходжеса, Г.С. Лбова, Фогеля (Fogel), Уолша (Walsh), А.Г. Ивахненко, Бреймана (Breiman), Рипли (Repley), Фрейдмана (Freidman), Олшена (Olshen), Стоуна (Stone).
В настоящее время различные методы технология Data Mining (алгоритмы поиска ассоциативных правил, нейронные сети, деревья
решений, эволюционные алгоритмы и т.д.) широко применяются для прогнозирования лояльности клиентов в телекоммуникационных компаниях. Наиболее известными являются разработки Сриканта Рамакришнана (Ramakrishnan Srikant), Ракеша Агравала (Rakesh Agraval), А. Мейдана, Б. де Виля, В. Дюка, М. Куприянова, В. Степаненко, а также компаний SPSS, StatSoft, WizSoft, Megaputer, BaseGroup, Integral Solutions, Microsoft. Однако эти разработки обладают недостатками (невысокая точность прогнозов, низкая скорость работы, высокая стоимость), что не позволяет широко и в полной мере использовать их для прогнозирования лояльности клиентов. Кроме того, низкая скорость работы препятствуют применению существующих аналитических систем для прогнозирования лояльности на этапе заключения договора с клиентом (обработка данных и формирование прогноза должны производится в реальном масштабе времени). В связи с этим, решение проблемы прогнозирования оттока клиентов в телекоммуникационных системах, является актуальной.
Объектом исследования является персонифицированный трафик клиентов телекоммуникационной компании-оператора.
Целью работы является разработка методов прогнозирования оттока клиентов в телекоммуникациях с использованием технологии Data Mining (интеллектуального анализа данных).
Для достижения поставленной цели требуется решить следующие задачи:
Разработать имитационную модель для генерации баз данных на основе выявления скрытых закономерностей.
Выявить наиболее перспективные алгоритмы технологии Data Mining для анализа персонифицированного трафика.
Проанализировать выявленные алгоритмы с целью определения лучшего из них.
Модифицировать выбранный алгоритм для обеспечения большей скорости и точности прогноза.
Разработать программное обеспечение системы поддержки принятия решений относительно лояльности клиента, реализующей модифицированный алгоритм.
Провести сравнительный анализ разработанной системы с существующими, построенными на базе алгоритмов Data Mining.
Методы исследования
Основные теоретические и экспериментальные исследования диссертационной работы выполнены с применением методов комбинаторного анализа, математической статистики, деревьев решений, ограниченного перебора; статистического пакета STATISTICA 6.0 (StatSoft); аналитических систем WizWhy 3.08 (WizSoft) и Deductor (BaseGroup).
Научная новизна заключается в следующем:
Разработана имитационная модель, генерирующая базу данных прецедентов на основе выявления скрытых закономерностей.
Предложен новый алгоритм определения лояльности клиента, созданный на основе расслоения базы данных прецедентов с использованием трёх количественных критериев: поддержка (support), достоверность (confidence) и улучшение (improvement).
Разработано программное обеспечение системы поддержки принятия решений относительно лояльности клиента, реализующей алгоритм расслоения.
Практическая ценность работы
Разработана система поддержки принятия решений, позволяющая прогнозировать лояльность потенциального клиента по его личностным характеристикам (для различных тарифных планов) на этапе заключения договора.
Реализация результатов работы
Разработанный в работе алгоритм определения лояльности клиента, а также программное обеспечение системы поддержки принятия решений относительно лояльности клиента приняты к использованию Самарским филиалом ОАО «ВолгаТелеком», внедрены в учебный процесс в Поволжской государственной академии телекоммуникаций и информатики г.Самара; система поддержки принятия решений «Forecaster» зарегистрирована в отраслевом фонде алгоритмов и программ Государственного координационного центра информационных технологий.
Апробация работы
Отдельные законченные этапы работы докладывались и обсуждались на международном форуме «Новые инфокоммуникационные технологии: достижения, проблемы, перспективы» (Новосибирск, 2003), 5й многопрофильной международной конференции молодых учёных и студентов «Актуальные проблемы современной науки» (Самара, 2004), 5й международной научно-технической конференции «Проблемы техники и технологии телекоммуникаций» (Самара, 2004), международной научно-практической конференции «Экономика и менеджмент: проблемы и перспективы» (Санкт-Петербург, 2005), 10й (2003 г.), 11й (2004 г.) и 12й (2005 г.) Российских научных конференциях профессорско-
преподавательского состава, научных сотрудников и аспирантов (Самара), межвузовском научно-практическом семинаре «Экономика и конкурентоспособность России» (Санкт-Петербург, 2004).
Публикации
Основное содержание диссертации отражено в 11 опубликованных работах. Публикации включают 3 статьи в научных изданиях и 8 материалов докладов.
На защиту выносятся:
Алгоритм прогнозирования лояльности клиентов телекоммуникационной компании-оператора.
Система поддержки принятия решений относительно лояльности клиента, построенная на базе вышеуказанного алгоритма.
Результаты сравнительного анализа работы разработанной и существующей систем прогнозирования.
Структура и объём работы
Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложений. Основная часть работы содержит 117 страниц машинописного текста, 28 рисунков, 18 таблиц. Список литературы содержит 94 наименования.
Первая глава посвящена краткому обзору стратегии управления взаимодействием с клиентами (CRM) и одного из её компонент -биллинговой системы.
Вторая глава посвящена аналитическому обзору технологии интеллектуального анализа данных (Data Mining), используемой для анализа персонифицированного трафика (прогнозирования лояльности клиентов).
Третья глава содержит описание структуры моделируемой базы данных персонифицированного трафика клиентов (прецедентов) телекоммуникационной компании и имитационной модели (программа «Генератор»), которая генерирует вышеуказанную базу данных на основе выявления скрытых закономерностей. Здесь также приведено описание сравнительного анализа перспективности использования алгоритмов деревьев решений и ассоциативных правил (алгоритмов ограниченного перебора) для прогнозирования оттока клиентов.
Четвёртая глава посвящена описанию алгоритма определения лояльности клиента, созданного на основе расслоения базы данных прецедентов, разработанной системы поддержки принятия решений, реализующей алгоритм расслоения и сравнительному анализу двух систем прогнозирования.
В заключении сформулированы результаты работы.
Применение CRM для персонификации клиентов
В настоящее время «обычные» методы повышения лояльности (и удержания) старых и привлечения новых клиентов (массовая реклама, традиционный маркетинг, низкие цены) не оказывают должного положительного воздействия. Именно поэтому во всём мире приоритетными становятся концепции, позволяющие осуществлять персонифицированные продажи товаров и услуг.
Примером может служить Customer Relationship Management (CRM) -Управление Взаимоотношениями с Клиентами [32, 33]. CRM не является технологией или программным продуктом. Это бизнес-стратегия, в основе которой лежит клиентоориентированный (customer-oriented) [64, 28] подход, т.е. можно сказать, что основная задача CRM - повышение эффективности бизнес-процессов, направленных на привлечение и удержание клиентов, независимо от канала, через который происходит контакт с клиентом [1, 40].
Технологически, CRM-система - это совокупность программных продуктов, связанных в единое целое и интегрируемых в информационную среду компании.
Стратегия управления взаимоотношениями с клиентами окончательно сформировалась в середине 90-х гг. прошлого века. Она появилась в результате развития таких технологий и систем, как [1].: - Систем сбора информации о клиентах, частично включавших зачатки SAP (Sales Force Automation) - Автоматизация деятельности торговых представителей. - Маркетинговых баз данных, обеспечивавших анализ продукта на уровне продукта (его продаж), но слабо интегрированных с источниками другой информации. - Систем доставки информации до клиента (прямая почтовая рассылка и т.д.). - Базовых аналитических инструментов, использовавшихся для анализа поведения покупателя при покупке, но без учёта его жизненного цикла и др.
Любая CRM-система обладает следующими основными функциями [53]: - Сбор информации. Данные такого вида могут вводиться как самим клиентом (интернет-магазин) так и регистрироваться сотрудниками компании. Как правило, в систему поступают все доступные реквизиты сделки (описание купленного товара, цена, количество, цель покупки, вид оплаты) и клиента (возраст, семейное положение, ежегодный доход, имущество, и т.д.). - Хранение, обработка информации и её анализ для последующего экспорта в соответствии с заданными критериями. - Предоставление информации пользователям (текст, таблицы, графики, рекомендации, напоминания). Выполнение CRM-системой вышеуказанных функций сопровождается процессами, которые представлены на рис. 1.1.
Системы управления взаимоотношениями с клиентами по способу использования подразделяются на три класса: - Системы оперативного использования. Применяются для повседневных управленческих целей. - Аналитические системы. Используются маркетологами для обработки больших объёмов данных (как правило, о клиентах) с целью получения новых знаний.
Коллаборационные системы. Позволяют клиенту влиять на деятельность фирмы в целом тем или иным образом (в том числе на процессы разработки, производства, доставки и обслуживания товара).
Определение Data Mining
Технологией, с помощью которой реализуются аналитические функции CRM-систем, в большинстве случаев, является технология Data Mining (Интеллектуальный Анализ Данных) [78, 73, 82, 79, 35, 65, 72, 41, 42, 43].
Стремительное накопление данных (базы и хранилища данных по клиентам, услугам и операциям), всеобщая компьютеризация бизнес-процессов, появление Internet, как ещё одного источника информации и канала взаимодействия с клиентами, технологический прогресс: стремительный рост производительности вычислительной техники, объёмов накопителей, совершенствование СУБД, хранилищ данных [76] - всё это привело к образованию огромных массивов данных (см. рис. 2.1.) [92].
Использование традиционной математической статистики для поиска в них полезной информации не увенчалось успехом. Главная причина этого -концепция усреднения по выборке, приводящая к операциям над фиктивными величинами (например, средняя температура пациентов в больнице). Методы математической статистики оказались полезными главным образом для проверки заранее сформулированных гипотез [63]. В основу же современной технологии Data Mining положена концепция шаблонов (паттернов), отражающих фрагменты многоаспектных взаимоотношений в данных. Эти фрагменты представляют собой закономерности, свойственные подвыборкам данных, которые могут быть компактно выражены в понятной человеку форме. Поиск шаблонов производится методами, не ограниченными рамками априорных предположений о структуре выборки и виде распределений значений анализируемых показателей [21].
Всё вышесказанное не означает, что интеллектуальный анализ данных возник сразу, как только появились современные компьютеры и образовались огромные «залежи» данных: Data Mining - результат постепенного совершенствования технологий сбора, хранения и обработки данных, а также изменения приоритетов в бизнесе (от массового обслуживания - к персональному) [1]; это можно проиллюстрировать следующей таблицей (см. таблицу 2.1.)[81]:
Существуют различные определения Data Mining [69]:
- Data Mining - это процесс выделения из данных неявной и неструктурированной информации и представления её в виде, пригодном для реализации;
- Data Mining - это процесс анализа, выделения и представления детализированных (detailed data) данных неявной конструктивной информации для решения проблем бизнеса;
- Data Mining - это процесс выделения (selecting), исследования и моделирования больших объёмов данных для обнаружения неизвестных до этого структур (patterns) с целью достижения преимущества в бизнесе (SAS Institute);
- Data Mining - это процесс, цель которого - обнаружить новые значимые корреляции, образцы и тенденции в результате просеивания большого объёма хранимых данных с использованием методик распознавания образцов плюс [применение] статистических и математических методов (Gartner Group);
- Data Mining - это процесс автоматического выделения действительной, эффективной, ранее не известной и совершенно понятной информации из больших баз данных и использование её для принятия ключевых бизнес-решений и т.д., но в главном они совпадают, поскольку содержат четыре основных признака, которые присутствуют в лучшем, на мой взгляд, определении, которое дал технологии Data Mining один из её основателей Григорий Пиатецкий-Шапиро [38]:
Data Mining - это процесс обнаружения в сырых данных: ранее неизвестных; нетривиальных; практически полезных; доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности.
Моделирование базы данных персонифицированного трафика клиентов
Компании-операторы нечасто используют базы данных, которые содержат персонифицированную информацию о клиентах (их личностные характеристики и персональный трафик); кроме этого, информация такого рода является конфиденциальной. Поэтому возникла необходимость моделирования подобной базы данных.
Между личностными характеристиками и персональным трафиком существуют скрытые зависимости, которые имеют нечёткий характер и, поэтому, трудно формализуемы. Для выявления скрытых закономерностей фрагмент реальной базы данных (предоставлен российской телекоммуникационной компанией) был проанализирован при помощи алгоритма ограниченного перебора, который принадлежит к методам технологии интеллектуального анализа данных.
В результате было выявлено 275 значимых закономерностей (правил), которые имеют следующую структуру: ЕСЛИ (JIXeL) ТО (ПТ), где ЛХ — личностные характеристики клиента; ПТ— персональный трафик клиента; L -набор личностных характеристик.
Атрибуты личностных характеристик и персонального трафика могут принимать значения указанные в таблицах 3.1 и 3.2.
Ежемесячная абонентская плата (городской номер) - 0 руб. Ежемесячная минимальная оплата за трафик (включает 1000 минут местных вызовов) - 800 руб. Стоимость одной минуты:
Исходящие вызовы на мобильный телефон: 4 руб. (день);
4 руб. (ночь). Исходящие местные вызовы: 4 руб. (день); 4 руб. (ночь). Входящие вызовы с мобильного телефона: бесплатно.
Входящие остальные: 1 руб. (день); 1 руб. (ночь). Исходящее SMS: 0,98 руб. (за сообщение) Входящее SMS: бесплатно. Передача данных (9600 бит/с.) (день): 1,47 руб. Передача данных (9600 бит/с.) (ночь): 0,49 руб.
Пример для расчёта ПТ0 для тарифного плана «Тарифі» приведён ниже: «Тарифі» (руб.) = 83.58 + 4.42 Исходящие вызовы па мобильный телефон (день) в месяц + 2.45 Исходящие вызовы на мобильный телефон (ночь) в месяц + 4.42 Исходящие местные вызовы (день) в месяц + 2.45 Исходящие местные вызовы (ночь) в месяц + 4.42 Входящие остальные (день) в месяц + 2.45 Входящие остальные (ночь) в месяц + 0.98 Исходящее SMS в месяц + \Л1 Передача данных (9600 бит/с.) (день) в месяц + 0.47 Передача данных (9600 бит/с.) (ночь) в месяц.
Предоплата {ПТЇ) задаётся тарифным планом.
Атрибут ПТд (общее время за месяц) определяется следующим образом: ПТд = ПТ„. Средняя продолжительность разговора {ПТИ) и=2 определяется так: ПТи = ПТ9/ПТ10.
На основании выявленных значимых закономерностей было сформировано 75 ассоциативных правил установления связей между личностными характеристиками клиента и его персональным трафиком. Они имеют следующую структуру:
ЕСЛИ {ЛХХ =Лх)и (ЛХ2 =Л2)и (ЛХ3 =Л3)и (ЛХ4 =Л4)и (ЛХ5 =Л5)и (ЛХ6=Л6)и(ЛХ7=Л7) ТО {ПТй = П0)и(ПТХ = Я,) и(ПТ2 = Я2)и (ПТ3 = Я3)и(ЯГ4 = Я4)и (ПТ5 = Я5) и (ПТ6 = Я6) и (ПТ7 =П7)и {ПТ& = Я8) и {ПТ9 = Пд) и {ПТ]0 =П10)и {ПТи =Пи)и {ПТП = Я12) и (ПТ„ = Я13) и (ПТи = Я14) и {ПТ15=П15\ где Л,,..., JI-j - значения атрибутов личностных характеристик клиентов; Я0,..., Я15 - значения атрибутов персонального трафика клиентов.
Ниже приведен пример правила установления связей:
Если (Доход в месяц = высокий) и {(Работа = работает и учится) или (Работа - работает)) и ({Образование = специальное) или (Образование = высшее) или (Образование - учёная степень)) и (Дети = 1) и (Пол = женский) и (Семейное положение = состоит в браке) и {{Возраст - 20-30 лет) или (Возраст = 30-40 лет) или (Возраст = 40 50 лет) или (Возраст = 50-60 лет) или (Возраст = более 60 лет)) то Исходящие вызовы на мобильный телефон (день), мин = 40 + Random(61);
Исходящие вызовы на мобильный телефон (ночь), мин.= 60 + Random(61);
Исходящие местные вызовы (день), мин = 50 + Random(41); Исходящие местные вызовы (ночь), мин = 70 + Random(51); Входящие вызовы с мобильного телефона, мин = ((1500 - ({Исходящие вызовы на мобильный телефон (день) + Исходящие вызовы на мобильный телефон (ночь)) + (Исходящие местные вызовы (день) + Исходящие местные вызовы (ночь)))) / 3) + Random((500 - ((Исходящие вызовы на мобильный телефон (день) + Исходящие вызовы на мобильный телефон (ночь)) + (Исходящие местные вызовы (день) + Исходящие местные вызовы (ночь))) 13);
Входящие остальные (день) в месяц, мин.- ((1500 - {(Исходящие вызовы на мобильный телефон (день) + Исходящие вызовы на мобильный телефон (ночь) + (Исходящие местные вызовы (день) + Исходящие местные вызовы (ночь)))) / 3) + Random((500 - ((Исходящие вызовы на мобильный телефон (день) + Исходящие вызовы на мобильный телефон (ночь) + (Исходящие местные вызовы (день) + Исходящие местные вызовы (ночь)))) 13);
Входящие остальные (ночь) в месяц, мин.= ((1500 - ((Исходящие вызовы на мобильный телефон (день) + Исходящие вызовы на мобильный телефон (ночь)+ (Исходящие местные вызовы (день) + Исходящие местные вызовы (ночь)))) / 3) + Random(500 - ((Исходящие вызовы на мобильный телефон (день) + Исходящие вызовы на мобильный телефон (ночь) + (Исходящие местные вызовы (день) + Исходящие местные вызовы (ночь)))) 13);
Также было сформировано 60 правил определения лояльности клиента. Лояльность интерпретируется как вероятность того, что клиент не откажется от услуг компании (может принимать значения в диапазоне от 0 до 100 %). Она определяется на основании персонифицированного трафика клиента и длительности пребывания клиента в компании. Правила определения лояльности клиента имеют следующую структуру: ЕСЛИ (Т) И ((ПТ0 Х{) и (ПТо Щ ТО «Лояльность» = {100 - (U + Random(L )) %}, где Т -длительность пребывания клиента в компании, лет; ПТо - размер абонентской платы; Х\ и JG - некоторые пороговые значения абонентской платы; Lj и Д? - параметры, определяющие диапазон для генератора случайных чисел (Random) (см. табл. 3.3).
Описание разработанного алгоритма и системы «Forecaster»
Вектор переменных-предикторов, подаваемый на вход дерева, может содержать как числовые (непрерывные) так и категориальные переменные. В любом случае в каждом узле разбиение производится только по одной переменной. Если переменная числового типа, то в узле формируется правило вида х, с, где с - некоторый порог, который чаще всего выбирается как среднее арифметическое двух соседних упорядоченных значений переменной xt обучающей выборки. Если переменная категориального типа, то в узле формируется правило xieV(xi), где v{xi) - некоторое непустое подмножество множества значений переменной х,. Следовательно, для п значений числового атрибута алгоритм сравнивает п-\ разбиений, а для категориального - (2""l-l). На каждом шаге построения дерева алгоритм последовательно сравнивает все возможные разбиения для всех атрибутов и выбирает наилучший атрибут и наилучшее разбиение для него.
Нередко итогом работы алгоритмов деревьев решений являются сложные для понимания «ветвистые» деревья, содержащие много ветвей и узлов. В результате исследуемые данные разбиваются на очень большое количество подмножеств, которые включают в себя по нескольку элементов. Ценность правил, получаемых в результате использования такого дерева для анализа, может оказаться крайне низкой. Чтобы получить дерево, обладающее максимально возможной точностью классификации при минимальной его глубине («ветвистости»), используется так называемое отсечение ветвей (pruning). Пусть под точностью дерева решений понимается отношение правильно классифицированных объектов при обучении к общему количеству объектов из обучающего множества, а под ошибкой -количество неправильно классифицированных. Тогда, если известен способ оценки ошибки дерева, ветвей и листьев, можно использовать следующее правило: - построить дерево; - отсечь или заменить поддеревом те ветви, которые не приведут к возрастанию ошибки.
В большинстве практических задач отсечение даёт хорошие результаты, что позволяет говорить о правомерности использования подобной методики.
В CART вышеуказанная процедура реализована иначе, чем в не бинарных алгоритмах. Она носит название «отсечение дерева» (minimal cost-complexity tree pruning). Суть отсечения дерева заключается в нахождении компромисса между получением дерева оптимального размера и точной оценки вероятности ошибочной классификации. Главная проблема отсечения - большое число всех возможных отсечённых поддеревьев для одного дерева (например, если бинарное дерево имеет г- листов, то тогда существует «[l.5028369 rJ отсечённых поддеревьев).
Базовая идея метода - не рассматривать все возможные поддеревья, ограничившись только «лучшими представителями» согласно приведённой ниже оценке.
Обозначим \т\ - число листов дерева, R(T) - ошибка классификации дерева, равная отношению числа неправильно классифицированных примеров к числу примеров в обучающей выборке. Определим Са(т) полную стоимость (оценку/показатель затраты-сложность) дерева Г как:
Ca(T)=R(T)+a-\T\, где г - число листов дерева, а - некоторый параметр, изменяющийся от 0 до +оо. Полная стоимость дерева состоит из двух компонент - ошибки классификации дерева и штрафа за его сложность. Если ошибка классификации дерева неизменна, то с возрастанием а полная стоимость дерева будет увеличиваться. Тогда, в зависимости от а, менее ветвистое дерево, дающее большую ошибку классификации может стоить меньше, чем дающее меньшую ошибку, но более ветвистое. Определим Ттт максимальное по размеру дерево, у которого предстоит отсечь ветви. Если зафиксировать значение а, тогда существует наименьшее минимизируемое поддерево, которое выполняет следующие условия:
1. Са (т(а)) = minrs Tmm Са (т) - не существует такого поддерева дерева Гтах, которое имело бы меньшую стоимость, чем т(а) при этом значении а.
2. Если Са (т) = Са (т(а)) то т(а) Т - если существует более одного поддерева, имеющего данную полную стоимость, то тогда выбирается наименьшее дерево.
Можно показать, что для любого значения а существует такое наименьшее минимизируемое поддерево. Но эта задача не тривиальна. Она говорит, что не может быть такой ситуации, когда два дерева достигают минимума полной стоимости и они несравнимы, т.е. ни одно из них не является поддеревом другого. В данной работе этот результат доказываться не будет. Хотя а имеет бесконечное множество значений, существует конечное множество поддеревьев Гтах. Можно построить последовательность уменьшающихся поддеревьев дерева Гтах: Г, Т2 Т3 ... { ,}, (где /, корневой узел дерева) такую, что Тк - наименьшее минимизируемое поддерево для ае[ак,ак+1).
Похожие диссертации на Анализ и прогнозирование оттока клиентов в телекоммуникационных компаниях на основе технологии Data Mining
