TELECOMMUNICATION COMPANY BIG DATA CLASSIFICATION BY DATA MINING TECHNIQUE

Full Text

В телекоммуникационных компаниях (ТК) с использованием баз данных (БД) ежедневно собираются большие объемы информации. Из такого объема данных необходимо извлечь ценную информацию, касающуюся работы компании и ее клиентов. Для этой цели хорошо подходит технология DATA MINING - как мультидисциплинарная область, возникшая и развивающаяся на базе таких наук как прикладная статистика, классификация и кластеризация, распознавание образов, искусственный интеллект, теория баз данных и др. Поэтому здесь хорошо просматривается интеграция теории прикладной статистики анализа данных с очисткой данных, обучением и визуализацией результатов. Применительно к обработке информации ТК главная проблема состоит в том, что зачастую заранее неизвестно, как группировать эти данные, как находить связи между событиями и т.д. Для частичного решения данной проблемы используются методы классификации и кластеризации DATA MINING. При помощи них можно объединять данные по любым выбранным признакам. Например, находить взаимосвязь события от нагрузки в сети или дня недели и т.п. Постановка задачи В качестве примера накопления больших объемов данных рассмотрим ТК, которые каждый день собирают информацию о трафике пользователей. Требуется проанализировать весь объем информации, полученный за один месяц работы и выявить аномалии, нестандартное поведение клиентов и соотношение объема трафика ко дню недели и типу дня (рабочий, выходной). Компанией «СамараСвязьИнформ» авторам был предоставлен массив данных (135 Гб в формате txt) о трафике, который клиенты генерируют ежедневно. Он содержит, в числе прочих, следующую информацию: ID аккаунта, IP адрес источник, IP адрес получатель, размер пакета данных, номер порта источника, номера порта получателя, день и время события в unix формате. В общей сложности это примерно 45 млн. строк вида, показанного на рис. 1. Рис. 1. Пример строки предоставленных данных Классическая задача DATA MINING состоит в том, чтобы из очень большого объема данных извлечь самую нужную и ценную информацию. Провести анализ таких данных вручную невозможно, поэтому было принято решение преобразовать данные в нужный формат и применить к решению поставленной задачи статистические методы кластеризации и классификации. Кроме того, для анализа таких объемов информации также невозможно применить готовые статистические пакеты. Известный метод классификации на основе корреляционного анализа также здесь не может быть применен вследствие того, что получится корреляционная матрица очень большого порядка. Ниже приведена последовательность действий, необходимых для получения реальных результатов. Первичная обработка данных Для выявления соотношения объема трафика и активности клиента в целом решено преобразовать данные в следующий формат: ID аккаунта, объем трафика за сутки в гигабайтах, день недели, порядковый номер дня, тип дня (выходной - 0, рабочий - 1), число запросов за сутки - всего 6 упорядоченных признаков каждого вектора данных. Для такого преобразования была написана программа на языке C#, которая открывала по очереди txt файлы на чтение, складывала трафик за сутки каждого клиента и считывала количество обращений этого клиента к серверу. После преобразований было получено 60473 строк информации, и, если поделить это число на количество дней в месяце, то мы получим количество активных абонентов компании. Каждая строка, это информация о клиенте за день. На рис. 2 приведен пример данных для пяти клиентов компании с шестью упорядоченными признаками. Рис. 2. Пример данных после преобразования Описание программы преобразования данных к кластеризации Алгоритм работы этой программы разбивается на несколько цикличных этапов: 1. Открытие текстовых файлов с информацией, пока не прошли по всем файлам. 2. Построчное считывание информации, пока не конец файла. 3. Разбор строки на составляющие: id аккаунта, размер пакета и т.д. 4. Суммирование объема трафика. 5. Подсчет количества обращений к серверу. 6. Преобразование данных в формат CSV и сохранение полученных данных в файл. После первичной обработки требуется разбить эти данные на группы и проанализировать полученный результат. Поскольку при этом априори предполагается, что среди клиентов компании по двум признакам (второй и шестой) могут быть нестандартные, для этого был выбран метод кластеризации k-средних. Кластеризация данных Точность разбиения полученных векторов по кластерам зависит от изначально выбранных центроидов. Нами выбран метод инициализации центридов под названием k-means++. Это улучшенная версия алгоритма кластеризации k-средних. Суть улучшения заключается в нахождении более «хороших» начальных значений центроидов кластеров. Алгоритм метода включает пять основных шагов. Рис.3. Схема алгоритма работы программы Иницилизация. 1. Выбрать первый центроид случайным образом (среди всех точек). 2. Для каждой точки найти значение квадрата расстояния до ближайшего центроида (из тех, которые уже выбраны) (dx)². 3. Выбрать из этих точек следующий центроид так, чтобы вероятность выбора точки была пропорциональна вычисленному для нее квадрату расстояния. 4. Это можно сделать следующим образом: на шаге 2, параллельно с расчетом (dx)², нужно подсчитывать сумму Sum(dx²). После накопления данной суммы найти значение Rnd=random(0.0,1.0)*Sum. Генератор Rnd случайным образом укажет на число из интервала [0; Sum), и остается только определить, какой точке это соответствует. Для этого нужно снова начать подсчитывать сумму S(dx²) до тех пор, пока сумма не превысит Rnd. Как только это случится, суммирование останавливается, и мы можем взять текущую точку в качестве центроида. При выборе каждого следующего центроида не надо следить за тем, чтобы он не совпал с одной из уже выбранных в качестве центроидов, так как вероятность повторного выбора точки равна нулю. 5. Повторять шаги 2 и 3 до тех пор, пока не будут найдены все необходимые центроиды. Далее выполняется основной алгоритм k-средних: этот популярный метод кластеризации был предложен полвека назад Г. Штейнгаузом и С. Ллойдом. Действие алгоритма таково, что он стремится минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров: , где k - число кластеров, Si - полученные кластеры, i = 1; 2 … k и µi - центры масс векторов xj принадлежащих Si. Анализ полученных результатов Для проведения кластерного анализа была написана программа на языке Python, с подключенной библиотекой sklearn, которая содержит в себе реализации большинства математических методов интеллектуального анализа данных. В укрупненном виде схема алгоритма программы приведена на рис. 4. Рис. 4. Схема алгоритма программы кластеризации Применив совмещенный метод k-средних с методом инициализации центроидов k-means++, и разбив данные на два кластера, получим следующие результаты: 1-ый кластер включает 60427 записей; 2-ой кластер - 46 записей. На рис. 5 можно видеть графическое распределение векторов (записей) по кластерам. Здесь по горизонтальной оси X указано количество ответов от сервера, а по вертикальной оси Y - account id. Белыми крестами отображены центроиды кластеров. Рис. 5. Кластеры, полученные методом k-средних Как можно интерпретировать полученные данные? Первый кластер (справа) содержит информацию о стандартных записях, которые не выделяются из общей массы. Это стандартное поведение клиентов в течение месяца. Второй кластер (слева) содержит информацию о выделившихся из массы нестандартных записях. Это «особое», отличающееся от нормального, поведение клиентов: скорее всего на стороне клиентов с такими признаками можно обнаружить вирусную активность, либо «плохое» программное обеспечение, вызывающие очень большое число обращений к серверу ТК. Построение классификатора и его обучение Для того, чтобы программное обеспечение в дальнейшем само автоматически определяло принадлежность той или иной записи к выделенным кластерам, необходимо применить метод классификации. Для этого рассмотрим метод опорных векторов (англ. SVM, support vector machine) - набор схожих алгоритмов обучения с учителем, использующихся для задач классификации и регрессионного анализа. Он принадлежит к семейству линейных классификаторов, может также рассматриваться как специальный случай регуляризации по А.Н. Тихонову. Особым свойством метода опорных векторов является непрерывное уменьшение эмпирической ошибки классификации и увеличение зазора между гиперплоскостями, поэтому метод также известен как метод классификатора с максимальным зазором. Основная идея метода - перевод исходных векторов в пространство более высокой размерности и поиск разделяющей гиперплоскости с максимальным зазором в этом пространстве. Две параллельных гиперплоскости строятся по обеим сторонам гиперплоскости, разделяющей разные классы. Разделяющей гиперплоскостью будет гиперплоскость, которая максимизирует расстояние до двух параллельных гиперплоскостей. Алгоритм работает в предположении, что чем больше разница или расстояние между этими параллельными гиперплоскостями, тем меньше будет средняя ошибка классификатора. Для применения метода классификации к данным каждая запись должна быть вручную помечена принадлежностью к конкретному классу - после чего данные выглядят, как это показано на рис. 6. Вводится новое поле target, которое хранит в себе информацию о принадлежности каждой записи к тому или иному классу. Рис. 6. Вид данных Здесь поле target - это классификатор: 1 - относит данные к первому кластеру; 0 - ко второму. Рис. 7. Графический вид классифицированных данных На рис. 7 отображены классифицированные данные по полю target: красным цветом обозначены вектора, принадлежащие к кластеру 1 (верхнее семейство точек), синим цветом - к кластеру 2 (нижнее семейство точек). Программа написана на языке Python, также с использованием библиотеки sklearn, которая классифицирует новые данные при помощи метода опорных векторов и выводит информацию о принадлежности этих данных к тому или иному классу. Укрупненная схема алгоритма программы приведена на рис. 8. Для примера проверим принадлежность к кластерам следующие записи (размер трафика в гигабайтах, число ответов от сервера, день недели, день месяца, тип дня, месяц): 1. 30.0108,13883303,1,1,2,1 2. 0.007,4573,1,1,2,1,0 Программа дает ответ: первая запись принадлежит к первому кластеру, вторая - ко второму кластеру, что полностью подтверждает правильность работы классификатора. Рис.8. Схема алгоритма программы классификации данных Заключение Проведен полный спектр анализа данных ТК, предоставленных за февраль месяц, которые содержат служебную информацию об IP-потоках. Для проведения полного анализа написана программа на языке C#, агрегирующая данные по дням - таким образом были выделены признаки, в соответствии с которыми в дальнейшем будет осуществляться классификация по известным методам. Проведен кластерный анализ при помощи авторской программы на языке Python, выявлены два кластера: среднестатистические клиенты и «особые». Информация отображена на графиках. По этим данным было проведено обучение выборки большого объема (60427 векторов) с введением поля «target». Применен метод опорных векторов для классификации новых данных, поступающих в реальном времени. Обученный классификатор может быть применен для анализа новых данных ТК.

About the authors

Michael Evgenevich Samarkin

Povolzhsky State University of Telecommunications and Informatics

Email: m.samarkin@psuti.ru

Veniamin Nikolayevich Tarasov

Povolzhsky State University of Telecommunications and Informatics

Email: tarasov-vn@psuti.ru

References

Supplementary files