Применение неиерархического метода кластеризации и методов визуализации для интеллектуального анализа данных средствами Tableau
Сущность алгоритмов кластеризации и методов визуализации в анализе данных
Кластеризация является одной из фундаментальных задач в области анализа данных и часто выступает ее первым шагом. На практике легче выделить группы схожих объектов (кластеров), изучить их особенности и построить для каждой группы отдельную модель. Таким приемом часто пользуются в маркетинге, выделяя группы клиентов, поставщиков, товаров и разрабатывая для каждой их них отдельную стратегию.
Проблемы кластеризации:
Все атрибуты, или признаки объектов делятся на числовые и категорийные. Например, атрибут «цена» – числовой, «упаковка товара» – категорийный. Большинство алгоритмов кластеризации предполагают сравнение объектов между собой на основе некоторой меры близости (сходства). Мерой близости называется величина, возрастающая с увеличением близости объектов. Меры сходства создаются по специальным правилам, а выбор конкретных мер зависит от задачи, а также от шкалы измерений. В качестве меры близости для числовых атрибутов часто используется евклидово расстояние, вычисляемое по формуле изображенной на рисунке 9:
Рисунок 9 – формула евклидова расстояния
Для категорийных атрибутов распространена мера сходства Чекановского-Серенсена и Жаккара []. Мера показана на Рисунок 10:
Рисунок 10 – мера сходства Чекановского-Серенсена и Жаккара
Алгоритмы кластеризации:
По способу разбиения на кластеры алгоритмы бывают двух типов: иерархические и неиерархические. Классические иерархические алгоритмы работают с категорийными атрибутами, когда строится полное дерево вложенных кластеров. Здесь распространены агломеративные методы построения иерархий кластеров – в них производится последовательное объединение исходных объектов и соответствующее уменьшение числа кластеров. Иерархические алгоритмы обеспечивают сравнительно высокое качество кластеризации и не требуют предварительного задания количества кластеров. Неиерархические алгоритмы основаны на оптимизации целевой функции, определяющей оптимальное разбиение множества объектов на кластеры. В этой группе популярны алгоритмы семейства k-средних (k-means, fuzzy c-means, Густафсон-Кесселя и др.), которые в качестве целевой функции используют сумму квадратов взвешенных отклонений координат объектов от центров кластеров. Кластеры ищутся сферической либо эллипсоидной формы. В канонической реализации минимизация функции производится на основе метода множителей Лагранжа и позволяет найти только ближайший локальный минимум. Использование методов глобального поиска (генетические алгоритмы) значительно увеличит вычислительную сложность алгоритма. Недостатками алгоритма являются зависимость результата от инициализации центров кластеров и неопределенность выбора начального количества точек, играющих роль центров кластеров при первой итерации [6].
Среди неиерархических алгоритмов, не основанных на расстоянии, следует выделить EM-алгоритм (Expectation-Maximization). В нем вместо центров кластеров предполагается наличие функции плотности вероятности для каждого кластера с соответствующим значением математического ожидания и дисперсией. В смеси распределений ведется поиск их параметров (средние и стандартные отклонения) по принципу максимума правдоподобия. Проблема заключается в том, что перед стартом алгоритма выдвигается гипотеза о виде распределений, которые оценить в общей совокупности данных сложно.
Еще одна проблема появляется тогда, когда атрибуты объекта смешанные – одна часть имеет числовой тип, а другая часть – категорийный. При этом категорийные атрибуты часто важнее числовых.
Алгоритм оптимизации целевой функции в неиерархических алгоритмах, основанных на расстояниях, носит итеративный характер, и на каждой итерации требуется рассчитывать матрицу расстояний между объектами. При большом числе объектов это требует значительных вычислительных ресурсов.
Алгоритмы семейства k-means хорошо работают, когда данные в многомерном пространстве образуют компактные сгустки, хорошо отличимые друг от друга. Если данные имеют вложенную форму, то алгоритм семейства k-means не справится с такой задачей. Также алгоритм плохо работает в случае, когда один кластер значительно больше остальных, и они находятся близко друг от друга – возникает эффект «расщепления» большого кластера.
Разработаны интересные расширения алгоритма k-means для работы с категорийными атрибутами (k-modes) и смешанными атрибутами (k-prototypes). Например, в k-prototypes расчет расстояний между объектами осуществляется по-разному в зависимости от типа атрибута.
Разработаны масштабируемые аналоги k-means и EM (scalable k-means и scalable EM), масштабируемые агломеративные методы (CURE, CACTUS). Эти современные алгоритмы требуют всего несколько (от двух до десяти) сканирований базы данных до получения финальной кластеризации.
Получение масштабируемых алгоритмов основано на идее отказа от локальной функции оптимизации. Парное сравнение объектов между собой в алгоритме k-means есть не что иное, как локальная оптимизация, т.к. на каждой итерации необходимо рассчитывать расстояние от центра кластера до каждого объекта. Это ведет к большим вычислительным затратам. При задании глобальной функции оптимизации добавление новой точки в кластер не требует больших вычислений: оно рассчитывается на основе старого значения, нового объекта и так называемых кластерных характеристик (clusters features). Конкретные кластерные характеристики зависят от того или иного алгоритма. Так появились алгоритмы BIRCH, LargeItem, CLOPE и многие другие.
Перейдём к визуальной аналитике.
Основная идея визуального анализа – представление данных в различных визуальных формах, помогающих глубже понимать анализируемые данных и работать с визуальным представлением.
Раньше отображение визуальных данных в реальном времени не могло позволить себе более сложные графические решения, чем простую трехмерную или двухмерную графику из-за сложности и дороговизны. Благодаря совершенствованию операционной системы и аппаратной части, более продвинутые средства визуального анализа стали доступны. На сегодняшний день существует много различных видов графических образов, которые позволяют представлять результаты анализа в виде, удобном для понимания человеком.
Благодаря совершенствованию технологий стали доступны оценки расстояния и размеров объекта, в реальном времени рассматривать исследуемые данные со всех сторон, что открывает использования для анализа перцепционные навыки в обнаружении неопределенных образцов в визуальном пространстве. Это даёт возможность более чётко сформулировать цели исследования, когда о первичных данных мало известно, а цели непонятны.
Работа с зашумленными и неоднородными данными, с помощью визуальных данных и участия человека, легка и более точка в сравнении с автоматическими методами. Также не требуется статистических и математических алгоритмов, поскольку отображённые графические данные интуитивно понятны.
Все перечисленные преимущества позволяют еще больше облегчить работу аналитика и повысить качество получаемых знаний при совместном использовании визуального анализа и методов автоматического анализа.
Визуальный анализ данных обычно выполняется в три этапа:
- беглый анализ — позволяет идентифицировать интересные шаблоны и сфокусироваться на одном или нескольких из них;
- увеличение и фильтрация — идентифицированные на предыдущем этапе шаблоны отфильтровываются и рассматриваются в большем масштабе;
- детализация по необходимости — если пользователю нужно получить дополнительную информацию, он может визуализировать более детальные данные.
Процесс визуализации изображен на рисунке 11. Так же, как и при анализе данных, информация извлекается из некоторого источника, например, из базы данных или из файлов. Затем к ней могут быть применены алгоритмы Data Mining для выявления скрытых закономерностей (классификации, кластеризации и т. п.). Как результаты применения алгоритмов, так и исходные данные подвергаются обработке в ядре визуализации. Основной целью обработки является приведение многомерных данных к такому виду, который можно было бы представить на экране монитора.
Рисунок 11 – процесс визуализации данных
Характеристики средств визуализации данных
Наборы визуализируемых данных, как и в Data Mining, представляют собой матрицы, в которых ряды являются данными (например, записями об экспериментах, покупки в магазине и т. п.), а колонки — атрибутами данных. При этом данные могут характеризоваться одним или несколькими атрибутами. Кроме того, сами данные могут иметь более сложную структуру: иерархическую, текстовую, графическую и т. п. Таким образом, выделяют следующие виды данных, с которыми могут работать средства визуализации:
- одномерные данные — одномерные массивы, временные ряды и т. п.;
- двумерные данные — точки двумерных графиков, географические координаты и т. п.;
- многомерные данные — финансовые показатели, результаты экспериментов и т. п.;
- тексты и гипертексты — газетные статьи, Web-документы и т. п.;
- иерархические и связанные — структура подчиненности в организации, электронная переписка людей, гиперссылки документов и т. п.;
- алгоритмы и программы — информационные потоки, отладочные операции и т. п.
Одномерные данные состоят из одного атрибута. Пример: временные ряды, атрибут – время. Возможно, что несколько значений будут связаны с одной отметкой времени.
Двумерные данные – два отдельных измерения. Типичным примером могут служить географические данные, характеризующиеся двумя атрибутами: долгота и широта. Обычно такие данные отображаются в виде точек в двумерной системе координат.
Этим дум видам следует опасаться большого объема данных, поскольку возможны потери при попытке уменьшения масштаба для корректного отображения данных.
Многомерные данные. Отображение в виде двух/трехмерных точек невозможно. Например, реляционные таблицы баз данных. Атрибуты – колонки данных. Для корректного отображения требуются специальные методы визуализации, например, параллельные координаты.
Тексты и гипертексты – не могут быть отражены в виде измерений и не все методы визуализации для них могут использоваться, поэтому необходимо подготовить данные к виду пригодному для методов визуализации.
Иерархические и связанные данные. Для представления таких взаимосвязей широко используются графы. Граф состоит из набора узлов и соединяющих их линий, называемых дугами. Примерами таких данных могут являться: электронная почта, пересылаемая между людьми, гиперссылки между Web-документами, файловая структура диска и т. п. Для отображения таких связей используются специальные методы визуализации.
Другой класс данных — алгоритмы и программы. Копирование больших программных проектов является проблемой. Целью визуализации является поддержка в разработке программных средств, например, отображение потока информации в программе для лучшего понимания алгоритмов и написанного кода, отображение структуры тысячи строк исходного кода в виде графа и поддержки процесса отладки, визуализация ошибок. Существует большое количество инструментов и систем, которые реализуют эти задачи.
Для визуализации перечисленных типов данных используются различные визуальные образы и методы их создания. Очевидно, что количество визуальных образов, которыми могут представляться данные, ограничиваются только человеческой фантазией. Основное требование к ним — это наглядность и удобство анализа данных, которые они представляют. Методы визуализации могут быть как самые простые (линейные графики, диаграммы, гистограммы и т. п.), так и более сложные, основанные на сложном математическом аппарате. Кроме того, при визуализации могут использоваться комбинации различных методов. Выделяют следующие типы методов визуализации:
- стандартные 2D/3D-образы — гистограммы, линейные графики и т. п.;
- геометрические преобразования — диаграмма разброса данных, параллельные координаты и т. п.;
- отображение иконок — линейчатые фигуры (needle icons) и звезды (star icons);
- методы, ориентированные на пикселы — рекурсивные шаблоны, циклические сегменты и т. п.;
- иерархические образы — древовидные карты и наложение измерений [2, стр. 193].
Простейшие методы визуализации, к которым относятся 2D/3D-образы, широко используются в существующих системах (например, в Microsoft Excel). К этим методам относятся: графики, диаграммы, гистограммы и т. п. Основным их недостатком является невозможность приемлемой визуализации сложных данных и большого количества данных.
Методы геометрических преобразований визуальных образов направлены на трансформацию многомерных наборов данных с целью отображения их в декартовом и в недекартовом геометрических пространствах. Данный класс методов включает в себя математический аппарат статистики. К нему относятся такие популярные методы, как диаграмма разброса данных (scatter plot), параллельные координаты (Parallel Coordinates), гипердоли (Hyperslice) и др.
Другим классом методов визуализации данных являются методы отображения иконок. Их основной идеей является отображение значений элементов многомерных данных в свойства образов. Такие образы могут представлять собой: человеческие лица, стрелки, звезды и т. п. Визуализация генерируется отображением атрибутов элементов данных в свойства образов. Такие образы можно группировать для целостного анализа данных. Результирующая визуализация представляет собой шаблоны текстур, которые имеют различия, соответствующие характеристикам данных и обнаруживаемые преаттентивным восприятием.
Основной идеей методов, ориентированных на пикселы, является отображение каждого измерения значения в цветной пиксел и их группировка по принадлежности к измерению. Так как один пиксел используется для отображения одного значения, то, следовательно, данный метод позволяет визуализировать большое количество данных (свыше одного миллиона значений).
Методы иерархических образов предназначены для представления данных, имеющих иерархическую структуру. В случае многомерных данных должны быть правильно выбраны измерения, которые используются для построения иерархии.
В результате применения методов визуализации будут построены визуальные образы, отражающие данные. Однако этого не всегда бывает достаточно для полного анализа. Пользователь должен иметь возможность работать с образами: видеть их с разных сторон, в разном масштабе и т. п. Для этого у него должны быть соответствующие возможности взаимодействия с образами:
- динамическое проецирование;
- интерактивная фильтрация;
- масштабирование образов;
- интерактивное искажение;
- интерактивное комбинирование.
Основная идея динамического проецирования заключается в динамическом изменении проекций при проведении исследования многомерных наборов данных. Примером может служить проецирование в двумерную плоскость всех интересующих проекций многомерных данных в виде диаграмм разброса (scatter plots). Необходимо обратить внимание, что количество возможных проекций экспоненциально увеличивается с ростом числа измерений, и следовательно, при большом количестве измерений проекции будут тяжело воспринимаемы.
При исследовании большого количества данных важно иметь возможность разделять наборы данных и выделять интересующие поднаборы — фильтровать образы. При этом важно, чтобы данная возможность предоставлялась в режиме реального времени работы с визуальными образами (т. е. интерактивно). Выбор поднабора может осуществляться или напрямую из списка, или с помощью определения свойств интересующего поднабора. Выбор из списка неудобен при большом количестве поднаборов, в то же время запросы не всегда позволяют получить желаемый результат.
Примером масштабирования образов является «магическая линза» (Magic Lenses). Ее основная идея состоит в использовании инструмента, похожего на увеличительное стекло, чтобы выполнять фильтрацию непосредственно при визуализации. Данные, попадающие под увеличительное стекло, обрабатываются фильтром, и результат отображается отдельно от основных данных. Линза показывает модифицированное изображение выбранного региона, тогда как остальные визуализированные данные не детализируются.
Масштабирование — это хорошо известный метод взаимодействия, используемый во многих приложениях. При работе с большим объемом данных этот метод хорош для представления данных в сжатом общем виде, и, в то же время, он предоставляет возможность отображения любой их части в более детальном виде. Масштабирование может заключаться не только в простом увеличении объектов, но в изменении их представления на разных уровнях. Так, например, на нижнем уровне объект может быть представлен пикселом, на более высоком уровне — неким визуальным образом, а на следующем — текстовой меткой.
Метод интерактивного искажения поддерживает процесс исследования данных с помощью искажения масштаба данных при частичной детализации. Основная идея этого метода заключается в том, что часть данных отображается с высокой степенью детализации, а одновременно с этим остальные данные показываются с низким уровнем детализации. Наиболее популярные методы — это гиперболическое и сферическое искажения, которые часто используются на иерархиях и графах, но могут применяться и в других визуальных образах.
Существует достаточно много методов визуализации, но все они имеют как достоинства, так и недостатки. Основная идея комбинирования заключается в объединении различных методов визуализации для преодоления недостатков одного из них. Различные проекции рассеивания точек, например, могут быть скомбинированы с методами окрашивания и компоновки точек во всех проекциях. Такой подход может быть использован для любых методов визуализации. Окраска точек во всех методах визуализации дает возможность определить зависимости и корреляции в данных. Таким образом, комбинирование нескольких методов визуализации обеспечивает большую информативность, чем в общем независимое использование методов. Типичными примерами визуальных образов, которые могут комбинироваться, являются: точки рассеивания, гистограммы, параллельные координаты, отображаемые пикселы и карты.
Любое средство визуализации может быть классифицировано по всем трем параметрам, т. е. по виду данных, с которым оно работает, по визуальным образам, которые оно может предоставлять, и по возможностям взаимодействия с этими визуальными образами. Очевидно, что одно средство визуализации может поддерживать разные виды данных, разные визуальные образы и разные способы взаимодействия с образами.
Процесс кластеризации в среде Tableau
Кластерный анализ разбивает точки на диаграмме рассеяния на кластеры, в которых точки из одного кластера сильнее похожи друг на друга, чем на точки других кластеров. Tableau присваивает каждому кластеру свой цвет.
Для кластерного анализа Tableau использует метод k-средних. По этому методу данные разбиваются на несколько сегментов. Для каждого сегмента подбирается центр кластера, до тех пор, пока суммарное квадратичное отклонение точек кластеров от центров этих кластеров не будет сведено к минимуму. Иными словами, метод k-средних, вместе с Tableau, пытается определить схожесть точек на основе их расстояния до центра кластера. Этот метод не всегда работает хорошо. Результат зависит от выбора исходных центров кластеров, их оптимальный выбор неизвестен.
Для того, чтобы провести кластеризацию, необходимо добавить данные на полки Columns, Rows, Filters и Marks. затем перейти на вкладку Analytics и перетащить модель Cluster на точечную диаграмму. Пример показан на рисунках: 12, 13, 14 соответственно.
Рисунок 12 – добавление модели «Кластер» на точечную диаграмму
Рисунок 13 – очистка от лишних значений
Рисунок 14 – результат кластеризации
В результате образовалось 5 кластеров.
Кластеризация – описательная процедура, которая не делает статистических выводов, однако с её помощью появляется возможность провести первичный, разведочный анализ и изучить структуру данных.
Благодаря разделению выбранных групп на кластеры возможно установить высокодоходную, средне доходную и низкодоходную выручку по товарам, выявить лидеров продаж, как по группам, так и по отдельным товарам, определить дешёвые, но популярные товары, менее популярные, но дорогие. А также выявить факторы, влияющие на вышеописанные возможности. Данный подход позволяет не только существенно сократить объекты анализа, а дополнительно индивидуально подойти к каждой группе товаров.
Процесс визуализации в среде Tableau
Поскольку Tableau – аналитическая платформа, специализирующаяся на средствах визуализации данных, большинство действия с данными, помимо подключения источников данных будут считаться визуализацией.
Проиллюстрируем несколько методов визуализации с помощью среды Tableau.
2D/3D
Добавляем на полку Columns дату, указываем сортировку по месяцам, на полку Rows перетащим выручку, в Filters добавим группу и выберем сортировку, например «Энергетические товары» и выберем тип представления данных lines (Рисунок 15).
Рисунок 15 – линейный 2D график продаж в разрезе месяцы
В результате получился линейный график продаж в разрезе месяцы, отображающий выручку товарной группы «Энергетические напитки».
Геометрические преобразования — диаграмма разброса данных, параллельные координаты и т. п.;
На полку Columns и Filter добавим Measure Names (Измеряемые имена), на полку Rows и Marks перетащим Measure Values (Измеряемые значения), дополнительно указав продажи, коэффициент прибыли и клиента в измеряемых значениях Marks (Рисунок 16).
Рисунок 16 – диаграмма параллельных координат
В итоге получили диаграмму параллельных координат, с помощью которой можно выявить паттерны и корреляцию между разными переменными.
Иерархические образы
Добавим в filters Группы, в Marks товар, количество, и выручку. Выберем тип визуализации treemaps (Рисунок 17).
Рисунок 17 – график древовидная карта
В итоге получили древовидную карту, отображающую иерархию товаров по объёму выручки относительно других товаров.
В данном параграфе были рассмотрены способы реализации некоторых методов визуализации на примере Tableau.