Модели и задачи Data Mining

Август 10, 2022

Главная
Информатика
Модели и задачи Data Mining

Содержание

2. Кластерный анализ 1. Кластерный анализ предназначен для разбиения данных на поддающиеся интерпретации группы (1), таким образом,
4. В факторном анализе группируются столбцы, т.е. цель –анализ структуры множества признаков и выявление обобщенных факторов. В
5. Как очертить границу кластеров? Сколько их следует выделить?
6. Кластеры могут быть непересекающимися (non-overlapping), и пересекающимися (overlapping). Могут быть получены кластеры различной формы: длинными "цепочками",
11. Выделяют четыре основных метода анализа Big Data [1]: Описательная аналитика (descriptive analytics) — отвечает на вопрос
12. Диагностическая аналитика Диагностическая (diagnostic) аналитика — форма расширенной аналитики, которая строится на основе описательной и анализирует
13. Меры сходства Евклидово расстояние: расстояние(x,y) = {∑i (xi - yi)2 }1/2 Квадрат евклидова расстояния чтобы придать
14. Мера близости вычисленная как евклидово расстояние между двумя точками i и j на плоскости, когда известны
15. Когда осей (измерений) больше, чем две, расстояние рассчитывается как: сумма квадратов разницы координат из стольких слагаемых,
16. При неоднородности единиц измерения признаков становится невозможно корректно рассчитать расстояния между точками. Существуют различные способы нормирования
17. Результат зависит от нормировки признаков
18. Расстояние между кластерами Метод ближнего соседа. Расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими
19. Методы кластеризации: иерархические Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие или разделении
20. Иерархические методы кластерного анализа используются при небольших объемах наборов данных. Преимуществом иерархических методов кластеризации является их
22. Существует проблема определения числа кластеров. Иногда можно априорно определить это число. Однако в большинстве случаев число
24. Итеративные методы. Алгоритм k-средних (k-means) Наиболее распространен среди неиерархических методов алгоритм k-средних, также называемый быстрым кластерным
25. K-средних Выбор начальных центроидов может осуществляться следующим образом: выбор k-наблюдений для максимизации начального расстояния; случайный выбор
26. Достоинства алгоритма k-средних: • простота использования; • быстрота использования; • понятность и прозрачность. Недостатки алгоритма k-средних:
27. Проверка качества кластеризации После получений результатов кластерного анализа методом k-средних следует проверить правильность кластеризации (т.е. оценить,
28. Алrоритм g-means Недостаток k-means - отсутствие ясного критерия для выбора оптимального числа кластеров. G-means - популярный
29. Нормальное распределение Для нормального распределения количество значений, отличающиеся от среднего на число, меньшее чем одно стандартное
30. Ирисы Фишера
34. Максимальное ожидание EM-алгоритм EM (Expectation maximization - максимальное правдоподобие) – популярный алгоритм кластеризации. В основе идеи
35. Главным достоинством EM-алгоритма является простота исполнения. Алгоритм может оптимизировать не только параметры модели, но и делать
37. Кластеризации больших массивов категорийных данных Алгоритмы, основанные на парном вычислении расстояний (k-means и аналоги) эффективны в
38. Требований к алгоритмам кластеризации номинальных (качественных) данных Минимально возможное количество «сканирований» таблицы базы данных; Работа в
39. Алгоритм CLOPE (кластеризация с наклоном) CLOPE (Clustering with sLOPE) предложен в 2002 году группой китайских ученых.
40. Математическое описание алгоритма
41. При использовании метода CLOPE количество кластеров подбирается автоматически и зависит от коэффициента отталкивания — параметра, определяющего
42. ЗАКЛЮЧЕНИЕ В этой статье предлагается новый алгоритм категориальной кластеризации данных, называемый CLOPE, основанный на интуитивной идее
44. Скачать презентацию

Слайд 2

Кластерный анализ
1. Кластерный анализ предназначен для разбиения данных на поддающиеся интерпретации

группы (1), таким образом, чтобы элементы, входящие в одну группу были максимально «схожи» (2), а элементы из разных групп были максимально «отличными» друг от друга (3).
2. Кластерный анализ – группа методов, используемых для классификации объектов или событий в относительно гомогенные (однородные) группы, которые называют кластерами (clusters).
3. Цель кластеризации - поиск существующих структур.

Слайд 3

Слайд 4

В факторном анализе группируются столбцы, т.е. цель –анализ структуры множества признаков

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

Слайд 5

Как очертить границу кластеров?
Сколько их следует выделить?

Слайд 6

Кластеры могут быть непересекающимися (non-overlapping), и пересекающимися (overlapping).
Могут быть получены кластеры

различной формы: длинными "цепочками", удлиненной формы, произвольной формы.
Могут быть созданы кластеры определенных размеров (например, малых или крупных).

Типы кластерных структур

Слайд 7

Слайд 8

Слайд 9

Слайд 10

Слайд 11

Выделяют четыре основных метода анализа Big Data [1]:
Описательная аналитика (descriptive analytics)

— отвечает на вопрос «Что происходит?», анализирует данные, поступающие в реальном времени, и исторические данные.

1. Виды аналитики: описательная, прогнозная, предписывающая аналитика (projectpro.io)

Прогнозная или предикативная аналитика (predictive analytics) — помогает спрогнозировать наиболее вероятное развитие событий на основе имеющихся данных.

Предписательная аналитика (prescriptive analytics) — позволяет выявить проблемные точки в любой деятельности и рассчитать, при каком сценарии их можно избежать их в будущем.

Диагностическая аналитика (diagnostic analytics) — помогает выявлять аномалии и случайные связи между событиями и действиями.

Слайд 12

Диагностическая аналитика
Диагностическая (diagnostic) аналитика — форма расширенной аналитики, которая строится на

основе описательной и анализирует данные для ответа на вопрос «Почему это произошло?», т.е. позволяет выявить факторы, оказывающие влияние на целевые параметры.
Диагностическая аналитика позволяет изучить проблемы, определить слабые места и выявить цепочки событий.
Методы диагностической аналитики в Loginom:
EM Кластеризация.
Кластеризация k-means, кластеризация g-means.
Кластеризация транзакций.

Слайд 13

Меры сходства
Евклидово расстояние: расстояние(x,y) = {∑i (xi - yi)2 }1/2
Квадрат евклидова

расстояния чтобы придать большие веса более отдаленным друг от друга объектам расстояние (x,y) =∑i (xi - yi)2
Манхэттенское расстояние "хэмминговое" расстояние(x,y) =∑i |xi - yi|
Расстояние Чебышева используют когда необходимо определить два объекта как "различные", если они отличаются по какому-то одному измерению: расстояние(x,y) = Максимум|xi - yi|
Степенное расстояние для увеличения или уменьшения веса объектов при сильном отличии: расстояние(x,y) = (∑i |xi - yi|p)1/r
Процент несогласия - расстояние вычисляется, если данные являются категориальными: расстояние(x,y) = (Количество xi≠ yi)/ i

Слайд 14

Мера близости вычисленная как евклидово расстояние между
двумя точками i и

j на плоскости, когда известны их координаты X и Y.

Слайд 15

Когда осей (измерений) больше, чем две, расстояние рассчитывается как: сумма квадратов

разницы координат из стольких слагаемых, сколько осей (измерений) присутствует.

Кластер имеет следующие математические характеристики:
центр,
радиус,
среднеквадратическое отклонение,
размер кластера.
Центр кластера - это среднее геометрическое место точек в пространстве переменных.
Радиус кластера - максимальное расстояние точек от центра кластера.

Слайд 16

При неоднородности единиц измерения признаков становится невозможно корректно рассчитать расстояния между

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

Слайд 17

Результат зависит от нормировки признаков

Слайд 18

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

между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах.
Метод наиболее удаленных соседей или полная связь.
Метод Варда (Ward's method). В качестве расстояния между кластерами берется прирост суммы квадратов расстояний объектов до центров кластеров, получаемый в результате их объединения. Этот метод направлен на объединение близко расположенных кластеров и "стремится" создавать кластеры малого размера.
Метод невзвешенного попарного арифметического среднего. В качестве расстояния между двумя кластерами берется среднее расстояние между всеми парами объектов в них.

Слайд 19

Методы кластеризации: иерархические
Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров

в большие или разделении больших кластеров на меньшие.

Слайд 20

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

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

Слайд 21

Слайд 22

Существует проблема определения числа кластеров. Иногда можно априорно определить это число.

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

Слайд 23

Слайд 24

Итеративные методы. Алгоритм k-средних (k-means)
Наиболее распространен среди неиерархических методов алгоритм k-средних,

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

Слайд 25

K-средних
Выбор начальных центроидов может осуществляться следующим образом:
выбор k-наблюдений для максимизации начального

расстояния;
случайный выбор k-наблюдений;
выбор первых k-наблюдений.
В результате каждый объект назначен определенному кластеру.
Вычисляются центры кластеров, которыми затем и далее считаются покоординатные средние кластеров. Объекты опять перераспределяются.
Процесс вычисления центров и перераспределения объектов продолжается до тех пор, пока не выполнено одно из условий:
кластерные центры стабилизировались, т.е. все наблюдения принадлежат кластеру, которому принадлежали до текущей итерации;
число итераций равно максимальному числу итераций.

Слайд 26

Достоинства алгоритма k-средних:
• простота использования;
• быстрота использования;
• понятность

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

EM 15

Слайд 27

Проверка качества кластеризации
После получений результатов кластерного анализа методом k-средних следует

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

Слайд 28

Алrоритм g-means
Недостаток k-means - отсутствие ясного критерия для выбора оптимального числа

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

Слайд 29

Нормальное распределение
Для нормального распределения количество значений, отличающиеся от среднего на число,

меньшее чем одно стандартное отклонение, составляют 68,27 % выборок.

Слайд 30

Ирисы Фишера

Слайд 31

Слайд 32

Слайд 33

Слайд 34

Максимальное ожидание EM-алгоритм
EM (Expectation maximization - максимальное правдоподобие) – популярный алгоритм

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

EM 92

Слайд 35

Главным достоинством EM-алгоритма является простота исполнения.
Алгоритм может оптимизировать не только

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

Слайд 36

Слайд 37

Кластеризации больших массивов категорийных данных
Алгоритмы, основанные на парном вычислении расстояний

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

Слайд 38

Требований к алгоритмам кластеризации номинальных (качественных) данных
Минимально возможное количество «сканирований» таблицы

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

Слайд 39

Алгоритм CLOPE (кластеризация с наклоном)
CLOPE (Clustering with sLOPE) предложен в 2002

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

CLOPE 1

Слайд 40

Математическое описание алгоритма

Слайд 41

При использовании метода CLOPE количество кластеров подбирается автоматически и зависит от

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

Слайд 42

ЗАКЛЮЧЕНИЕ В этой статье предлагается новый алгоритм категориальной кластеризации данных, называемый

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

Модели и задачи Data Mining

Содержание

Кластерный анализ 1. Кластерный анализ предназначен для разбиения данных на поддающиеся интерпретации

В факторном анализе группируются столбцы, т.е. цель –анализ структуры множества признаков

Как очертить границу кластеров?Сколько их следует выделить?

Кластеры могут быть непересекающимися (non-overlapping), и пересекающимися (overlapping).Могут быть получены кластеры

Выделяют четыре основных метода анализа Big Data [1]:Описательная аналитика (descriptive analytics)

Диагностическая аналитикаДиагностическая (diagnostic) аналитика — форма расширенной аналитики, которая строится на

Меры сходстваЕвклидово расстояние: расстояние(x,y) = {∑i (xi - yi)2 }1/2Квадрат евклидова

Мера близости вычисленная как евклидово расстояние между двумя точками i и

Когда осей (измерений) больше, чем две, расстояние рассчитывается как: сумма квадратов

При неоднородности единиц измерения признаков становится невозможно корректно рассчитать расстояния между

Результат зависит от нормировки признаков

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

Методы кластеризации: иерархическиеСуть иерархической кластеризации состоит в последовательном объединении меньших кластеров

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

Существует проблема определения числа кластеров. Иногда можно априорно определить это число.

Итеративные методы. Алгоритм k-средних (k-means)Наиболее распространен среди неиерархических методов алгоритм k-средних,

K-среднихВыбор начальных центроидов может осуществляться следующим образом:выбор k-наблюдений для максимизации начального

Достоинства алгоритма k-средних: • простота использования; • быстрота использования; • понятность

Проверка качества кластеризации После получений результатов кластерного анализа методом k-средних следует

Алrоритм g-meansНедостаток k-means - отсутствие ясного критерия для выбора оптимального числа

Нормальное распределениеДля нормального распределения количество значений, отличающиеся от среднего на число,