Содержание к диссертации
Введение
ГЛАВА 1. Телекоммуникационный трафик в биллинговых системах 9
1.1. Обзор биллинговых систем 9
1.2. Основные функции и архитектура биллинговых систем 14
1.3. Требования, предъявляемые кбиллинговым системам 16
1.4. Основные процессы и организация биллинга 19
1.5. Телекоммуникационный трафик и задачи аналитического управления .25
1.6. Выводы 30
ГЛАВА 2. Классификация методов выявления скрытых закономерностей применительно к телекоммуникационному трафику 31
2.1. Определение Data Mining 31
2.2. Классификация задач Data Mining 32
2.3. Этапы исследования данных с помощью методов Data Mining 35
2.4. Методы Data Mining 37
2.4.1. Кластеризация 37
2.4.2. Ассоциация 38
2.4.3. Деревья решений 39
2.4.4. Метод «ближайших соседей» 40
2.4.5. Нейронные сети 41
2.4.6. Нечеткая логика 42
2.4.7. Генетические алгоритмы 43
2.4.8. Эволюционное программирование 44
2.4.9. Визуализация 45
2.5. Практическое использование Data Mining в телекоммуникационных системах 46
2.6. Выводы 49
ГЛАВА 3. Регрессионно-когнитивные модели для анализа биллинговых систем 50
3.1. Концепция когнитивного моделирования 50
3.2. Регрессионно-когнитивные модели (РКМ) 59
3.3. Регрессионный анализ телекоммуникационных данных 68
3.4. Поиск решения для РКМ 78
3.5. Выводы 81
ГЛАВА 4. Оценка взаимовлияний и прогнозирование объемов телекоммуникационных услуг на основе РКМ ... 83
4.1. Процесс сегментирования в телекоммуникациях 83
4.2. Прогнозирование объемов телекоммуникационных услуг на основе РКМ85
4.2.1. РКМ для прогнозирования объема трафика телекоммуникационной компании 85
4.2.2. РКМ для прогнозирования объема трафика телекоммуникационной компании с учетом фактора времени 98
4.2.3. РКМ для прогнозирования объемов трафика клиентов телекоммуникационной компании 108
4.3. Выводы 124
Заключение 125
- Требования, предъявляемые кбиллинговым системам
- Этапы исследования данных с помощью методов Data Mining
- Регрессионный анализ телекоммуникационных данных
- РКМ для прогнозирования объема трафика телекоммуникационной компании
Введение к работе
Количество видов телекоммуникационных услуг постоянно растет, а их объемы варьируются от клиента к клиенту, изменяются во времени, подвержены сезонным изменениям и т.п. Взаимосвязи между объемами услуг разных видов неочевидны: существуют ли скрытые связи между услугами, какова «сила» этих связей и к чему приведут возможные изменения объемов оказываемых услуг. Ответ на эти и подобные вопросы имеет вполне определенное практическое значение, позволяющее предсказать изменение объемов и, соответственно, экономические эффекты, свойственные той или иной ситуации, складывающейся на рынке телекоммуникационных услуг.
Одна из современных технологий анализа данных, направленная на выявление скрытых закономерностей, реализуется при помощи методов современной информационной технологии Data Mining (Интеллектуальный Анализ Данных). Одним из её основателей является Г. Пиатецкий-Шапиро. Data Mining является мультидисциплинарной областью, возникшей и развивающейся на основе достижений статистики, распознавания образов, методов искусственного интеллекта, теории баз данных и др. Большой вклад в развитие внесли работы М. Бонгарда, Ф. Розенблатта, Мак-Каллока, Питса, Е.Фикса, Д. Ходжеса, Г.С. Лбова, Фогеля (Fogel), Уолша (Walsh), А.Г. Ивахненко, Бреймана (Breiman), Рипли (Repley), Фрейдмана (Freidman). Наиболее рельефно возможности ИАД характеризуют механизмы классификации данных и выявления цепочек. Классификация позволяет выявить классообразующие признаки, по которым тот или иной объект можно отнести к заданному классу. Например, признаки устойчивости (надежности, стабильности) клиента. Выявление цепочек (событий или связанных факторов) позволяет установить связи между факторами, которые на первый взгляд не связаны друг с другом. Такие цепочки могут быть хронологическими или причинно-следственными, связи между элементами
цепочек могут определяться на различных основах: вероятностной, корреляционной, регрессионной и т.п.
В настоящее время различные методы технологии Data Mining широко применяются для анализа трафика в телекоммуникационных компаниях. Наиболее известными являются разработки Сриканта Рамакришнана (Ramakrishnan Srikant), А. Мейдана, Б. де Виля, В. Дюка, М. Куприянова, а также компаний SPSS, StatSoft, WizSoft, Megaputer, BaseGroup, Microsoft. Однако эти разработки обладают недостатками (невысокая точность прогнозов, низкая скорость работы, высокая стоимость), что не позволяет широко и в полной мере использовать их для прогнозирования объемов трафика предоставляемых услуг. Кроме того, невысокая точность прогноза препятствуют применению существующих аналитических систем для интеллектуального анализа данных и её использование в биллинговых системах для анализа объемов услуг, предлагаемых клиентам. В связи с этим, решение проблемы, связанной с перераспределением имеющихся ресурсов у компании-оператора в телекоммуникационных системах, является актуальным.
Объектом исследования является биллинговый файл
телекоммуникационной компании.
Целью работы является разработка метода анализа биллинговой системы в телекоммуникациях с использованием технологии Data Mining (интеллектуального анализа данных) для эффективного управления трафиком.
Для достижения поставленной цели требуется решить следующие задачи:
Провести анализ существующих биллинговых систем.
Выявить наиболее перспективные алгоритмы технологии Data Mining для анализа трафика биллинговой системы.
Проанализировать выявленные алгоритмы с целью определения лучшего из них.
Разработать алгоритм анализа и прогноза файла данных биллинговой системы.
Провести моделирование, основанное на предложенном алгоритме и реальных данных биллинговой системы, и сделать выводы на полученных результатах о целесообразности использования предложенной методологии.
Методы исследования
Основные теоретические и экспериментальные исследования диссертационной работы выполнены с применением методов математической статистики, когнитивного моделирования, регрессионного анализа; аналитической системы PolyAnalyst (Megaputer).
Научная новизна заключается в следующем:
Предложен новый алгоритм регрессионно-когнитивного моделирования, который позволит производить прогнозирование объема трафика телекоммуникационной компании на основе биллингового файла.
Практическая ценность работы
Представленное регрессионно-когнитивное моделирование позволит телекоммуникационным компаниям эффективно анализировать свои биллинговые файлы и выстраивать работу, ориентированную на качественное предоставление своих услуг клиентам и увеличение прибыли.
Реализация результатов работы
Разработанный в работе алгоритм регрессионно-когнитивного моделирования принят к использованию Самарским филиалом ОАО
«ВолгаТелеком», внедрен в учебный процесс в Поволжской государственной академии телекоммуникаций и информатики г. Самара.
Апробация работы
Основные результаты по теме диссертационного исследования докладывались на Международной научно-технической конференции "Проблемы техники и технологии телекоммуникаций" (Самара, 2006) . Научные и прикладные результаты диссертационной работы опубли-кованы в 5 статьях в периодических научных изданиях.
Публикации
Основное содержание диссертации отражено в 6 научных изданиях.
На защиту выносятся
модель прогнозирования объемов телекоммуникационных ус-луг, построенная на основе регрессионно-когнитивного анали-за;
алгоритм реализации вышеупомянутой модели применительно к реальным данным оператора связи;
результаты применения модели для прогнозирования объемов телекоммуникационных услуг.
Структура и объём работы
Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложений. Основная часть работы содержит 116 страниц машинописного текста, 44 рисунка, 3 таблицы. Список литературы содержит 82 наименования.
Первая глава посвящена краткому обзору биллинговой системы и телекоммуникационного трафика.
Вторая глава посвящена аналитическому обзору технологии интеллектуального анализа данных (Data Mining), используемой для анализа биллинговой системы.
Третья глава содержит описание предлагаемого алгоритма регрессионно-когнитивного моделирования (РКМ). Здесь также приведены основные принципы моделирования при помощи данной методологии, описаны системные подходы, связанные с прогнозированием объемов трафика телекоммуникационной компании на основе биллингового файла данных.
Четвёртая глава посвящена демонстрированию работы предлагаемой методологии РКМ на реальных данных биллинговой системы. Здесь получены конкретные результаты прогнозирования, на основе которых компания-оператор может выстраивать свою работу более эффективно. В заключении сформулированы результаты работы.
Требования, предъявляемые кбиллинговым системам
При выборе или создании биллинговой системы необходимо обращать внимание не только на функциональность, но и на технологии, используемые при разработке [22, 23] (рисунок 1.2). Отказоустойчивость
Требования, предъявляемые к биллинговым системам
Одним из основных требований для биллинговой системы является масштабируемость. Программная часть системы не должна требовать переделок и доработок при увеличении нагрузки на систему (при увеличении числа клиентов, множества тарифных планов, сервисов и клиентских транзакций3). Увеличение возможностей должно достигаться расширением аппаратной части (добавлением задействованных процессоров, расширением дискового пространства). При этом между нагрузкой и быстродействием системы должна быть обеспечена зависимость, которую можно спрогнозировать. Принципы построения масштабируемых систем таковы:
- использование СУБД, рассчитанных на большие объемы данных;
- совместимость СУБД с различными компьютерными платформами;
- поддержка многопроцессорного режима работы;
- централизация основных расчетов и процедур доступа к данным на сервере баз данных;
- увеличение нагрузки должно ложиться в основном на серверную часть.
Особую важность имеет надежность данных, а именно: их актуальность, целостность и достоверность. В систему должны быть заложены механизмы, которые бы обеспечивали эти свойства. Для достижения этой цели необходимо:
- создание непротиворечивой модели данных;
- возможность отката транзакций при ошибке или невозможности закончить транзакцию корректно.
При авариях, сбоях, потери данных система должна иметь средства для быстрого восстановления работоспособности, то есть обеспечивать отказоустойчивость, основными методами которой являются:
- резервирование и копирование данных;
- наличие резервирующих серверов;
- распределенная структура базы данных.
Важнейшим качеством биллинговой системы является ее гибкость [24], то есть способность приспосабливаться к изменившимся обстоятельствам. Система должна иметь возможность настраиваться, дорабатываться, адаптироваться для решения задач оператора, которые, в частности, могут быть не совсем ясны на момент разработки. Обеспечить гибкость можно с помощью таких качеств системы как настраиваемость, модульность и открытость.
Настраиваемость — это возможность увеличения функциональности системы без ее доработки.
Модульность обеспечивается выделением в системе подсистем с четко описанными интерфейсами между ними. Модульность более низкого уровня обеспечивается выделением в модулях функций или иных программно-информационных единиц. Разделение системы на функциональные модули позволяет развивать, наращивать или изменять функции системы, поддерживающие любой этап процесса обслуживания, независимо от остальных. Модульность является основой для создания переносимой системы, преимущество которой заключается в возможности использовать технологию разделенных серверов.
Открытость системы заключается в том, что форматы данных и интерфейсы удовлетворяют неким специфицированным стандартам. Это свойство позволяет заменять одни модули системы другими, а также подключать внешние системы по стандартным протоколам.
Также система должна иметь возможность работать на различных платформах, с разными СУБД, что обеспечивает переносимость биллинговой системы. Это, во-первых, делает ее более масштабируемой (система будет устойчиво работать при использовании более мощного сервера, более производительной СУБД), во-вторых, более гибкой (работать на том оборудовании и с тем программным обеспечением, которое уже есть у оператора). Переносимость системы может также косвенным- образом влиять на повышение ее отказоустойчивости (распределение функций по разным машинам, использование распределенных или реплицированных баз данных).
Этапы исследования данных с помощью методов Data Mining
Первый этап состоит в приведении данных к форме, пригодной для применения конкретных реализаций систем Data Mining. Данный этап наименее автоматизирован в том смысле, что выбор необходимых для ИАД параметров производится человеком. Кроме того, на первом этапе производится постановка задачи, и определяются цели, которые должны быть достигнуты методами Data Mining. Данный этап особенно важен, т.к. некорректный выбор целей, методов и параметров приведёт к искажению окончательных результатов.
На втором этапе происходит форматирование (и, если необходимо, -редактирование) данных, чтобы к ним можно было применить конкретные методы интеллектуального анализа данных (поиск ошибок и пропусков, приведение данных к одному формату и т.д.). На этапе предобработки данных (или предпроцессинга) необходимо, во-первых, выделить то множество признаков, которые наиболее важны в контексте данного исследования, отбросить явно неприменимые из-за малой или чрезмерной вариабельности и выделить те, которые наиболее вероятно войдут в искомую зависимость. Для этого, как правило, используются статистические методы, основанные на применении корреляционного анализа, линейных регрессий и т.д., т.е. методы, позволяющие быстро, хотя и приближенно оценить влияние одного параметра на другой.
На третьем этапе осуществляется применение выбранных методов Data Mining. Существует множество вариантов их применения: от использования одного - двух алгоритмов до сложных комбинаций из разнообразных методов, что позволяет выполнить всесторонний анализ.
Четвёртый этап - тестирование полученных моделей. Широко используется следующий приём: весь исследуемый массив данных разделяют на две неравные части. Большая из них (обучающая) является исходным материалом для построения моделей методами Data Mining, а меньшая представляет собой тестовую группу, на которой проверяются полученные модели. По разности точности между группами можно судить насколько адекватна, статистически значима построенная модель.
На пятом этапе производится интерпретация моделей, построенных человеком. От того, насколько эффективным будет данный этап, в значительной степени зависит успех решения поставленной задачи.
Окончательная оценка моделей может быть дана только после практического применения полученных результатов.
При исследовании данных средствами Data Mining используется большое число различных методов и их различные комбинации. Наиболее важные и часто используемые методы [40,41,42]:
- кластеризация;
- ассоциация;
- деревья решений;
- метод ближайших соседей;
- нейронные сети;
- нечеткая логика;
- генетические алгоритмы;
- эволюционное программирование.
Методы кластерного анализа [43] позволяют разделить изучаемую совокупность объектов на группы «схожих» объектов, разнести записи в различные группы, или сегменты. Кластеризацию удобно использовать на начальных этапах исследования, когда о данных мало что известно.
Существует большое число методов кластеризации. В Data Mining наиболее популярны дивизивные методы (division), или методы расщепления, непосредственно разбивающие всю совокупность записей на несколько кластеров. Другие методы кластеризации - аггломеративные, или объединительные, начинаются с создания элементарных кластеров, каждый из которых состоит ровно из одного исходного наблюдения (одной точки), а на каждом последующем шаге происходит объединение двух наиболее близких кластеров в один.
К недостаткам кластеризации следует отнести зависимость результатов от выбранного метода кластеризации и от исходного преобразования данных, зависимость результатов от выбора параметров алгоритма расщепления/объединения и от выбора метрики. Поэтому результаты кластеризации часто могут быть дискуссионными. Кроме того, методы кластерного анализа не дают какого-либо способа для проверки достоверности разбиения на кластеры, для проверки статистической гипотезы об адекватности разбиения.
На сегодняшний день на рынке представлены разнообразные программные пакеты, реализующие данный метод и получившие название предметно-ориентированные аналитические системы. Как правило, они довольно дёшевы (обычно $300 - $1000).
Ассоциация [44], или метод «корзины покупателя», является одним из вариантов кластеризации, используемым для поиска групп характеристик, наблюдаемых одновременно. Анализ ассоциации имеет смысл в том случае, если несколько событий связаны друг с другом. Конструируемые модели характеризуют близость различных одновременно наблюдаемых категориальных характеристик и могут быть выражены в виде простых правил.
Основным достоинством метода ассоциации является простота генерируемых правил, которые легко воспринимаются человеком и имеют форму: если {условие}, то {результат}.
Примером такого правила, служит утверждение, что абонент, использующий услугу А, будет использовать услугу Б.
Целью анализа ассоциации является установление следующих зависимостей: если в транзакции (7) (наборе используемых услуг в определенное время) встретился некоторый набор элементов X, то на основании этого можно сделать вывод о том, что другой набор элементов Y также же должен появиться в этой транзакции: if(XeT)t then(Yє7\ , Ь
t/. Установление таких зависимостей дает возможность находить очень простые и интуитивно понятные правила.
Регрессионный анализ телекоммуникационных данных
Телекоммуникационные данные, хранящиеся в биллинговых системах, представляют собой базы данных большого объема, содержащие разнородную информацию, - трафик, финансовую информацию, тарифную информацию, сведения о клиентах, услугах, хронологическую информацию и т.п. Статистическая обработка такой информации является основой для построения аналитических, тенденциозных зависимостей, характеризующих организацию и перспективность ситуационной структуры телекоммуникационной системы.
Регрессионный анализ — один из основных методов, который позволяет анализировать значительные объемы разнородной информации с целью исследования вероятной взаимосвязи между анализируемыми факторами. Такая связь представляется в виде математической зависимости на множестве переменных системы. Такая зависимость (функция регрессии) подбирается исследователем на основе опыта и здравого смысла, при этом параметры регрессии определяются на основе критерия максимальной близости регрессионной поверхности к набору экспериментальных данных, имеющихся в распоряжении пользователя. Чаще всего используется линейная регрессионная модель [75, 76].
Данные, на основе которых строится функция регрессии, имеют две основных разновидности - числа и категории. Категориальные данные, например, «пол клиента», «район проживания», «образование» представляются натуральными числами.
Основные требования к данным, на основе которых строится регрессионная модель, определяющая функциональный когнитивный граф, следующие:
1) любые используемые данные должны быть количественно измеримы. Если необходимо включить в модель качественный фактор, не имеющий количественного измерения, то ему необходимо придать количественную определенность (например, в модели тарификационного файла биллинговой системы все качественные факторы могут быть проранжированы);
2) набор факторов, которые находятся в явной функциональной связи (известной исследователю) или сильно коррелирующие должны быть представлены в регрессионной модели только одним базовым фактором;
3) любой совокупный фактор, определяемый функционально несколькими базовыми, должен быть исключен из регрессионной модели;
4) количество включаемых в модель факторов не должно превышать одной трети числа наблюдений в выборке [71].
Второй и третий пункты фактически проводят границу между РКМ и функционально зависимыми факторами. Например, фактор «Общий объем услуг- ООУ» складывается из услуг трех видов (1,2, 3).
РКМ для этого примера связан с вершинами 1, 2, 3. Дуги 1 - ООУ, 2 — ООУ, 3 - ООУ не входят в регрессионную модель - это «чисто функциональные» связи. В то же время связи между вершинами 1, 2, 3 -скрытые, регрессионные, образующие РКМ.
Основная цель множественной регрессии - определить модели скрытых и неявных (гипотетических) причинно-следственных взаимосвязей. ООУ в этом примере выполняет роль совокупного фактора, интефирующего объемы услуг в явном виде: Здесь Ys объем соответствующих услуг. Отметим, что ООУ как совокупный показатель может выполнять роль и целевого показателя системы.
Также при отборе факторов следует учитывать, что реальные данные часто описываются довольно большим количеством параметров, среди которых встречаются сильно коррелирующие между собой, которые следует дополнительно анализировать, прежде чем ввести в регрессионную модель. Выделение переменных, дающих только наиболее значимый вклад, во-первых, приводит к тому, что описание найденной зависимости становится более понятным, т.к. будет включать только существенные факторы, и, во-вторых, значимость построенной модели, а значит, и ее предсказательная сила будет выше. Для выбора независимых переменных, включаемых в регрессионную модель, целесообразно использовать технологии Data Mining.
Одной из таких технологий выбора переменных и анализа регрессионной модели является эволюционное программирование, реализованное в системе PolyAnalyst [77]. В модуле системы после задания целевого и других факторов происходит автоматический выбор наиболее значимых независимых переменных, после которого начинается анализ. На рисунке 3.9 представлено диалоговое окно запуска вычислительного процесса линейной регрессии в системе PolyAnalyst для вершины графа «объем трафика», представленного на рисунке 3.6. Цель такого анализа -определить наличие скрытых связей между элементами графа для данной вершины, на основе которых будет возможно предусматривать будущие значения этого фактора и, как следствие, управлять данным элементом биллинговой системы.
РКМ для прогнозирования объема трафика телекоммуникационной компании
Для прогнозирования объемов телекоммуникационных услуг в сфере телекоммуникаций могут быть использованы различные типы алгоритмов технологии интеллектуального анализа данных. Их реальное использование для решения вышеуказанной задачи сопряжено с достаточно большими финансовыми затратами и может сильно повлиять на доходность компании как в положительную, так и в отрицательную сторону.
Поэтому возникает проблема выбора наиболее эффективного алгоритма, прогностические возможности которого являются главным критерием выбора. Целью данной главы является анализ прогностических возможностей регрессионно-когнитивного моделирования (РКМ) на предмет определения перспективности их использования для прогнозирования объемов телекоммуникационных услуг в сфере телекоммуникаций.
Количество видов телекоммуникационных услуг постоянно растет, а их объемы варьируются от клиента к клиенту, изменяются во времени, подвержены сезонным изменениям и т.п. Взаимосвязи между объемами услуг разных видов неочевидны: существуют ли скрытые связи между услугами, какова «сила» этих связей и к чему приведут возможные изменения объемов оказываемых услуг. Ответ на эти и подобные вопросы имеет вполне определенное практическое значение, позволяющее предсказать изменение объемов и, соответственно, экономические эффекты, свойственные той или иной ситуации, складывающейся на рынке телекоммуникационных услуг.
Рассмотрим один из примеров анализа биллингового файла для прогнозирования объемов четырех видов услуг: международная связь (М), местная связь (МС), передача данных (ПД) и Интернет (И). На рисунке 4.1 приведен полносвязный граф, иллюстрирующий возможные связи между услугами.
Двунаправленные стрелки иллюстрируют взаимные влияния факторов друг на друга.
Для количественного анализа таких взаимных влияний, согласно формуле (3.1), представленной в предыдущей главе, можно отразить линейную регрессионную модель вида:
Здесь Мб, И6, МСб, ПД5 - базовые объемы по видам услуг (свободные члены регрессий), к - коэффициенты влияния. Например, км и определяет влияние объемов международной связи на объемы услуг Интернета.
Значения коэффициентов оцениваются на основе биллингового файла, состоящего из 800 записей по объемам услуг, оказываемых различным клиентам в разное время. Следует также отметить, что данный файл был усреднен по нескольким телекоммуникационным компаниям, приоритетно занимающимися предоставлением «классических» видов услуг связи. Кроме того, для упрощения ситуации были оставлены вне поля зрения хронология получения записей и категориальный тип клиента.
Структура полученного файла в системе PolyAnalyst, в которой будет реализован последующий анализ, представлена на рисунке 4.-2, где значения по видам услуг отражены в рублях.
Структура биллингового файла в PolyAnalyst На рисунке 4.3 отражена статистика по исходному биллинговому файлу.
На основе биллингового файла, представленного на рисунке 4.2, в системе PolyAnalyst производится регрессионный анализ, который является основным компонентом РКМ. Поочередно, для каждой из вершин графа 4.1, проводится построение регрессионной модели. На рисунке 4.4 представлено построение линейного регрессионного уравнение для вершины «Интернет», причем, как уже упоминалось выше, в анализе не учитывается хронологический аспект (месяц предоставления услуги).
