Кластеризация текстов

Содержание

Слайд 2

Содержание

1. Основные определения
2. Автоматическая кластеризация текстов:
постановка задачи
виды алгоритмов кластеризации
алгоритмы и примеры применения
3.

Содержание 1. Основные определения 2. Автоматическая кластеризация текстов: постановка задачи виды алгоритмов
Оценка качества кластеризации
4. Домашнее задание

Слайд 3

Вопрос

В чем основные отличия кластеризации от классификации?

Вопрос В чем основные отличия кластеризации от классификации?

Слайд 4

Основные определения

Классификация (или рубрицирование) – отнесение объекта к заранее известным классам (рубрикам)
классы:

Основные определения Классификация (или рубрицирование) – отнесение объекта к заранее известным классам
с заданными характеристиками,
иерархическая система классов
обычно классифицируют по «содержанию» объектов
Кластеризация – разбиение заданного множества объектов на подмножества (кластеры)
объекты в кластерах похожи по смыслу/теме/структуре/…
характеристики, количество, структура кластеров заранее не заданы

Слайд 5

Вопрос

Какие цели может преследовать кластеризация?

Вопрос Какие цели может преследовать кластеризация?

Слайд 6

Цели кластеризации

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

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

Слайд 7

Пример: «интеллектуальная» группировка результатов при информационном поиске
Сейчас кластеризация часто – один из

Пример: «интеллектуальная» группировка результатов при информационном поиске Сейчас кластеризация часто – один из этапов анализа данных
этапов анализа данных

Слайд 8

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

Имеется множество объектов
D = {d1, …, d|D|}
Существует

Формальная постановка задачи автоматической кластеризации Имеется множество объектов D = {d1, …,
множество «тематических классов»
C = {c1, …, с|C|}
Предполагается, что можно автоматически разбить D на кластеры и они будут соответствовать C
Задача сводится к поиску такого C, которое являлось бы оптимальным в соответствии с некоторым критерием качества
Нужно определить критерий качества разбиения

Слайд 9

Какими должны быть кластеры?

Внутри каждого кластера должны оказаться «похожие» объекты, а объекты

Какими должны быть кластеры? Внутри каждого кластера должны оказаться «похожие» объекты, а
разных кластеров должны быть «не похожи»
Другими словами:
схожесть между объектами из одного кластера должна быть как можно больше
схожесть между объектами из разных кластеров должна быть как можно меньше
Нужно определить критерий схожести между объектами
Алгоритм должен самостоятельно принимать решение о количестве и составе кластеров

Слайд 10

Кластеризация текстов (документов)

Документов представляются как вектора в пространстве признаков
di = (di1,

Кластеризация текстов (документов) Документов представляются как вектора в пространстве признаков di =
…, di|Τ|), где
dij – вес j-ого признака в i-ом документе 0≤dij≤1,
|T| – количество различных признаков в D
Для определения схожести документов обычно вычисляют расстояния между ними
Примеры: евклидова метрика, манхэттенское расстояние, косинусное расстояние 
Кто выбирает критерий схожести?

Слайд 11

Примеры мер (1)

Евклидово расстояние – геометрическое расстоянием в многомерном пространстве
Квадрат евклидова расстояния.

Примеры мер (1) Евклидово расстояние – геометрическое расстоянием в многомерном пространстве Квадрат
Применяется для придания большего веса более отдаленным друг от друга объектам
Манхэттенское расстояние (расстояние городских кварталов) – сумма разностей по координатам. Уменьшает влияние выбросов

Слайд 12

Примеры мер (2)

Расстояние Чебышева полезно для «различения» объектов, отличных в одной координате
Считающее

Примеры мер (2) Расстояние Чебышева полезно для «различения» объектов, отличных в одной
расстояние – число координат, по которым векторы x и y различаются
Косинусное расстояние
Всегда ли нужны именно подобные меры?

Слайд 13

Задание 1

1: Карл у Клары украл кораллы
2: Клара у Карла

Задание 1 1: Карл у Клары украл кораллы 2: Клара у Карла
украла кларнет
3: Клара у Карла украла кораллы
4: Простота – хуже воровства
Построить для каждого текста представление в виде вектора. Вес: присутствует признак в документе или нет

Слайд 14

Задание 1. Ответ

1: Карл у Клары украл кораллы
2: Клара у

Задание 1. Ответ 1: Карл у Клары украл кораллы 2: Клара у
Карла украла кларнет
3: Клара у Карла украла кораллы
4: Простота – хуже воровства
Построить для каждого текста представление в виде вектора. Вес: присутствует признак в документе или нет
w1=(1, 1, 1, 1, 0, 0, 0, 0)
w2=(1, 1, 1, 0, 1, 0, 0, 0)
w3=(1, 1, 1, 1, 0, 0, 0, 0)
w4=(0, 0, 0, 0, 0, 1, 1, 1)

Слайд 15

Задание 2

1: Карл у Клары украл кораллы
2: Клара у Карла украла

Задание 2 1: Карл у Клары украл кораллы 2: Клара у Карла
кларнет
3: Клара у Карла украла кораллы
4: Простота – хуже воровства
Построить для каждого текста представление в виде вектора. Вес: tf-idf

Слайд 16

Взгляд в прошлое


Взгляд в прошлое

Слайд 17

Задание 2. Ответ

1: Карл у Клары украл кораллы
2: Клара у Карла

Задание 2. Ответ 1: Карл у Клары украл кораллы 2: Клара у
украла кларнет
3: Клара у Карла украла кораллы
4: Простота – хуже воровства
Построить для каждого текста представление в виде вектора. Вес: tf-idf
w1=(0.03, 0.03, 0.03, 0.075, 0, 0, 0, 0)
w2=(0.03, 0.03, 0.03, 0, 0.15, 0, 0, 0)
w3=(0.03, 0.03, 0.03, 0.075, 0, 0, 0, 0)
w4=(0, 0, 0, 0, 0, 0.2, 0.2, 0.2)

Слайд 18

Задание 3

1. Вычислить косинусное расстояние для
w1=(1,1,1,1,0,0,0,0) и w2=(1,1,1,0,1,0,0,0)
w1=(1,1,1,1,0,0,0,0) и w3=(1,1,1,1,0,0,0,0)
2. Вычислить

Задание 3 1. Вычислить косинусное расстояние для w1=(1,1,1,1,0,0,0,0) и w2=(1,1,1,0,1,0,0,0) w1=(1,1,1,1,0,0,0,0) и
евклидово расстояние для
w3=(1,1,1,1,0,0,0,0) и w4=(0,0,0,0,0,1,1,1)
w3=(0.03,0.03,0.03,0.075,0,0,0,0) и w4=(0,0,0,0,0,0.2,0.2,0.2)
3. Вычислить манхэттенское расстояние для
w1=(0.03,0.03,0.03,0.075,0,0,0,0) и w4=(0,0,0,0,0,0.2,0.2,0.2)
w2=(0.03,0.03,0.03,0,0.15,0,0,0) и w3=(0.03,0.03,0.03,0.075,0,0,0,0)
https://habr.com/ru/post/101338/    https://delirium-00.livejournal.com/7215.html

Слайд 19

Задание 3. Обсуждение (1)

1: Карл у Клары украл кораллы
2: Клара у

Задание 3. Обсуждение (1) 1: Карл у Клары украл кораллы 2: Клара
Карла украла кларнет
3: Клара у Карла украла кораллы
4: Простота – хуже воровства
косинусное расстояние для
w1 и w2 ≈ 0,72 w1 и w3 = 0 w1 и w4 ≈ 1,57
w2 и w3 ≈ 0,72 w2 и w4 ≈ 1,57 w3 и w4 ≈ 1,57
евклидова метрика для
w1 и w2 ≈ 1,41 w1 и w3 = 0 w1 и w4 ≈ 2,65
w2 и w3 ≈ 1,41 w2 и w4 ≈ 2,65 w3 и w4 ≈ 2,65
манхэттенское расстояние для
w1 и w2 = 2 w1 и w3 = 0 w1 и w4 = 7
w2 и w3 = 2 w2 и w4 = 7 w3 и w4 = 7

Слайд 20

Задание 3. Обсуждение (2)

1: Карл у Клары украл кораллы
2: Клара у

Задание 3. Обсуждение (2) 1: Карл у Клары украл кораллы 2: Клара
Карла украла кларнет
3: Клара у Карла украла кораллы
4: Простота – хуже воровства
косинусное расстояние для
w1 и w2 ≈ 1,55 w1 и w3 = 0 w1 и w4 ≈ 1,57
w2 и w3 ≈ 1,55 w2 и w4 ≈ 1,57 w3 и w4 ≈ 1,57
евклидова метрика для
w1 и w2 ≈ 0,17 w1 и w3 = 0 w1 и w4 ≈ 0,36
w2 и w3 ≈ 0,17 w2 и w4 ≈ 0,38 w3 и w4 ≈ 0,36
манхэттенское расстояние для
w1 и w2 ≈ 0,23 w1 и w3 = 0 w1 и w4 ≈ 0,77
w2 и w3 ≈ 0,23 w2 и w4 ≈ 0,84 w3 и w4 ≈ 0,77

Слайд 21

Виды алгоритмов кластеризации

Иерархические и плоские алгоритмы
иерархические строят не одно разбиение выборки на

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

Слайд 22

Иерархические алгоритмы

Восходящие (агломеративные): построение кластеров снизу вверх
Начало: один документ – один

Иерархические алгоритмы Восходящие (агломеративные): построение кластеров снизу вверх Начало: один документ –
кластер
Последовательно объединяем пары кластеров
В итоге: один кластер – все документы
Нисходящие (дивизивные): построение кластеров сверху вниз
Начало: все документы – один кластер
Рекурсивно делим кластеры пополам
(с помощью алгоритма плоской кластеризации)
В итоге: один кластер – один документ
«История» объединения/деления кластеров дает их иерархию (бинарное дерево)

Слайд 23

Восходящие алгоритмы: критерии объединения

Сходство двух кластеров есть:
сходство между их наиболее похожими документами

Восходящие алгоритмы: критерии объединения Сходство двух кластеров есть: сходство между их наиболее
(одиночная связь)
создаются протяженные кластеры
не учитывает вся структура кластера
сходство между их наиболее непохожими документами (полная связь)
создаются компактные кластеры
учитывает вся структура кластера
среднее сходство всех пар документов (групповое усреднение)
сходство между их центроидами

Слайд 24

Вопросы

Какой тип сходства изображен на Рисунке 1?
Какой тип сходства изображен на Рисунке

Вопросы Какой тип сходства изображен на Рисунке 1? Какой тип сходства изображен
2?
Какие должны быть рисунки для других типов?
Рисунок 1 Рисунок 2

Слайд 25

Пример (1): тексты

Пример (1): тексты

Слайд 26

Пример (1): деревья

Матрица расстояний:
Одиночная связь Полная связь

Пример (1): деревья Матрица расстояний: Одиночная связь Полная связь

Слайд 27

Пример 2


Давайте построим дерево

Пример 2 Давайте построим дерево

Слайд 28

Пример 2: полученное дерево

Пример 2: полученное дерево

Слайд 29

Просто пример дерева

Выборка из 10000 писем: дерево (дендрограмма) и график зависимости расстояния

Просто пример дерева Выборка из 10000 писем: дерево (дендрограмма) и график зависимости
между объединяемыми кластерами от номера итерации алгоритма

Слайд 30

Плоский четкий алгоритм k-средних (k-means)

Входные данные:
количество кластеров k
множество документов как векторов

Плоский четкий алгоритм k-средних (k-means) Входные данные: количество кластеров k множество документов
di = (di1, …, di|Τ|)
Выполнение алгоритма:
1. Выбираем k начальных центроидов кластеров
2. Каждый документ относим к тому кластеру, чей
центроид является наиболее близким
3. Выполняем повторное вычисление центроидов
каждого кластера
Повторяем, пока не достигнем условия остановки:
достигнуто пороговое число итераций
центроиды кластеров больше не изменяются
достигнуто пороговое значение целевой функции

Слайд 31

Оптимизируемая функция

Алгоритм минимизирует среднее внутрикластерное расстояние
каждая точка присваивается к тому кластеру, центр

Оптимизируемая функция Алгоритм минимизирует среднее внутрикластерное расстояние каждая точка присваивается к тому
которого ближе
каждый центр переходит в среднее арифметическое точек кластера
где μj – центроид кластера cj
|cj| – количество документов в кластере cj

Слайд 32

Иллюстрация работы k-средних, k=2

Иллюстрация работы k-средних, k=2

Слайд 33

Иллюстрация работы k-средних, k=2

Иллюстрация работы k-средних, k=2

Слайд 34

Иллюстрация работы k-средних, k=2

Иллюстрация работы k-средних, k=2

Слайд 35

Иллюстрация работы k-средних, k=2

Иллюстрация работы k-средних, k=2

Слайд 36

Иллюстрация работы k-средних, k=2

Иллюстрация работы k-средних, k=2

Слайд 37

Иллюстрация работы k-средних, k=2

Иллюстрация работы k-средних, k=2

Слайд 38

Иллюстрация работы k-средних, k=2

Иллюстрация работы k-средних, k=2

Слайд 39

Иллюстрация работы k-средних, k=2

Центроиды классов
не изменились ? завершение работы

Иллюстрация работы k-средних, k=2 Центроиды классов не изменились ? завершение работы

Слайд 40

Пример использования: документы

Пример использования: документы

Слайд 41

Пример использования: применение алгоритма

Итерация 1. Случайным образом инициализированы μi:
μ1=[0,96 0,80 0,42

Пример использования: применение алгоритма Итерация 1. Случайным образом инициализированы μi: μ1=[0,96 0,80
0,79 0,66 0,85] μ2=[0,49 0,14 0,91 0,96 0,04 0,93]
? c1:={d1, d4, d5, d6}, c2:={d2, d3}
Итерация 2.
μ1=[0,24 0,45 0 0 0,43 0,35] μ2=[0,16 0 0,49 0,49 0 0]
? c1:={d1, d4, d5, d6}, c2:={d2, d3}
Разбиение не изменилось, условие остановки выполнено

Слайд 42

Пример использования: уменьшение цветов изображения

Охарактеризуйте
рисунки с точки зрения
цвета

Пример использования: уменьшение цветов изображения Охарактеризуйте рисунки с точки зрения цвета

Слайд 43

Пример использования: уменьшение цветов изображения
64 цвета (случайно)
96615 цветов
64 цвета (K-means)

Пример использования: уменьшение цветов изображения 64 цвета (случайно) 96615 цветов 64 цвета (K-means)

Слайд 44

Проблемы алгоритма k-средних

Не гарантируется достижение глобального минимума суммарного квадратичного отклонения e(D,C) ?
Результат

Проблемы алгоритма k-средних Не гарантируется достижение глобального минимума суммарного квадратичного отклонения e(D,C)
зависит от выбора исходных центров кластеров. Решение – эвристические правила (например, алгоритм k-means++)
Число кластеров надо знать заранее. Решение – специальные методы (например, метод локтя)
Не справляется с задачей, когда объект принадлежит к разным кластерам в равной степени или не принадлежит ни одному. Решение – нечеткие алгоритмы (например, c-means)
Хорошо работает только для кластеров, близких к сферическим. Решение – другие алгоритмы (например, DBSCAN)

Слайд 45

Плоский нечеткий алгоритм c-средних (c-means)

Является модификацией метода k-средних
Входные данные:
количество кластеров

Плоский нечеткий алгоритм c-средних (c-means) Является модификацией метода k-средних Входные данные: количество
k
степень нечеткости m
множество документов как векторов di = (di1, …, di|Τ|)
Выполнение алгоритма:
1. Выбираем k начальных центроидов кластеров
2. Каждый документ относим к тем m кластерам, чьи
центроиды являются наиболее близким
3. Выполняем повторное вычисление центроидов
каждого кластера
4. Повторяем, пока не достигнем условия остановки

Слайд 46

Пример применения: тексты

Пример применения: тексты

Слайд 47

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

Вычисляются меры двух видов:
Внешние меры: сравнение созданного разбиения с «эталонным»
анализируется

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

Слайд 48

Сравнение алгоритмов кластеризации

Решение задачи кластеризации принципиально неоднозначно:
не существует однозначно наилучшего критерия качества

Сравнение алгоритмов кластеризации Решение задачи кластеризации принципиально неоднозначно: не существует однозначно наилучшего
кластеризации
количество кластеров заранее неизвестно
результат кластеризации существенно зависит от того, как определяется схожесть
нет общепризнанных тестовых данных
Главное основание для выбора алгоритма – знание о его теоретических характеристиках и оценка пригодности для решения поставленной задачи

Слайд 49

Домашнее задание. Вариант 1

1. Взять выбранный к прошлому разу набор данных

Домашнее задание. Вариант 1 1. Взять выбранный к прошлому разу набор данных

2. Написать программу кластеризации данных из этого набора. Использовать 2 разных метрики схожести и 2 метода разных видов
3. Подсчитать 2 внутренние и 2 внешние меры качества работы методов
4. Написать отчет, в котором:
описать выбранный набор данных
описать выбранные метрики, методы кластеризации (не рассказанные – подробно), меры качества
сравнить качество работы методов между собой
сделать выводы

Слайд 50

Домашнее задание. Вариант 2

Написать программу определения расстояния между текстами
1. Взять несколько

Домашнее задание. Вариант 2 Написать программу определения расстояния между текстами 1. Взять
текстов (около 10)
2. Написать функцию, реализующую одну из мер схожести именно текстов (!!!)
3. Найти попарные расстояния между всеми текстами
4. Написать отчет, в котором:
описать структуру программы
подробно описать выбранные меры
сделать выводы
Стандартные (чужие) меры определения схожести можно использовать только для сравнении их качества работы со своей

Слайд 51

Домашнее задание. Вариант 3

1. Найти готовые средства визуализации многомерных векторов (текстов)
2.

Домашнее задание. Вариант 3 1. Найти готовые средства визуализации многомерных векторов (текстов)
Рассказать про них на следующем занятии
3. Показать их работу
Имя файла: Кластеризация-текстов.pptx
Количество просмотров: 44
Количество скачиваний: 0