Поиск кластеров сообществ Live Journal с помощью методов Data Mining в среде RapidMiner

Анализ проблем, возникающих при применении методов и алгоритмов кластеризации. Основные алгоритмы разбиения на кластеры. Программа RapidMiner как среда для машинного обучения и анализа данных. Оценка качества кластеризации с помощью методов Data Mining.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 22.10.2012
Размер файла 3,9 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Содержание

  • 1. Введение
  • 2. Кластеризация
    • 2.1. Общие понятия
    • 2.2. Цели
    • 2.3. Формальная постановка задачи.
    • 2.4. Основные алгоритмы
      • 2.4.1. K-means
      • 2.4.2. G-means
      • 2.4.3. Сети Кохонена
    • 2.5. Проблемы алгоритмов
  • 3. Среда RapidMiner
  • 4. Постановка задачи
  • 5. Реализация
    • 5.1. Подготовка входных данных
    • 5.2. Выбор меры близости
    • 5.3. Выбор способа кластеризации
    • 5.4. Оценка качества кластеризации
    • 5.5. Представление и анализ результатов
    • 5.6. Проверка результатов
  • 6. Заключение
  • 7. Список литературы
  • 1. Введение

Методы Data Mining помогают решить многие задачи, с которыми сталкивается аналитик. Особенный интерес к методам анализа данных возник в связи с развитием средств сбора и хранения данных, позволившим накапливать большие объемы информации.

Перед специалистами из разных областей человеческой деятельности встал вопрос об обработке собираемых данных, превращения их в знания. Известные статистические методы покрывают лишь часть нужд по обработке данных, и для их использования необходимо иметь четкое представление об искомых закономерностях. В такой ситуации методы интеллектуального анализа данных приобретают особую актуальность. Их основная особенность заключается в установлении наличия и характера скрытых закономерностей в данных, тогда как традиционные методы занимаются главным образом параметрической оценкой уже установленных закономерностей.

Среди методов интеллектуального анализа данных особое место занимает кластеризация. Она основывается на установленном отношении схожести элементов, устанавливает подмножества (кластеры), в которые группируются входные данные. В широком круге задач нашли своё применение методы нечёткой кластеризации, в которых элементы входного множества относят к тому или иному кластеру на основании значения функции принадлежности.

Первые публикации по кластерному анализу появились в конце 30-х гг. прошлого столетия, но активное развитие этих методов и их широкое использование началось лишь в конце 60-х - начале 70-х гг. В дальнейшем это направление многомерного анализа интенсивно развивалось. Появились новые методы, модификации уже известных алгоритмов, существенно расширилась область применения кластерного анализа. Если первоначально методы многомерной классификации использовались в психологии, археологии, биологии, то сейчас они стали активно применяться в социологии, экономике, статистике, в исторических исследованиях. Особенно расширилось их использование в связи с появлением и развитием ЭВМ и, в частности, персональных компьютеров.

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

Целью данной работы является выделение из исследуемого множества объектов (сообществ) Live Journal групп похожих объектов на основе их характеристик, и анализ полученных данных с помощью методов и технологий Data Mining в среде RapidMiner.

В процессе достижения поставленной цели решались следующие задачи:

1. Анализ проблем, возникающих при применении методов и алгоритмов кластеризации;

2. Выбор необходимых характеристик;

3. Оценка качества кластеризации при выборе оптимального решения;

4. Анализ результатов кластеризации;

5. Проверка достоверности результатов кластерного решения.

Методологической базой явились работы по методам кластеризации, в том числе посвященные практическим аспектам их применения. В работе использован математический аппарат классической теории множеств, математической статистики, нейронных сетей, методы дискретной и вычислительной математики.

2. Кластеризация

2.1 Общие понятия

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

В результаты кластеризации некоторого множества данных формируется определённое количество кластеров, что выражается в итоговой модели данных, которая является решением задачи кластеризации.

Задача кластеризации заключается в поиске независимых групп (кластеров) и их характеристик во всём множестве анализируемых данных. Решение этой задачи помогает нам лучше понять данные. Кроме того, группировка однородных объектов позволяет сократить их число, а, следовательно, и облегчить анализ.

Рис. 2.1. Иллюстрация задачи кластеризации

Кластеризацию используют, когда отсутствуют априорные сведения относительно классов, к которым можно отнести объекты исследуемого набора данных, либо когда число объектов велико, что затрудняет их ручной анализ.

Для задачи кластеризации характерно отсутствие каких-либо различий, как между переменными, так и между объектами. Напротив, ищутся группы наиболее близких, похожих объектов. Методы автоматического разбиения на кластеры редко используются сами по себе, а только для получения групп схожих объектов. После определения кластеров используются другие методы Data Mining, чтобы попытаться установить, что означает такое разбиение и чем оно вызвано.

Отметим ряд особенностей, присущих задаче кластеризации.

Во-первых, решение сильно зависит от природы объектов данных (и их атрибутов). Так, с одной стороны, это могут быть однозначно определённые, количественно очерченные объекты, а с другой - объекты, имеющие вероятностное или нечёткое описание.

Во-вторых, решение в значительной степени зависит и от представления кластеров и предполагаемых отношений объектов данных и кластеров. Так, необходимо учитывать такие свойства, как возможность/невозможность принадлежности объектов к нескольким кластерам. Необходимо определение самого понятия принадлежности кластеру: однозначная (принадлежит / не принадлежит), вероятностная (вероятность принадлежности), нечёткая (степень принадлежности). [2][3][4][5]

2.2 Цели

Цели кластеризации в Data Mining могут быть различными и зависят от конкретной решаемой задачи. Рассмотрим эти задачи.

Ё Изучение данных. Разбиение множества объектов на группы помогает выявить внутренние закономерности, увеличить наглядность представления данных, выдвинуть новые гипотезы, понять, насколько информативны свойства объектов.

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

Ё Сжатие данных. В случае, когда данные имеют большой объём, кластеризация позволяет сократить объём хранимых данных, оставив по одному наиболее типичному представителю от каждого кластера.

Ё Прогнозирование. Кластеры используются не только для компактного представления объектов, но и для распознавания новых. Каждый новый объект относится к тому кластеру, присоединение к которому наилучшим образом удовлетворяет критерию качества кластеризации. Значит, можно прогнозировать поведение объекта, предположив, что оно будет схожим с поведением других объектов кластера.

Ё Обнаружение аномалий. Кластеризация применяется для выделения нетипичных объектов. Эту задачу также называют обнаружением аномалий (outlier detection). Интерес здесь представляют кластеры (группы), в которые попадает крайне мало, скажем один-три, объектов. [2][3][4]

2.3 Формальная постановка задачи

Дано - набор данных со следующими свойствами:

Ё каждый экземпляр данных выражается чётким числовым значением;

Ё класс для каждого конкретного экземпляра данных неизвестен.

Найти:

Ё способ сравнения данных между собой (меру сходства);

Ё способ кластеризации;

Ё разбиение данных по кластерам.

Формально задача кластеризации описывается следующим образом.

Дано множество объектов данных I, каждый из которых представлен набором атрибутов. Требуется построить множество кластеров C и отображение F множества I на множество C, т.е. F : I > C. Отображение F задаёт модель данных, являющуюся решением задачи. Качество решения задачи определяется количеством верно классифицированных объектов данных. кластеризация rapidminer алгоритм программа

Множество I определим следующим образом:

,

где - исследуемый объект.

Каждый из объектов характеризуется набором параметров:

.

Каждая переменная может принимать значения из некоторого множества:

.

Задача кластеризации состоит в построении множества:

,

Здесь - кластер, содержащий похожие друг на друга объекты из множества I :

,

где - величина, определяющая меру близости для включения объектов в один кластер; - мера близости между объектами, называемая расстоянием.

Неотрицательное значение называется расстоянием между элементами и , если выполняются следующие условия:

1.

2.

3.

4.

Если расстояние меньше некоторого значения , то говорят, что элементы близки и помещаются в один кластер. В противном случае говорят, что элементы отличны друг от друга и их помещают в разные кластеры.[2][3]

2.4 Основные алгоритмы

По способу разбиения на кластеры алгоритмы бывают двух типов: иерархические и неиерархические.

Классические иерархические алгоритмы работают только с категорийными атрибутами, когда строится полное дерево вложенных кластеров. Здесь распространены агломеративные методы построения иерархий кластеров - в них производится последовательное объединение исходных объектов и соответствующее уменьшение числа кластеров. Иерархические алгоритмы обеспечивают сравнительно высокое качество кластеризации и не требуют предварительного задания количества кластеров. Большинство из них имеют сложность .

Неиерархические алгоритмы основаны на оптимизации некоторой целевой функции, определяющей оптимальное в определенном смысле разбиение множества объектов на кластеры. В этой группе популярны алгоритмы семейства k-средних (k-means, fuzzy c-means, Густафсон-Кесселя), которые в качестве целевой функции используют сумму квадратов взвешенных отклонений координат объектов от центров искомых кластеров. Кластеры ищутся сферической либо эллипсоидной формы. В канонической реализации минимизация функции производится на основе метода множителей Лагранжа и позволяет найти только ближайший локальный минимум. Использование методов глобального поиска (генетические алгоритмы) значительно увеличит вычислительную сложность алгоритма.

Среди неиерархических алгоритмов, не основанных на расстоянии, следует выделить EM-алгоритм (Expectation-Maximization). В нем вместо центров кластеров предполагается наличие функции плотности вероятности для каждого кластера с соответствующим значением математического ожидания и дисперсией.[6]

2.4.1 K-means

Одной из широко используемых методик кластеризации является разделительная кластеризация, в соответствии с которой для выборки данных, содержащей n записей, задаётся число кластеров k, которое должно быть сформировано. Затем алгоритм разбивает все объекты выборки на k групп (k<n), которые и представляют собой кластеры.

К наиболее простым и эффективным алгоритмам кластеризации относится k-means (k-средних). Он состоит из четырёх шагов:

1. Задаётся число кластеров k, которое должно быть сформировано из объектов исходной выборки.

2. Случайным образом выбирается k записей, которые будут служить начальными центрами кластеров. Начальные точки, из которых потом вырастает кластер, часто называют «семенами». Каждая такая запись представляет собой своего рода «эмбрион» кластера, состоящий только из одного элемента.

3. Для каждой записи исходной выборки определяется ближайший к ней центр кластера.

4. Производится вычисление центроидов - центров тяжести кластеров. Это делается путём определения среднего для значений каждого признака всех записей в кластере.

Шаги 3 и 4 повторяются до тех пор, пока выполнение алгоритма не будет прервано, либо пока не будет выполнено условие в соответствии с некоторым критерием сходимости (чаще всего используется сумма квадратов ошибок между центроидом кластера и всеми вошедшими в него записями).

Остановка алгоритма производится, когда границы кластеров и расположение центроидов перестают изменяться, то есть на каждой итерации в каждом кластере остаётся один и тот же набор записей. Алгоритм k-means обычно находит набор стабильных кластеров за несколько десятков итераций.[4]

2.4.2 G-means

Одним из недостатков алгоритма k-means является отсутствие ясного критерия для выбора оптимального числа кластеров.

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

Одним из самых популярных алгоритм кластеризации с автоматическим выбором числа кластеров является G-means. В его основе лежит предположение о том, что кластеризуемые данные подчиняются некоторому унимодальному закону распределения, например гауссовскому. Тогда центр кластера, определяемый как среднее значений признаков попавших в него объектов, может рассматриваться как мода соответствующего распределения.

Если исходные данные описываются унимодальным гауссовским распределением с заданными средним, то можно предположить, что все они относятся к одному кластеру.

Если распределение данных не гауссовское, то выполняется разделение на два кластера. Если в этих кластерах распределения окажутся близки к гауссовскому, то в первом приближении считается, что k = 2 будет оптимальным. В противном случае строятся новые модели с большим числом кластеров, и так до тех пор, пока распределение в каждом из них не окажется достаточно близким к гауссовскому. Такая модель и, соответственно, число кластеров в ней будут считаться оптимальными.

Алгоритм G-means является итеративным, где на каждом шаге с помощью обычного алгоритма k-means строится модель с определённым числом кластеров (начальное значение k выбирается равным 1), которое увеличивается на каждой итерации. Увеличение k производится за счёт разбиения кластеров, в которых данные не соответствуют гауссовскому распределению.

Алгоритм «принимает решение» о дальнейшем разбиении на основе статистического теста данных, связанных с каждым центроидом. Если при этом будет обнаружено, что они распределены по гауссовскому закону, то дальнейшего смысла в их разбиении нет. Фактически в процессе работы G-means алгоритм k-means будет повторён k раз, поэтому сложность алгоритма составляет O(k).[4]

2.4.3 Сети Кохонена

Термин «сети Кохонена» был введён в 1982 г. финским учёным Тойво Кохоненом. Сети Кохонена представляют собой разновидность самоорганизующихся карт признаков, которые, в свою очередь, являются специальным типом нейронных сетей.

Основная цель сетей Кохонена - преобразование сложных многомерных данных в более простую структуру малой размерности. Таким образом, они хорошо подходят для кластерного анализа, когда требуется обнаружить скрытые закономерности в больших массивах данных.

По способам настройки входных весов сумматоров и по решаемым задачам различают много разновидностей сетей Кохонена. Наиболее известные из них:

Ё Сети векторного квантования сигналов, тесно связанные с простейшим базовым алгоритмом кластерного анализа (метод динамических ядер или K-средних);

Ё Самоорганизующиеся карты Кохонена (Self-Organising Maps, SOM)

Ё Сети векторного квантования, обучаемые с учителем (Learning Vector Quantization).

Сеть Кохонена состоит из узлов, которые объединяются в кластеры. Наиболее близкие узлы соответствуют похожим объектам, а удалённые друг от друга - непохожим.

В основе построения сети Кохонена лежит конкурентное обучение, когда выходные узлы (нейроны) конкурируют между собой за право стать «победителем».

Обучение сети. Рассмотрим набор из m значений полей n-й записи исходной выборки, который будет служить входным вектором , и текущий вектор весов j-го выходного нейрона

.

Алгоритм Кохонена включает следующие шаги:

1. Инициализация. Для нейронов сети устанавливаются начальные веса, а также задаются начальная скорость обучения ? и радиус обучения R.

2. Возбуждение. На входной слой подаётся вектор воздействия , содержащий значения входных полей записи обучающей выборки.

3. Конкуренция. Для каждого выходного нейрона вычисляется расстояние D() между векторам весов всех нейронов выходного слоя и вектором входного воздействия. Если в качестве меры близости двух векторов выбрано евклидово расстояние, то получим:

D()=.

Иными словами, рассчитывается расстояние между векторами весов всех нейронов выходного слоя и вектором входного воздействия. Тот нейрон j, для которого расстояние окажется наименьшим, и будет победителем.

4. Объединение. Определяются все нейроны, расположенные в пределах радиуса обучения относительно нейрона-победителя.

5. Подстройка. Производится подстройка весов нейронов в пределах радиуса обучения в соответствии с формулой линейной комбинации входных векторов и текущих векторов весов:

При этом веса нейронов, ближайших к нейрону-победителю, подстраиваются в сторону его вектора весов.

6. Коррекция. Изменяются радиус и параметр скорости обучения в соответствии с заданным законом.[4][7]

2.5 Проблемы алгоритмов

Ранее мы уже отмечали, что одно и то же множество объектов можно разбить на несколько кластеров по-разному. Это привело к изобилию алгоритмов кластеризации. Пожалуй, ни одна другая задача Data Mining не имеет в своём арсенале столько алгоритмов и методов решения.

Причинами сложившейся ситуации является несколько факторов, имеющих общее объяснение: не существует одного универсального алгоритма кластеризации. Перечислим эти факторы.

Ё Неопределённость в выборе критерия качества кластеризации;

Ё Сложность выбора характеристик, на основе которых проводится кластеризация;

Ё Трудность выбора меры близости, обусловленная различной природой данных;

Ё Различные требуемые машинные ресурсы (память и время);

Ё Выбор числа кластеров.[1][2][3][4]

3. Среда RapidMiner

Программа RapidMiner (первое название «Yale») является средой для машинного обучения и анализа данных, в которой пользователь ограждён от всей «черновой работы». Вместо этого ему предлагается «нарисовать» весь желаемый процесс анализа данных в виде цепочки (графа) операторов и запустить его на выполнение. Цепочка операторов представляется в RapidMiner'е в виде интерактивного графа и в виде выражения на языке XML (eXtensible Markup Language, основного языка системы).

Система написана на языке Java и распространяется под лицензией AGPL Version 3. Ко всем основным функциям имеется доступ через Java API и версия программы для командной строки (а не только через общий пользовательский интерфейс).

Приложениями RapidMiner'а могут быть как исследовательские (модельные), так и прикладные (реальные) задачи интеллектуального анализа данных, включая анализ текста (text mining), анализ мультимедиа (multimedia mining), анализ потоков данных (data stream mining).

Функциональные возможности:

Ё RapidMiner предоставляет более 400 операторов для всех наиболее известных методов машинного обучения:

1. Операторы обучения по прецедентам (machine learning algorithms), в которых реализованы алгоритмы классификации, регрессии, кластеризации и поиска ассоциаций, а также мета-алгоритмы (типа бустинга).

2. Операторы системы WEKA.

3. Операторы предобработки (дискритизация, фильтрация, заполнение пропусков, уменьшение размерности и т.д.);

4. Операторы работы с признаками (селекция и генерация признаков);

5. Мета-операторы (например, оператор оптимизации по нескольким параметрам);

6. Операторы оценки качества (скользящий контроль и т.д.);

7. Операторы визуализации (это «конёк» системы, поскольку способов визуализации достаточно много и все графики смотрятся очень эффектно);

8. Операторы загрузки и сохранения данных (включая работу со специальными форматами: arff, C4.5, csv, bibtex, базы данных и т.д.).

Ё Имеется встроенный язык сценариев, позволяющий выполнять массивные серии экспериментов;

Ё Концепция многоуровневого представления данных (multi-layered data view) обеспечивает эффективную и прозрачную работу с данными;

Ё Графическая подсистема обеспечивает многомерную визуализацию данных и моделей;

Ё Имеется пошаговый учебник, включающий популярное введение в машинное обучение и интеллектуальный анализ данных;

Ё Имеются богатые возможности по добавлению в систему своих операторов.

Реализация и технологии:

Ё Программное обеспечение написано целиком на Java, поэтому работает во всех основных операционных системах;

Ё Для представления экспериментов как суперпозиций операторов применяется язык XML;

Ё Встраивание в другие приложения осуществляется посредством Java API;

Ё Поддерживаются механизмы плагинов (plugin) и расширений (extension).

Рис. 3.1. Главное окно программы

Последняя версия системы представлена для свободного скачивания на официальном сайте. Система поставляется в виде инсталлятора для Windows или в виде Java-версии (для последней необходимо ПО Java Runtime Environment, version 5.0).[8][9]

4. Постановка задачи

Наименование задачи:

Поиск кластеров сообществ Live Journal с помощью методов Data Mining в среде RapidMiner.

Общее описание:

Понять структуру множества объектов, разбив его на группы схожих объектов.

Входная информация:

Набор данных о сообществах Live Journal, содержащий 2907 экземпляров с разными значениями семи атрибутов: nick, name, membernum, readernum, recnum, commget, writernum.

Описание атрибутов:

· nick - метка сообщества;

· name - название сообщества;

· membernum - общее количество пользователей;

· readernum - количество читателей;

· recnum - количество статей;

· commget - оставленные комментарии;

· writernum - количество блогеров.

Выходная информация:

Набор данных с результатами разбиения первоначального набора данных по кластерам, полученный с помощью среды машинного обучения и анализа данных RapidMiner. Результаты представлены в виде таблицы формата Excel и различных графиков.

Рис. 4.1. Таблица с входными данными по 32 случайным экземплярам

5. Реализация

5.1 Подготовка входных данных

Реализация поставленной задачи выполнялась в среде RapidMiner, кратко рассмотренной нами в главе 3.

Исходные данные нашей задачи были представлены в виде числовых и строковых типов данных, описывающих свойства объектов, записанных в таблицу, хранимую в файле Microsoft Access. Данные были импортированы оператором «Read Access» с помощью SQL-запроса в среду RapidMiner, где подверглись предварительной обработке. Обработка заключалась в удалении всех экземпляров с неизвестными целыми или вещественными признаками. Полученные данные были записаны в файл Microsoft Excel для дальнейшей работы.

Рис. 5.1. Цепочка узлов предварительной обработки

Следующим нашим шагом в процессе выполнения задачи была формировка рабочего набора, состоящего из следующих этапов:

1. Загрузка ранее полученного в ходе предварительной обработки файла данных;

2. Отбор выборки для кластеризации.

В ходе анализа входных данных, мы пришли к выводу, что целесообразно выбрать числовые атрибуты: membernum, readernum, recnum, commget и writernum, описывающие свойства объектов.

Загрузка выходных данных осуществлялась оператором «Read Excel», а выбор атрибутов - «Select Attributes».

Рис. 5.2. Выбор необходимых атрибутов в свойствах оператора «Select Attributes»

5.2 Выбор меры близости

Как мы уже знаем - задача кластеризации состоит в разделении исследуемого множества объектов на группы «похожих» объектов, называемыми кластерами. Похожесть объектов между собой определяется специальной величиной - мерой близости, называемой расстоянием.

Для вычисления расстояний Расстояния между объектами предполагают их представление в виде точек m - мерного пространства . между объектами используются много различных подходов, но к числовым наборам данных чаще всего применяется популярная метрика евклидово расстояние, которое способствует увеличению контрастности кластеров:

.

Применение евклидова расстояния оправдано в следующих случаях:

Ё Свойства (признаки) объекта однородны по физическому смыслу и одинаково важны для классификации;

Ё Признаковое пространство совпадает с геометрическим пространством.[2][3]

Эта метрика хорошо подходит для решения нашей задачи.

5.3 Выбор способа кластеризации

Для кластеризации данных в RapidMiner был выбран наиболее распространённый среди неиерархических методов алгоритм k-средних, также называемый быстрым кластерным анализом. Принцип работы алгоритма был кратко нами рассмотрен в четвёртом разделе второй главы.

Рис. 5.3. Цепочка узлов решения поставленной задачи

Перечислим основные достоинства и недостатки данного алгоритма.

Достоинства:

Ё простота использования;

Ё быстрота использования;

Ё понятность и прозрачность алгоритма.

Недостатки:

Ё слишком чувствителен к выбросам;

Ё может медленно работать на больших базах данных;

Ё не в состоянии выбрать автоматически оптимальное число кластеров.

5.4 Оценка качества кластеризации

Для решения последней проблемы в предыдущем разделе, в среде RapidMiner был разработан новый процесс, выполняющий оценивание качества кластеризации по двум параметрам, выполненный на основе метода k-средних путём перебора различного числа кластеров. Дополнительно в процесс был включён оператор валидации.

Рис. 5.4. Общий вид процесса оценки качества кластеризации

Здесь оператор «Loop Parameters» представляет из себя совокупность функций и подпроцессов по оценке качества кластеризации на основе алгоритма k-means:

Рис. 5.5. Состав оператора «Loop Parameters»

Краткое описание операторов:

Ё «Multiply» - создаёт копию входных данных на выходе;

Ё «Clustering» - процесс кластеризации алгоритмом k-means;

Ё «Distance» - оценивает среднее расстояние между кластерами путём вычисления среднего расстояния между центроидами и всеми входными данными кластера.

Ё «Distribution» - оценивает распределение данных по кластерам.

Рис. 5.6. Задание параметров в операторе «Loop Parameters»

Валидация кластеров. Под валидацией кластеров понимают проверку их обоснованности. Различают два типа валидации: внутреннюю - по тому, насколько кластеры соответствуют данным, и внешнюю - по тому, насколько кластеры соответствуют информации, не учитывавшейся при их построении, но известной специалистам - такого рода информация обычно представляется в виде разбиения.

Среди многообразия различных индексов, использующихся для валидации кластеров, наиболее популярным является индекс - Дэвиса Болдина, который можно определить следующим образом. Охарактеризуем относительный разброс в двух кластерах как полусумму средних расстояний их элементов до центров, делённую на расстояние между центрами. Охарактеризуем разброс кластера максимальной величиной его относительного разброса (относительно других кластеров). Тогда индекс Дэвиса - Болдина - не что иное, как средний разброс кластеров.[10][11]

Результаты всех выполненных вычислений оператором «Loop Parameters» представлены в численном и графическом виде.

Рис. 5.7. Вычисленные значения индексов и параметров

Рис. 5.8. График распределения среднего расстояния между кластерами

Рис. 5.9. График распределения индекса Дэвиса - Болдина

Рис. 5.10. График распределения данных по кластерам

Рис. 5.11. Объединение предыдущих трёх графиков

Проведя анализ полученных графиков, мы пришли к выводу, что значение k = 6, является оптимальным числом для выделения кластеров в наших данных. Это подтверждается двумя известными эмпирическими правилами выбора числа кластеров:

Ё Двух или трёх кластеров, как правило, недостаточно: кластеризация будет слишком грубой, приводящей к потере информации об индивидуальных свойствах объектов.

Ё Больше десяти кластеров не укладывается в «число Миллера 7 ± 2» В 1956 г. Дж. Миллер обобщил имевшиеся данные об объёме кратковременной памяти человека и показал, что этот объём определяется не числом слов в предложении, а числом объектов и обычно равен 7 ± 2.: аналитику трудно держать в кратковременной памяти столько кластеров.[4]

5.5 Представление и анализ результатов

Результатом кластерного анализа является набор кластеров, содержащих элементы исходного множества. Кластерная модель должна описывать как сами кластеры, так и принадлежность каждого объекта к одному из них.

Анализ результатов кластеризации подразумевает решение таких вопросов: не является ли полученное разбиение на кластеры случайным; является ли разбиение надежным и стабильным на подвыборках данных; существует ли взаимосвязь между результатами кластеризации и переменными, которые не участвовали в процессе кластеризации; можно ли интерпретировать полученные результаты кластеризации.

Рис. 5.12. Результаты кластерного разбиения

Результаты кластеризации были записаны в файл Microsoft Excel.

Среда разработки RapidMiner предлагает богатые возможности для визуализации результатов кластеризации.

Изучив рис. 5.13. мы сделали вывод: для визуальной интерпретации результатов кластерного разбиения подходят только те матричные графики, на которых присутствует атрибут commget.

Рассмотрим более детально матричный график с атрибутами recnum и commget, названный нами условно как «M.RecNum-CommGet»

Рис. 5.13. Всевозможные варианты матричных графиков

Рис. 5.14. Матричный график «M.RecNum-CommGet»

На графике хорошо просматривается результат разбиения входного набора данных. Точки есть наши сообщества, а их цвет характеризует принадлежность к тому или иному кластеру.

Можно сделать предварительный вывод: алгоритм кластеризации k-means справился с возложенной на него работой, а число первоначальных кластеров было выбрано нами правильно.

В следующем разделе мы займёмся проверкой результатов кластеризации, чем подтвердим или опровергнем сделанный вывод. Но прежде чем приступить к проверке, рассмотрим ещё пару графиков.

Рис. 5.15. График отклонений значений атрибутов

Рис. 5.16. График плотности распределения

Рис. 5.15. показывает отклонения значений параметров объектов, а рис. 5.16. плотность распределения записей в кластерах.

Рис. 5.17. Круговая диаграмма распределения сообществ по кластерам

Рис. 5.18. Сравнение результатов кластеризации с невключёнными в анализ атрибутами

Для каждого кластера был произведён расчёт средних значений атрибутов, участвовавших в процессе кластеризации.

Табл. 1. Средние значения атрибутов в кластерах

membernum

readernum

recnum

commget

writernum

cluster_0

8777,1

6172,9

38312,6

840175,0

8761,3

cluster_1

310,8

310,5

401,4

1592,4

289,8

cluster_2

1885,1

1793,0

2961,2

26028,9

1880,3

cluster_3

5800,4

4104,2

16167,5

174808,7

5810,8

cluster_4

3570,5

3254,0

6836,5

75957,9

3502,9

cluster_5

7809,6

5786,0

25104,1

322164,2

7805,6

В соответствии с рис. 5.15., рис. 5.18. и табл. 1 можно сделать вывод о том, что в распределении сообществ по кластерам ключевую роль сыграл атрибут commget.

Обобщая полученные результаты кластеризации можно сказать, что каждый кластер представляет собой некий «организм», а множество входящих в него объектов - «клетки».

5.6 Проверка результатов

Результаты кластеризации всегда должны быть проверены формальными или неформальными методами. Формальные методы зависят от того метода, который использовался для кластеризации. Неформальные включают следующие процедуры проверки качества кластеризации:

Ё Анализ результатов кластеризации, полученных на определенных выборках набора данных;

Ё Кросс-проверка;

Ё Проведение кластеризации при изменении порядка наблюдений в наборе данных;

Ё Проведение кластеризации при удалении некоторых наблюдений;

Ё Проведение кластеризации на небольших выборках.

Один из вариантов проверки качества кластеризации - использование нескольких методов и сравнение полученных результатов. Отсутствие подобия не будет означать некорректность результатов, но присутствие похожих групп считается признаком качественной кластеризации.

Прежде чем приступить к проверке результатов кластеризации, проведём небольшую проверку правильности выбора начального числа кластеров.

В ходе анализа рис 5.11. некоторыми аналитиками может быть выбрано значение k = 11, которое является вкорне неверным. Попробуем это доказать.

Для доказательства нашего утверждения мы построили Карты Кохонена для кластеризации со значениями k равными 6 и 11.

Рис. 5.19. Карта Кохонена для кластеризации 6-ю кластерами

Рис. 5.20. Карта Кохонена для кластеризации 11-ю кластерами

Самоорганизующиеся карты Кохонена - один из частных видов нейронных сетей. Карты Кохонена - инструмент для обнаружения взаимосвязей между объектами. Формально, карты Кохонена - это метод проецирования многомерного пространства наблюдений на пространство более низкой размерности - карту. Поэтому карты Кохонена часто используют для решения задач визуализация и кластеризации.

В кластеризации полученные кластеры отображаются на двухмерном рисунке, что позволяет нам наглядно и легко интерпретировать изображение кластеров.[12][13]

Сравнив рис. 5.19. и рис 5.20. мы отметили, что при кластеризации 6-ю кластерами объекты распределены по кластерам компактными сгустками. При кластеризации 11-ю кластерами данное явление менее заметно.

Следующей нашей процедурой в проверке качества кластеризации было проведение кластеризации при удалении некоторых параметров объектов. Для этого в среде RapidMiner был разработан специальный процесс поиска соответствий. Его работа заключается в поиске похожих групп в результатах кластеризации по всем и только двум атрибутам объектов.

Рис. 5.21. Цепочка операторов поиска соответствий

Рис. 5.22. Найденные совпадения при кластеризации 6-ю кластерами по атрибутам recnum и commget

Рис. 5.23. Найденные совпадения при кластеризации 6-ю кластерами по атрибутам recnum и readernum

Табл. 2. Результаты совпадений при кластеризации 6-ю кластерами по двум атрибутам

membernum

readernum

recnum

commget

writernum

membernum

18,163%

1,376%

0,275%

19,677%

readernum

18,163%

98,005%

0,275%

15,652%

recnum

1,376%

98,005%

0,275%

11,971%

commget

0,275%

0,275%

0,275%

0,275%

writernum

19,677%

15,652%

11,971%

0,275%

Табл. 3. Результаты совпадений при кластеризации 11-ю кластерами по двум атрибутам

membernum

readernum

recnum

commget

writernum

membernum

1,891%

5,847%

0,034%

0,929%

readernum

1,891%

7,115%

0,034%

2,236%

recnum

5,847%

7,115%

0%

0,825%

commget

0,034%

0,034%

0%

0%

writernum

0,929%

2,236%

0,825%

0%

На основании рис. 5.23. и данных из табл. 2. и табл. 3., полученных в ходе работы процесса поиска соответствий, было подтверждено сделанное нами ранее утверждение: алгоритм кластеризации k-means справился с возложенной на него работой, а число первоначальных кластеров было выбрано нами правильно.

6. Заключение

Данная курсовая работа посвящена поиску кластеров сообществ Live Journal с помощью методов и технологий Data Mining в среде RapidMiner.

В процессе достижения поставленной цели были решены следующие задачи:

1. Анализ проблем, возникающих при применении методов и алгоритмов кластеризации;

2. Выбор необходимых характеристик;

3. Оценка качества кластеризации при выборе оптимального решения;

4. Анализ результатов кластеризации;

5. Проверка достоверности результатов кластерного решения.

Итогом проделанной работы стали следующие выводы и практические результаты:

Ё Задача кластеризации состоит в разделении исследуемого множества объектов на группы похожих объектов, называемых кластерами;

Ё Для определения «похожести» объектов вводится мера близости, называемая расстоянием;

Ё Результаты кластеризации могут быть представлены разными способами;

Ё Базовые методы кластеризации делятся на иерархические и неиерархические;

Ё Наиболее популярный из неиерархическиъ алгоритмов - алгоритм k-means, который в силу своих достоинств прекрасно подходит для оперируемости числовыми наборами данных в решении задач кластеризации, хотя и имеет свои недостатки. Одним из главных недостатков является выбор начального числа кластеров. Для решения этой проблемы в среде RapidMiner был разработан специальный процесс по оценке качества кластеризации. Экспериментальное исследование, проведённое с использованием данной среды, подтвердило достоверность и эффективность результатов полученных в работе;

Ё Кластеры представляют собой некие «организмы», жизнь которых характеризуется активностью их «клеток». «Клетки» есть множество сообществ сети Live Journal, характеризующиеся различными параметрами, среди которых главную роль в определении «активности клетки» играет атрибут commget (количество комментариев).

Данные полученные в ходе анализа могут найти свои применение в рекламе, в социальных опросах, и PR-акциях для которых будет подобрана целевая аудитория.

7. Список литературы

1. Чубукова И.А. Data Mining. Учебное пособие. - М.: Интернет-Университет Информационных технологий; БИНОМ. Лаборатория знаний, 2006.

2. Методы и модели анализа данных OLAP и Data Mining: А.А. Барсегян, М.С. Куприянов, В.В. Степаненко, И.И. Холод - СПб.: БХВ-Петербург, 2004. - 336 стр.

3. Анализ данных и процессов: учеб. пособие / А.А. Барсегян, М.С. Куприянов, И.И. Холод, М.Д. Тесс, С.И. Илизаров. - 3-е изд., перераб. и доп. - СПб.: БХВ-Петербург, 2009. - 512 стр.

4. Бизнес-аналитика: от данных к знаниям: учеб. пособие / Н. Паклин, В. Орешков - 2-е изд., перераб. и доп. - СПб.: Питер, 2012. - 704 стр.

5. Введение в Data Mining - (http://www.zsoft.ru/page.php?8).

6. Алгоритмы кластеризации на службе Data Mining - (http://www.basegroup.ru/library/analysis/clusterization/datamining).

7. Нейронная сеть Кохонена - (http://ru.wikipedia.org/wiki/Нейронная_сеть_Кохонена).

8. Домашняя страница проекта RapidMiner - (http://rapid-i.com/content/view/181/190).

9. Описание приложения RapidMiner - (http://www.machinelearning.ru/wiki/index.php?title=RapidMiner).

10. Sum-of-Squares Based Cluster Validity Index and Significance Analysis: Q. Zhao, M. Xu, P. Franti. Department of Computer Science, University of Joensuu, Box 111, Fin-08101 Joensuu Finland, 2009. -10 стр.

11. Методы кластер-анализа для поддержки принятия решений: обзор / Б.Г. Миркин - серия WP7 «Математичесие методы анализа решений в экономике, бизнесе и политике» / Ф.Т. Алесеров, В.В. Подиновский, Б.Г. Миркин - НИУ «Высшая школа экономики», 2011. - 88 стр.

12. Самоорганизующиеся карты Кохонена - (http://wiki.witology.com/index.php/Самоорганизующиеся_карты_Кохонен).

13. Самоорганизующиеся карты Кохонена - математический аппарат - (http://www.basegroup.ru/library/analysis/clusterization/som).

Размещено на Allbest.ru


Подобные документы

  • Основы для проведения кластеризации. Использование Data Mining как способа "обнаружения знаний в базах данных". Выбор алгоритмов кластеризации. Получение данных из хранилища базы данных дистанционного практикума. Кластеризация студентов и задач.

    курсовая работа [728,4 K], добавлен 10.07.2017

  • Описание функциональных возможностей технологии Data Mining как процессов обнаружения неизвестных данных. Изучение систем вывода ассоциативных правил и механизмов нейросетевых алгоритмов. Описание алгоритмов кластеризации и сфер применения Data Mining.

    контрольная работа [208,4 K], добавлен 14.06.2013

  • Data mining, developmental history of data mining and knowledge discovery. Technological elements and methods of data mining. Steps in knowledge discovery. Change and deviation detection. Related disciplines, information retrieval and text extraction.

    доклад [25,3 K], добавлен 16.06.2012

  • Классификация задач DataMining. Создание отчетов и итогов. Возможности Data Miner в Statistica. Задача классификации, кластеризации и регрессии. Средства анализа Statistica Data Miner. Суть задачи поиск ассоциативных правил. Анализ предикторов выживания.

    курсовая работа [3,2 M], добавлен 19.05.2011

  • Роль информации в мире. Теоретические основы анализа Big Data. Задачи, решаемые методами Data Mining. Выбор способа кластеризации и деления объектов на группы. Выявление однородных по местоположению точек. Построение магического квадранта провайдеров.

    дипломная работа [2,5 M], добавлен 01.07.2017

  • Совершенствование технологий записи и хранения данных. Специфика современных требований к переработке информационных данных. Концепция шаблонов, отражающих фрагменты многоаспектных взаимоотношений в данных в основе современной технологии Data Mining.

    контрольная работа [565,6 K], добавлен 02.09.2010

  • Перспективные направления анализа данных: анализ текстовой информации, интеллектуальный анализ данных. Анализ структурированной информации, хранящейся в базах данных. Процесс анализа текстовых документов. Особенности предварительной обработки данных.

    реферат [443,2 K], добавлен 13.02.2014

  • Понятие информационных систем и принципы их проектирования. Изучение различных методов извлечения знаний, построение оптимальной информационной системы Data Mining, позволяющей разбивать набор данных, представленных реляционными базами данных на кластеры.

    аттестационная работа [4,7 M], добавлен 14.06.2010

  • Классификация задач Data Mining. Задача кластеризации и поиска ассоциативных правил. Определению класса объекта по его свойствам и характеристикам. Нахождение частых зависимостей между объектами или событиями. Оперативно-аналитическая обработка данных.

    контрольная работа [26,1 K], добавлен 13.01.2013

  • Создание структуры интеллектуального анализа данных. Дерево решений. Характеристики кластера, определение групп объектов или событий. Линейная и логистическая регрессии. Правила ассоциативных решений. Алгоритм Байеса. Анализ с помощью нейронной сети.

    контрольная работа [2,0 M], добавлен 13.06.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.