WEBVTT

00:00:08.205 --> 00:00:09.846
Здравствуйте, уважаемые студенты.

00:00:10.087 --> 00:00:14.611
Вашему вниманию предлагается лекция по
дисциплине использования больших данных в

00:00:14.691 --> 00:00:16.172
информационных системах.

00:00:16.813 --> 00:00:20.697
Продолжаем тему методы и методики
обработки информации в технологиях больших

00:00:20.817 --> 00:00:25.021
данных. Лекцию ведёт кандидат технических
наук, доцент Чернчук

00:00:25.425 --> 00:00:27.784
Игорь Владимирович. Лекция шестая.

00:00:29.783 --> 00:00:34.180
План лекции — кластеризация как инструмент
анализа данных.

00:00:34.380 --> 00:00:38.698
Обучение методам опорных векторов,
использование системы RapedMi для решения

00:00:38.818 --> 00:00:41.976
задач кластеризации с использованием
метода опорных векторов.

00:00:46.663 --> 00:00:50.582
Так, рассмотрим формальную постановку
задачи кластеризации.

00:00:50.702 --> 00:00:57.420
Значит, дано, соответственно, X —
пространство объектов — X большое,

00:00:58.860 --> 00:01:02.419
X верхний индекс L пред предполагается как

00:01:04.185 --> 00:01:09.267
Множество элементов иксы, где L
предполагается, что какой-нибудь один

00:01:09.547 --> 00:01:15.069
признак, признаков может быть много,
обучающая выборка.

00:01:15.589 --> 00:01:20.310
Соответственно, функция расстояния между
объектами, то есть какая-то вот

00:01:21.765 --> 00:01:28.012
Отображение декартового произведения на
характеристику в интервале от нуля до

00:01:28.092 --> 00:01:32.617
бесконечности. То есть функция расстояния
между объектами.

00:01:34.700 --> 00:01:37.022
Игрек большое — множество кластеров.

00:01:38.403 --> 00:01:44.680
Соответственно, и Aточие X — отображение в
Y — алгоритмы кластеризации.

00:01:44.800 --> 00:01:50.277
Такие, что каждый кластер состоит из
близких объектов, объектов.

00:01:50.437 --> 00:01:53.155
Объекты разных кластеров существенно
различные.

00:01:53.675 --> 00:01:57.593
Значит, кластеризация относится к типу
обучения без учителя.

00:02:00.852 --> 00:02:04.413
Рассмотрим такой вопрос, как
некорректность задач кластеризации в

00:02:04.453 --> 00:02:09.614
какой-то степени. Решение задач
кластеризации принципиально неоднозначно.

00:02:10.094 --> 00:02:14.495
То есть она характеризуется точной
постановкой задач, кластеризации нет.

00:02:15.176 --> 00:02:18.177
То есть вроде как просто разбиваем на
кластеры.

00:02:18.893 --> 00:02:23.216
Соответственно, это вот не как задача
классификации, где тут всё чётко

00:02:23.296 --> 00:02:29.300
определено. Здесь какие-то, в принципе,
просто имеется в виду кластеры, сгустки,

00:02:29.380 --> 00:02:34.823
что называется. И вот мы, соответственно,
пытаемся разделить эти сгустки.

00:02:35.705 --> 00:02:38.786
Существует много критериев качества
кластеризации.

00:02:39.227 --> 00:02:43.709
Существует много элистических методов
кластеризации: число кластеров, то есть

00:02:43.829 --> 00:02:47.431
мощность множества игрек, как правило,
неизвестно заранее.

00:02:47.671 --> 00:02:52.394
Результат кластеризации существенно
зависит от метрики RO, то есть расстояния,

00:02:52.754 --> 00:02:55.035
которое эксперт задаёт субъективно.

00:02:59.458 --> 00:03:01.177
Цели задач кластеризации.

00:03:01.297 --> 00:03:06.691
Значит, упростить дальнейшую обработку
данных, разбить множество X верхний индекс

00:03:06.771 --> 00:03:13.005
L на группы схожих объектов, чтобы
работали с каждой группой в отдельности.

00:03:13.724 --> 00:03:16.602
Задачи классификации регрессии и
прогнозирования.

00:03:17.390 --> 00:03:19.589
Сократить объём хранимых данных.

00:03:19.749 --> 00:03:22.586
То есть оставив по одному представителю от
каждого кластера.

00:03:22.826 --> 00:03:24.865
Как вариант, задача сжатия данных.

00:03:25.664 --> 00:03:28.982
Выделить нетипичные объекты, которые не
подходят.

00:03:30.070 --> 00:03:33.711
Ни к одному из кластеров, то есть задача
так называемой одноклассовой

00:03:33.871 --> 00:03:38.113
классификации. Построить иерархию
множества объектов.

00:03:38.313 --> 00:03:39.834
Задача таксономии.

00:03:42.435 --> 00:03:43.956
Типы кластерных структур.

00:03:47.850 --> 00:03:51.611
Внутрикластерные, внутрикластерные
расстояния, как правило, меньше

00:03:51.691 --> 00:03:56.013
межкластерных. То есть, вот они,
соответственно.

00:03:57.894 --> 00:04:03.096
Как видите, вот есть у нас один сгусток,
есть второй сгусток, то тут вот здесь вот

00:04:03.216 --> 00:04:03.856
довольно это всё

00:04:04.820 --> 00:04:06.702
Соответственно, можно наблюдать визуально.

00:04:06.782 --> 00:04:08.665
Ну, это практически идеальный вариант.

00:04:09.105 --> 00:04:14.873
Есть варианты, соответственно, вот
ленточные кластеры, как видите, такие

00:04:14.953 --> 00:04:17.396
размазанные несколько в длину.

00:04:18.872 --> 00:04:21.229
Соответственно, один кластер, второй
кластер.

00:04:21.469 --> 00:04:26.064
Причём один кластер может быть даже где-то
как-то частично примыкать, смыкаться с

00:04:26.144 --> 00:04:30.618
другим ленточным кластером кластеры с
центром.

00:04:30.778 --> 00:04:34.214
Вот такой вариант конфигурации тоже вполне
возможен быть.

00:04:35.933 --> 00:04:40.093
Соответственно, как видите, вот здесь вот
центры этих кластеров ярко выражены.

00:04:40.333 --> 00:04:44.054
Ну и, соответственно, по этим центрам
легко можно будет ориентироваться в

00:04:44.174 --> 00:04:47.774
решении задач кластеризации, если мы такие
центры найдём.

00:04:51.614 --> 00:04:54.055
Кластеры могут соединяться перемычками.

00:04:54.928 --> 00:04:59.126
То есть там вот во втором случае, там оно
было не так явно, здесь практически явно.

00:04:59.565 --> 00:05:02.764
То есть один сгусток, другой сгусток,
третий сгусток.

00:05:02.884 --> 00:05:06.802
И вот на границе тут уже вопрос, к какому
кластеру относить.

00:05:07.361 --> 00:05:09.360
Можно как к одному, так и ко второму.

00:05:10.284 --> 00:05:15.925
Кластеры могут накладываться на
разрежённый фон из редко расположенных

00:05:16.085 --> 00:05:18.806
объектов. То есть, вот есть какой-то фон.

00:05:19.246 --> 00:05:22.647
Один ярко выраженный кластер, второй,
может быть, даже третий.

00:05:23.047 --> 00:05:24.487
Ну, и какие-то вот такие вот

00:05:26.552 --> 00:05:31.188
Хаотично расположенные точки на больших
расстояниях относительно друг от друга.

00:05:31.348 --> 00:05:32.867
Вот такой разряженный фон.

00:05:33.466 --> 00:05:35.385
Кластеры могут перекрываться.

00:05:35.745 --> 00:05:39.982
Тут видно вертикально расположен густой
сгусток.

00:05:40.581 --> 00:05:44.338
Более разряженный, горизонтально
расположен вытянутый сгусток.

00:05:44.458 --> 00:05:46.817
Ну, в данном случае они вот так вот
перекрываются.

00:05:48.867 --> 00:05:53.149
Значит, какая-то зона соответствует двум
кластерам одновременно.

00:06:00.072 --> 00:06:06.915
Кластеры могут образовываться не по
сходству, а по иным типам регулярностей.

00:06:08.155 --> 00:06:13.315
То есть, вот, как показано здесь,
соответственно, прямоугольник, кластер

00:06:13.515 --> 00:06:18.795
какой-то. Это видно, что фигура, другая
кусок параболы, как вариант.

00:06:19.235 --> 00:06:21.276
Кластеры могут вообще отсутствовать.

00:06:22.316 --> 00:06:25.956
Довольно сложно такую конфигурацию
нарисовать, но вот что-то в этом роде.

00:06:27.926 --> 00:06:29.127
Так, ну и вот выводы.

00:06:29.288 --> 00:06:33.612
Каждый метод кластеризации имеет свои
ограничения и выделяет кластер лишь

00:06:33.733 --> 00:06:39.059
некоторых типов. Понятие типа кластерной
структуры зависит от метода, а также не

00:06:39.099 --> 00:06:40.620
имеет формального определения.

00:06:42.354 --> 00:06:45.672
Так, ну вот здесь мы попытались,
соответственно, составить некоторую

00:06:45.752 --> 00:06:51.428
классификацию типов кластерных структур,
соответственно, которые могут возникать в

00:06:51.508 --> 00:06:55.625
практических задачах. Различные алгоритмы
кластеризации могут быть более или менее

00:06:55.705 --> 00:06:57.184
успешны в этих ситуациях.

00:06:57.584 --> 00:07:02.261
Простые алгоритмы, как правило,
узкоспециализированные и дают адекватные

00:07:02.381 --> 00:07:04.699
результаты только в одной из двух
ситуаций.

00:07:05.378 --> 00:07:12.176
Более сложные алгоритмы, такие, например,
как Forel или агломеративная процедура

00:07:13.375 --> 00:07:18.854
Ланса Уильямса справляется с несколькими
типами ситуаций.

00:07:19.014 --> 00:07:22.693
Однако создание алгоритма, успешно
работающего во всех ситуациях, без

00:07:22.813 --> 00:07:25.812
исключения, представляется трудной, едва
ли разрешимой задачей.

00:07:28.035 --> 00:07:31.551
Так, кроме того, существует такая
проблема, как проблема чувствительности к

00:07:31.631 --> 00:07:32.990
выбору метрики.

00:07:33.709 --> 00:07:35.707
То есть, вот как здесь показан пример.

00:07:35.827 --> 00:07:38.424
Результат зависит от нормеровки признаков.

00:07:39.023 --> 00:07:45.657
Вот у нас как бы такие распределения:
студентки-студенты, Б.

00:07:48.190 --> 00:07:54.114
Соответственно, после перенурмировки, то
есть сжали ось вес

00:07:54.274 --> 00:07:58.757
вдвое, может получиться вот такая вот
картина.

00:08:07.602 --> 00:08:09.123
Методы кластеризации.

00:08:12.057 --> 00:08:16.574
Соответственно, вот можно выделить,
выделяются следующие: как иерархические

00:08:19.092 --> 00:08:24.328
неиерархические, иерархические своё
времени очередь-делятся на

00:08:25.727 --> 00:08:27.007
агломеративные.

00:08:34.754 --> 00:08:40.999
Дивизионные неерархические чёткая
кластеризация, нечёткая

00:08:41.079 --> 00:08:47.324
кластеризация. Методы основываются на

00:08:48.927 --> 00:08:53.010
...иерархической процедуре, то есть вот,
соответственно, итеративной процедуры.

00:08:53.450 --> 00:08:58.173
Вот иерархическая, если рассматривать,
которые пытаются найти наилучшее

00:08:58.213 --> 00:09:03.617
разбиение, ориентируясь на заданные
критерии оптимизации, не строя при этом

00:09:03.817 --> 00:09:07.219
полного дерева, наиболее популярный
алгоритм метода К-средних, то есть

00:09:07.379 --> 00:09:08.220
Маккина.

00:09:08.806 --> 00:09:12.128
Иерархические алгоритмы кластерного
анализа могут быть двух типов:

00:09:12.529 --> 00:09:16.852
гламеративные и дивизионные.

00:09:16.932 --> 00:09:21.456
Иерхические алгоритмы связаны с
построением дендограмм, то есть от

00:09:21.576 --> 00:09:22.496
греческого.

00:09:23.225 --> 00:09:27.467
Дендрон — дерево, который является
результатом эрахического кластерного

00:09:27.587 --> 00:09:33.389
анализа. Дентограмма описывает близость
отдельных точек и кластеров друг к другу,

00:09:33.869 --> 00:09:37.311
представляет в графическом виде
последовательность объединения, то есть

00:09:37.431 --> 00:09:40.312
разделение кластеров: дентограмма,
дентограмм.

00:09:41.252 --> 00:09:45.694
Древовидная диаграмма, содержащая эн
уровней, каждая из которых соответствует

00:09:45.774 --> 00:09:49.456
одному из шагов процесса
последовательности укрупнения кластеров.

00:09:49.776 --> 00:09:56.339
Дендограммы также называют древовидной
схемой, деревом объединения кластером,

00:09:56.379 --> 00:09:57.980
деревом иерхической структуры.

00:09:58.020 --> 00:10:02.502
Дендограмма представляет собой вложенную
группировку объектов.

00:10:02.519 --> 00:10:05.956
...которая изменяется на различных уровнях
иерархии.

00:10:06.836 --> 00:10:09.154
Так, ну вот примеры дантограмм.

00:10:09.514 --> 00:10:14.390
То есть, в зависимости от величины в
данном случае расстояния, скажем, можно

00:10:14.590 --> 00:10:19.026
выделить какие-то классы, подклассы, вот
иерархическая структура.

00:10:19.306 --> 00:10:24.102
То есть, соответственно, классы, кластеры
шестой-седьмой близко расположены...

00:10:24.874 --> 00:10:29.840
К ним недалеко от них относится восьмой,
через какое-то небольшое расстояние

00:10:30.080 --> 00:10:36.688
четвёртый. Одной также изолированно,
близко расположены Первый и второй.

00:10:37.209 --> 00:10:38.571
Соответственно, и вот

00:10:39.555 --> 00:10:45.670
Первый, второй не так далеко расположен от
объединения кластера четвёртый,

00:10:46.110 --> 00:10:49.547
скажем, с группой восемь-шесть-семь.

00:10:49.627 --> 00:10:53.543
Ну и так далее. Соответственно, вот такие
тендограммы строятся

00:10:57.540 --> 00:10:59.578
иногда выделяются какие-то группы.

00:11:00.274 --> 00:11:03.355
Цветом вполне могут быть выделены.

00:11:03.915 --> 00:11:10.077
Система статистики в своё время очень
удачно строила такие дендерограммы для при

00:11:10.237 --> 00:11:17.160
проведении кластера-анализа, ну, можно ещё
посмотреть

00:11:18.360 --> 00:11:20.121
ряд, соответственно, таких вариантов.

00:11:31.760 --> 00:11:34.602
Так, следующие эвристические, графовые
алгоритмы.

00:11:34.883 --> 00:11:36.844
Вот здесь показана иллюстрация.

00:11:38.405 --> 00:11:42.008
То есть, видите, принадлежность к одному
кластеру помещается цветом.

00:11:50.593 --> 00:11:52.631
Эвуристические графовые алгоритмы.

00:11:52.671 --> 00:11:56.986
Обширный класс алгоритмов кластеризации,
основан на представлении выборки в виде

00:11:57.066 --> 00:12:02.141
графа. Вершинами графа соответствуют
объекты выборки, а рёбрам, соответственно,

00:12:02.221 --> 00:12:04.338
попарные расстояние между объектами.

00:12:04.818 --> 00:12:05.977
Вот некоторое ро.

00:12:06.681 --> 00:12:08.995
Соответственно, ежи равняется ро.

00:12:10.153 --> 00:12:12.906
Какой-то вот между X It / жит.

00:12:13.830 --> 00:12:17.545
Достоинством графовых алгоритмов
кластеризации является наглядность,

00:12:17.625 --> 00:12:22.020
относительная простота реализации и
возможность вносить различные

00:12:22.100 --> 00:12:25.336
усовершенствования, опираясь на простые
геометрические соображения.

00:12:25.735 --> 00:12:29.770
Алгоритм выделения связанных компонентов
рассматривается как вариант.

00:12:30.570 --> 00:12:33.609
Задаётся параметр R большое в графе.

00:12:34.168 --> 00:12:40.486
Удаляются все рёбра, соответственно, J,
для которых, соответственно, расстояние ro

00:12:40.606 --> 00:12:42.525
и жит больше R.

00:12:43.245 --> 00:12:46.723
Соединёнными остаются только наиболее
близкие пары объектов.

00:12:47.478 --> 00:12:52.439
Идея алгоритма заключается в том, чтобы
подобрать такое значение R,

00:12:52.719 --> 00:12:56.399
соответственно, минимизирующее,
соответственно, R It житое.

00:12:57.279 --> 00:13:03.480
Р принадлежит, соответственно, какому-то,
как видите, отрезку от минимального R ри

00:13:03.720 --> 00:13:06.600
сжитого до максимального р-те сжитие, при
котором граф

00:13:08.022 --> 00:13:10.663
развалится на несколько связанных
компонент.

00:13:10.783 --> 00:13:14.506
Вот найденные связанные компоненты и есть
кластеры.

00:13:16.067 --> 00:13:20.510
Связанные компоненты графа называется
подмножество вершин, в котором любые две

00:13:20.710 --> 00:13:25.353
вершины можно соединить путём целиком
лежащим в этом подмножестве.

00:13:25.593 --> 00:13:27.194
Для поиска связанных компонентов

00:13:28.035 --> 00:13:31.952
Можно использовать стандартные алгоритмы
поиска в ширину, вот, например, как

00:13:32.072 --> 00:13:34.910
алгоритм Декстры, или поиска в глубину.

00:13:35.110 --> 00:13:38.348
То есть известные алгоритмы из теории
графов.

00:13:45.542 --> 00:13:49.779
Так, ну вот можно на этом рисунке показать
пример иллюстрации.

00:13:51.059 --> 00:13:55.379
Граф несложный, и тут показаны компоненты
связности.

00:13:56.659 --> 00:14:00.258
Видите, тут конфигурация меняется,
компоненты связности меняются.

00:14:07.321 --> 00:14:12.294
Вы можете нажать паузу и, соответственно,
каждую из конфигураций внимательно

00:14:12.454 --> 00:14:13.056
рассмотреть.

00:14:23.790 --> 00:14:25.309
Компоненты связа.

00:14:25.349 --> 00:14:29.544
Ещё раз — это такое множество вершин
графа, что для любых двух вершин из этого

00:14:29.704 --> 00:14:31.422
множества существует путь.

00:14:31.942 --> 00:14:35.658
Из одной в другую не существует пути из
вершины этого множества в вершину не из

00:14:35.818 --> 00:14:40.573
этого множества. Вот как варианты.

00:14:47.027 --> 00:14:49.387
Соответственно, вот ещё одна иллюстрация.

00:14:50.107 --> 00:14:54.186
Связанный граф — это граф между любыми
вершинами, которых существует путь.

00:14:54.746 --> 00:14:56.186
Так, ну и, соответственно, вот

00:15:05.825 --> 00:15:08.345
ещё несколько примеров из теории графов.

00:15:18.870 --> 00:15:23.275
Для подбора параметра Р обычно
рекомендуется построить гистограмму

00:15:23.515 --> 00:15:27.159
распределения попарных расстояний ro It /
J.

00:15:27.519 --> 00:15:30.122
Ну, не будем поддавать иллюстрацию,
наверно, понятно.

00:15:30.282 --> 00:15:35.927
То есть, соответственно, так графически
представить эти расстояния в наглядном

00:15:36.047 --> 00:15:36.328
виде.

00:15:36.792 --> 00:15:40.875
Большое расстояние — большой столбик;
малое расстояние, соответственно,

00:15:41.035 --> 00:15:43.037
пропорционально малый столбик.

00:15:43.318 --> 00:15:47.081
В задачах с выраженной
кластеризацией-кластерной структурой эта

00:15:47.161 --> 00:15:49.723
гистограмма имеет два чётких пика.

00:15:50.004 --> 00:15:56.089
То есть зоны наибольших внутриклассовых
расстояний и зона больших межклассовых

00:15:56.209 --> 00:15:56.770
расстояний.

00:15:57.987 --> 00:16:02.983
Параметр R задаётся как расстояние,
соответствующее точке минимума между этими

00:16:03.103 --> 00:16:07.699
пиками. Отметим два недостатка этого
алгоритма.

00:16:14.534 --> 00:16:18.730
Ограниченная применимость, то есть
алгоритм выделения связанных компонент.

00:16:19.671 --> 00:16:25.513
Наиболее подходит для выделения кластеров
типа сгущений или лент.

00:16:25.593 --> 00:16:31.196
Наличие разреженного фона или узких
перемечков K между кластерами производит

00:16:31.316 --> 00:16:33.037
неадекватной кластеризации.

00:16:33.557 --> 00:16:37.959
Плохая управляемость числом кластеров, то
есть для многих приложений удобнее

00:16:38.039 --> 00:16:38.359
задавать

00:16:39.340 --> 00:16:44.897
Не параметр R, а число кластеров или
некоторый порог чёткости кластеризации.

00:16:45.217 --> 00:16:50.254
Управлять числом кластеров с помощью
параметра R довольно затруднительно,

00:16:50.334 --> 00:16:54.692
приходится многократно решать задачу при
разных R, что

00:16:55.648 --> 00:16:58.528
Отрицательно сказывается на временных
затратах.

00:17:00.408 --> 00:17:06.047
Так, ну вот ещё некоторая иллюстрация к
алгоритму выделения связных компонентов.

00:17:06.127 --> 00:17:07.606
Как он работает?

00:17:08.606 --> 00:17:14.445
То есть исходный связный граф делится
помаленьку на подграфы.

00:17:16.820 --> 00:17:19.061
И выделяются связные компоненты.

00:17:20.581 --> 00:17:27.422
Здесь, конечно, предполагается, что длина
дуги пропорциональна расстоянию.

00:17:38.268 --> 00:17:42.591
Так, решение программное этой задачи.

00:17:42.631 --> 00:17:45.432
Ну, кстати, алгоритмов можно довольно
много найти.

00:17:46.232 --> 00:17:50.835
Следующее — алгоритм кратчайшего
внезапного пути — КНП.

00:17:51.315 --> 00:17:57.678
Соответственно, предполагаю, что нужно
найти пару точек с наименьшим и соединить

00:17:57.758 --> 00:17:58.478
их ребром.

00:17:58.975 --> 00:18:02.816
Второе, пока выборки остаются
изолированные точки, найти изолированную

00:18:02.896 --> 00:18:04.937
точку, ближайшую к некоторой
неизолированной.

00:18:05.017 --> 00:18:09.978
Соединить эти две точки ребром, удалить К
минус один из самых дальних рёбёр.

00:18:11.498 --> 00:18:17.259
Алгоритм кратчайшего незамкнутого пути
строит граф, соответственно, из L -1 рёбер

00:18:17.499 --> 00:18:17.699
так.

00:18:18.011 --> 00:18:22.734
Чтобы они соединяли все Л точек и области
минимальной суммарной длиной.

00:18:22.854 --> 00:18:27.738
Такой граф называется кратчайшим
незамкнутым путём КМП минимальным,

00:18:27.778 --> 00:18:30.419
покрывающим деревом или каркасом.

00:18:30.499 --> 00:18:35.262
Доказано, что этот граф строится с помощью
несложной процедуры, соответствующей

00:18:35.343 --> 00:18:35.823
шагам.

00:18:36.449 --> 00:18:39.369
Один-четыре вот рассмотренного ниже
алгоритма.

00:18:39.650 --> 00:18:45.850
На шаге пять удаляются, соответственно, К
самых длинных рёбер, и связный граф

00:18:46.290 --> 00:18:48.171
распадается на K кластеров.

00:18:48.251 --> 00:18:51.131
В отличие от предыдущего алгоритма, число
кластеров K

00:18:51.968 --> 00:18:56.734
Задаётся как входной параметр, его можно
также определить графически, если

00:18:56.934 --> 00:19:02.220
упорядочить все расстояния, образующие
каркас, в порядке убывания и отложить их

00:19:02.300 --> 00:19:05.704
на графике. Резкий скачок вниз где-то по

00:19:07.651 --> 00:19:12.290
На начальном левом участке графа покажет
количество наиболее чётко выделяемых

00:19:12.410 --> 00:19:18.329
кластеров. Соответственно, вот сам
алгоритм кратчайшего расстояния

00:19:19.169 --> 00:19:20.848
показан на данном слайде.

00:19:21.448 --> 00:19:26.047
Найти пару точек G с наименьшим RO и Жт и
соединить их ребром.

00:19:27.108 --> 00:19:31.751
Пока выборки остаются изолированные точки.

00:19:31.871 --> 00:19:36.194
Найти изолированную точку, ближайшую к
некоторой неизолированной, соединить эти

00:19:36.354 --> 00:19:41.558
точки ребром, соответственно, удалить К
минус один самых длинных рёбер.

00:19:41.998 --> 00:19:45.800
Этот алгоритм, как и предыдущий, очень
прост и также имеет ограниченную

00:19:45.880 --> 00:19:46.601
применимость.

00:19:47.375 --> 00:19:53.580
Наличие разряженного фона или перемычек
приводит к неадекватной кластеризации.

00:19:53.700 --> 00:19:58.384
Другим недостатком КНП, соответственно,
кратчайшего незамкнутого пути, является

00:19:58.785 --> 00:20:02.908
высокая трудоёмкость для построения
кратчайшего незамкнутого пути.

00:20:03.501 --> 00:20:07.937
Требуется о от в кубе операций

00:20:11.974 --> 00:20:14.212
Далее. Алгоритм Forel.

00:20:14.332 --> 00:20:21.206
Формальный элемент предложен Загоруйко
Елкиной в 1967 году при решении

00:20:21.326 --> 00:20:22.885
одной прикладной задачи в области

00:20:23.953 --> 00:20:29.549
Политологии. Алгоритм имеет многочисленные
вариации, и в основе этих вариаций лежит

00:20:29.589 --> 00:20:31.667
как раз следующая базовая процедура.

00:20:31.907 --> 00:20:34.384
Алгоритм Forell, алгоритм 72.

00:20:34.784 --> 00:20:41.418
Первое. Инициализировать

00:20:41.618 --> 00:20:44.016
множество неклассов.

00:20:45.243 --> 00:20:46.750
некласеризованных точек

00:20:49.907 --> 00:20:54.067
Значит, инициализировать множество
некластеризованных точек, то есть U равно

00:20:54.387 --> 00:21:01.306
XL. Пока выборки есть некластеризованные
точки, соответственно, U

00:21:01.426 --> 00:21:07.426
не равно нулю. Взять произвольную точку
X-нулевое, принадлежащую u случайным

00:21:07.586 --> 00:21:10.265
образом. Цикл повторять.

00:21:10.785 --> 00:21:11.465
Как видите.

00:21:13.060 --> 00:21:18.820
Образововать кластер сферу с центром X-0
радиусом R, соответственно, К нулевое

00:21:19.140 --> 00:21:24.021
равня X и T принадлежащим u с расстоянием
менее R.

00:21:24.661 --> 00:21:27.982
Дальше, поменять центр сферы и центр
массы.

00:21:28.022 --> 00:21:34.502
...кластера, соответственно, пересчитываем
центральную точку X0 равно

00:21:35.903 --> 00:21:40.663
в соответствии с указанной формулой,
единица делить на норма, К нулевое,

00:21:41.263 --> 00:21:42.663
суммируя все X

00:21:44.346 --> 00:21:45.948
Принадлежащим Kneвое.

00:21:46.228 --> 00:21:48.870
Пока центр X нулевое не стабилизируется.

00:21:49.191 --> 00:21:53.235
Изменить все точки K-нулевое как
кластеризованные.

00:21:53.435 --> 00:21:56.638
Соответственно, вычислить из- разность.

00:21:56.758 --> 00:22:01.563
То есть U обновлённое равно 'u разность K-
нулевое.

00:22:02.031 --> 00:22:03.272
К нулевое большое.

00:22:03.593 --> 00:22:08.638
И, соответственно, применять алгоритм KNP
к множеству центров всех найденных

00:22:08.758 --> 00:22:15.365
кластеров каждый объект, соответственно К
иТ, принадлежащий X большое

00:22:18.653 --> 00:22:22.375
Приписать к лазеру с большим центром, с
ближайшим центром.

00:22:22.896 --> 00:22:28.780
Соответственно, X нулевое у нас находится
как аргумент по всем

00:22:29.861 --> 00:22:36.625
X', принадлежащим K- нулевое функционала
сумма, как видите,

00:22:36.705 --> 00:22:38.587
расстояния по X-Xry.

00:22:48.015 --> 00:22:52.016
То есть, то есть задана некоторая точка: X
нулевое, принадлежащая X'.

00:22:52.096 --> 00:22:53.776
Большое, и параметр R.

00:22:54.656 --> 00:22:59.937
Выделяются все точки выборки,
соответственно, X & & & принадлежащими XL,

00:23:00.537 --> 00:23:05.257
попадающими внутрь сферы: RO: X & X
нулевое меньше или равно R, и точка

00:23:05.337 --> 00:23:06.177
X-нуллевое.

00:23:12.298 --> 00:23:15.458
Переносится в центр тяжести выделенных
точек.

00:23:15.538 --> 00:23:19.618
Эта процедура повторяется до тех пор, пока
состав выделенных точек, а значит, и

00:23:19.738 --> 00:23:22.417
положение центра не перестаёт меняться.

00:23:22.537 --> 00:23:25.577
Доказано, что эта процедура сходится за
конечное число шагов.

00:23:25.657 --> 00:23:29.897
При этом сфера перемещается в место
локального сгущения точек.

00:23:29.976 --> 00:23:33.296
Центр сферы как раз вот искомого X-
нулевой в общем случае не является

00:23:33.736 --> 00:23:34.656
объектом выборки.

00:23:35.750 --> 00:23:38.428
Поэтому и называется формальным элементом.

00:23:38.628 --> 00:23:42.705
Для вычисления центра необходимо, чтобы
множество объектов X было не только

00:23:42.985 --> 00:23:45.823
метрическим, но и линейным векторным
пространством.

00:23:46.143 --> 00:23:49.420
Это требование естественным образом
выполняется, когда объекты описываются

00:23:49.540 --> 00:23:54.536
числовыми признаками. Однако существуют
задачи, в которых изначально задана только

00:23:54.776 --> 00:23:57.374
метрика сложение и умножения на число.

00:23:57.930 --> 00:24:00.733
не определены, соответственно, на X.

00:24:00.773 --> 00:24:06.377
Тогда в качестве центра сферы можно взять
тот объект обучающий выборки, для которого

00:24:06.577 --> 00:24:10.100
среднее расстояние до других объектов
кластера минимально.

00:24:12.390 --> 00:24:18.152
Соответственно, шаг шесть заменяется на
вот этот вот X нулевое равняется как

00:24:18.352 --> 00:24:24.874
аргумент результаты минимизации
функционально указанного на данном слайде.

00:24:25.354 --> 00:24:31.676
То есть поиск расстояния, минимального
расстояния всех X

00:24:33.117 --> 00:24:35.277
принадлежащим K- нулевое.

00:24:36.650 --> 00:24:39.609
При этом заметно увеличивается
трудоёмкость алгоритма.

00:24:39.768 --> 00:24:44.525
Если в данном пространстве для вычисления
центра потребуется o от X операций, то в

00:24:44.645 --> 00:24:48.363
метрическом, соответственно, o от
X-квадрат, где, соответственно, вот это X

00:24:49.043 --> 00:24:50.522
число точек в кластере.

00:24:50.602 --> 00:24:55.079
Алгоритм можно несколько ускорить, если
заметить, что пересчёт центра

00:24:56.896 --> 00:25:02.655
При добавлении или удалении отдельной
точки кластера требует лишь otk операции в

00:25:02.695 --> 00:25:07.175
линейном пространстве, то есть o-1, в
линейном пространстве, o-от-единицы.

00:25:07.615 --> 00:25:12.214
Различные варианты алгоритмов формел
отличаются способами объединения сфер

00:25:12.374 --> 00:25:13.054
класт в классе

00:25:13.134 --> 00:25:18.733
Кластеры способами варьирования параметр,
способами выбора начального приближения

00:25:18.893 --> 00:25:23.453
для точки X. Вот в алгоритме X7.2
представлен один из вариантов, в котором

00:25:23.573 --> 00:25:25.693
сферы строятся последовательно.

00:25:26.013 --> 00:25:29.132
На шаге девять центром этих сфер
принимается

00:25:30.616 --> 00:25:35.125
Алгоритм КНП. С одной стороны, это решает
проблему низкой эффективности КНП, так как

00:25:36.687 --> 00:25:39.047
Сфер гораздо меньше, чем исходных
объектов.

00:25:39.127 --> 00:25:43.607
С другой стороны, мы получаем более тонкую
двухуровневую структуру кластеров.

00:25:43.727 --> 00:25:48.607
Каждый кластер верхнего уровня разделяется
на более мелкие подкластеры нижнего

00:25:48.687 --> 00:25:52.887
уровня. Другое преимущество этого
алгоритма — возможности описывать кластеры

00:25:53.047 --> 00:25:55.088
произвольной геометрической формы.

00:25:55.368 --> 00:26:01.168
Варьируя параметр R, можно получать
кластер различной степени детальности.

00:26:01.328 --> 00:26:06.568
Если кластеры, близкие по форме, к шарам,
можно сделать R достаточно большими, для

00:26:06.728 --> 00:26:10.208
описания кластеров более сложной формой
следует уменьшить R.

00:26:10.688 --> 00:26:13.408
Алгоритм R довольно чувствителен к выбору

00:26:15.472 --> 00:26:19.156
Начального положения точки X-нулевое для
каждого нового кластера.

00:26:19.316 --> 00:26:22.599
Для устранения этого недостатка
предлагается сгенерировать несколько

00:26:23.600 --> 00:26:26.603
порядков, где-то от нуля до двадцати
кластеризации.

00:26:26.643 --> 00:26:31.647
Поскольку начальное положение центров
выбирается случайным образом.

00:26:32.200 --> 00:26:34.959
Эти кластеризации будут довольно сильно
отличаться.

00:26:35.119 --> 00:26:41.677
Окончательно выбирается та кластеризация,
которая доставляет лучшее значение

00:26:41.877 --> 00:26:43.797
заданному функционалу качества.

00:26:44.597 --> 00:26:47.436
Различные виды функционалов качества
рассмотрим далее.

00:26:49.406 --> 00:26:52.262
Так, соответственно, функционал, качество
кластеризации.

00:27:09.190 --> 00:27:12.667
Задачу кластеризации можно ставить как
задачу дискретной оптимизации.

00:27:12.747 --> 00:27:17.384
То есть необходимо приписать номера
кластеров игреки объектам и чтобы значение

00:27:17.544 --> 00:27:20.662
выбранного функционала качества приняло
наилучшее значение.

00:27:21.021 --> 00:27:24.539
Существует много разновидностей
функционалов качества кластеризации, но

00:27:24.659 --> 00:27:26.497
нет самого правильного функционала.

00:27:26.697 --> 00:27:29.935
То есть, по сути дела, каждый метод
кластеризации можно рассматривать как

00:27:30.055 --> 00:27:34.172
точный или приближённый алгоритм поиска
оптимума, некоторого функционала.

00:27:34.532 --> 00:27:36.610
Среднее внутриклассовое расстояние

00:27:36.930 --> 00:27:38.529
Должно быть как можно меньше.

00:27:38.689 --> 00:27:41.806
Соответственно, вот как приводится формула
F.

00:27:43.365 --> 00:27:49.361
Соответственно, читать не буду, но вот
видно формула изображается как,

00:27:49.561 --> 00:27:52.919
соответственно, произведение сумм
стремится к минимуму.

00:27:53.038 --> 00:27:56.636
Среднее межкластерное расстояние должно
быть как можно больше.

00:27:57.156 --> 00:28:02.032
Соответственно, тогда эта же
характеристика стремится к максимум, к

00:28:02.112 --> 00:28:04.191
максиму к максимуму F1.

00:28:04.727 --> 00:28:11.044
Если алгоритм кластеризации вычисляет
центры кластеров, соответственно, какие-то

00:28:11.204 --> 00:28:15.682
вот игрек из igrek большого, то можно
определить функционалы вычислительного

00:28:15.762 --> 00:28:19.680
более эффективные. Сумма средних
внутрикластерных расстояний должна быть

00:28:19.840 --> 00:28:20.839
как можно меньше.

00:28:22.461 --> 00:28:28.139
Соответственно, вот как приводится на
данном слайде: F нулевое греческое

00:28:30.138 --> 00:28:36.016
сумма единицы делить на норма,
соответственно, расстояние в квадрате,

00:28:36.496 --> 00:28:41.174
сумма расстояний в квадрате
минимизируется, соответственно, кластер с

00:28:41.254 --> 00:28:42.253
номером Y.

00:28:44.747 --> 00:28:49.743
В этой формуле можно было бы взять не
квадраты расстояний, а сами расстояния.

00:28:49.823 --> 00:28:55.658
Однако, если Ро — это евклидовая метрика,
то внутренняя сумма F- нулевое приобретает

00:28:55.738 --> 00:29:01.374
физический смысл момента инерции кластера
относительно его центра масс.

00:29:01.494 --> 00:29:05.571
Если рассматривать кластер как
материальное тело, состоящее из качек

00:29:05.651 --> 00:29:06.570
одинаковой массы.

00:29:07.264 --> 00:29:10.583
Сумма межклассерных расстояний должна быть
как можно больше.

00:29:11.102 --> 00:29:18.099
Соответственно, вот это F1 греческое, где,
соответственно, M — центр масс

00:29:18.259 --> 00:29:19.539
всякой-всей выборки.

00:29:19.619 --> 00:29:22.657
На практике вычисляют отношение пары
функционалов, чтобы учесть как

00:29:22.777 --> 00:29:25.096
межклассные, так и внутриклассные
расстояния.

00:29:25.176 --> 00:29:27.295
То есть вот F0 делить на F1

00:29:29.674 --> 00:29:33.590
Минимизируется. Либо F0 делить на F1
минимизируется.

00:29:33.950 --> 00:29:39.584
То есть, соответственно, греческие F-0 F1.

00:29:40.383 --> 00:29:45.098
Так, ну, отвлекаясь от вопроса, вспомню,
что существуют, в принципе, различные меры

00:29:45.258 --> 00:29:47.216
расстояния, ну вот, как приводится.

00:29:47.793 --> 00:29:54.072
Наиболее удобно, известно — это Евклидовое
расстояние, как, соответственно,

00:29:58.591 --> 00:30:00.871
расстояние между точками A и B.

00:30:01.311 --> 00:30:04.110
Кроме этого, существует ещё
Манхэттеновское расстояние.

00:30:04.230 --> 00:30:07.310
Тут уже используются, как видите, не
квадраты расстояний.

00:30:08.054 --> 00:30:11.617
Разность, а, соответственно, модули.

00:30:15.700 --> 00:30:20.424
Ну, можно найти ещё довольно большое
количество различных мер расстояния.

00:30:21.345 --> 00:30:22.746
Статистические алгоритмы.

00:30:22.826 --> 00:30:26.189
Статистические алгоритмы основаны на
предположении, что кластеры

00:30:28.595 --> 00:30:32.439
Неплохо описывается некоторым семейством
вероятностных распределений.

00:30:32.639 --> 00:30:36.643
Такая задача кластеризации сводится к
разделению смеси распределений по конечной

00:30:36.723 --> 00:30:43.009
выборке. Значит, соответственно, можно
использовать EM-алгоритм, соответственно

00:30:49.982 --> 00:30:53.261
Кластеризация с помощью ЕМ-алгоритма.

00:30:54.300 --> 00:30:59.098
Ну вот тут я слишком много описывать дам
без комментариев.

00:30:59.498 --> 00:31:03.936
Соответственно, вычислительный процесс EM
— алгоритм кластеризации.

00:31:05.389 --> 00:31:09.148
Кто интересуется более подробно, может
посмотреть соответствующие литературы.

00:31:09.227 --> 00:31:12.746
Ну, тоже, как видите, трудоёмкость
вычислений уже несколько больше того, что

00:31:12.826 --> 00:31:17.744
мы рассматривали. Так, в основу ставится
гипотеза о вероятностной природе данных.

00:31:17.824 --> 00:31:22.862
То есть считается, что объекты выборки
ExcL появляются случайно, независимо

00:31:22.982 --> 00:31:24.861
согласно вероятностному распределению.

00:31:26.251 --> 00:31:28.611
...представляющим собой смесь
распределений.

00:31:28.731 --> 00:31:33.051
Соответственно, вот какие-то тут весовые W
на P.

00:31:33.291 --> 00:31:37.330
Соответственно, где, соответственно,
нормируются веса, сумма весов равна

00:31:37.450 --> 00:31:44.330
единице. Где, соответственно, p от грек,
Preк от X — это функция плотности

00:31:44.530 --> 00:31:46.410
распределения кластера Yeк.

00:31:46.570 --> 00:31:52.090
Соответственно, W Y неизвестная априорная
вероятность появления объектов из кластера

00:31:52.210 --> 00:31:52.610
Yeк.

00:31:55.417 --> 00:32:02.328
То есть, вот какой-то веспотеза о
пространстве объекта в форме кластеров.

00:32:02.408 --> 00:32:07.881
Каждый объект, соответственно, из X
равняется RN, описывается Н-числовыми

00:32:08.001 --> 00:32:10.718
признаками F1, F2 и так далее, и

00:32:12.467 --> 00:32:17.547
N Каждый кластер, соответственно, Y
большого описывается мерной гаусовской

00:32:17.867 --> 00:32:24.546
плотностью Preк от X с центром,
соответственно, M и диагональ-матри,

00:32:24.586 --> 00:32:28.146
квадратичной матрицы и диагональ от Sigma
It квадрат.

00:32:28.226 --> 00:32:31.745
Ну и таким образом мы имеем вот такую вот
смесь.

00:32:32.453 --> 00:32:39.367
Соответственно, как показано на данном
слайде снизу, где снизу — это не

00:32:39.447 --> 00:32:43.283
что иное, как взвешенное вклидовое
расстояние с весами, соответственно.

00:32:43.763 --> 00:32:46.120
Сигма квадрат Y.

00:32:53.332 --> 00:32:57.733
Кластеризуя вид распределения по Ig от X,
чаще всего будут берут сферические

00:32:57.933 --> 00:32:59.373
гаусовские плотности.

00:32:59.853 --> 00:33:05.214
Мы будем считать, что кластеры похожи
скорее на шары, а не на эллипсоиды, оси

00:33:05.334 --> 00:33:08.535
которых направлены вдоль оси оси
координат.

00:33:08.575 --> 00:33:09.895
Преимущество эллиптических гаус

00:33:10.528 --> 00:33:14.325
Гаусианов в том, что они обходят проблему
выбора нормеровки признаков.

00:33:14.405 --> 00:33:19.202
Нормировать можно немного по-разному,
причём результат кластеризации существенно

00:33:19.362 --> 00:33:21.041
зависит от нормировки.

00:33:21.201 --> 00:33:26.278
Пока не произведена кластеризация, трудно
понять, какая нормировка лучше.

00:33:26.358 --> 00:33:28.277
При использовании эллиптических гасианов

00:33:28.910 --> 00:33:34.783
Оптимальная нормировка подбирается самим
алгоритмом кластеризации, соответственно,

00:33:34.943 --> 00:33:39.178
индивидуализу индивидуально для каждого
кластера.

00:33:39.378 --> 00:33:45.571
И вот, собственно, алгоритм, который мы
рассматриваем алгоритм ЕМ.

00:33:48.615 --> 00:33:50.493
И таким образом повторяем.

00:33:52.730 --> 00:33:54.808
Так, метод К средних.

00:33:55.567 --> 00:34:01.481
То есть прежде всего определяется Yeк как
аргумент минимума расстояния по этой жите

00:34:01.681 --> 00:34:03.998
между X и центром миум.

00:34:08.257 --> 00:34:11.260
Кластеризация с помощью алгоритма
Ксредних.

00:34:11.781 --> 00:34:17.226
То есть, видите, сформировать начальное
приближение центра всех кластеров наиболее

00:34:17.987 --> 00:34:23.472
удалённые друг от друга объекты выборки,
соответственно, повторять, отнести каждый

00:34:23.552 --> 00:34:25.153
объект к ближайшему центру.

00:34:25.273 --> 00:34:27.195
То есть, по аналогии с E-шага.

00:34:28.125 --> 00:34:32.326
Вот вычисляется Е как аргумент от минимума
расстояний до центра.

00:34:32.406 --> 00:34:38.647
Вычислить новые положения центров, то есть
аналогом шага, соответственно, iгрек-жит.

00:34:39.607 --> 00:34:45.568
Пока, соответственно, игрек и Т не
перестанут изменяться, выполняем следующий

00:34:45.608 --> 00:34:46.888
вычислительный процесс.

00:34:47.048 --> 00:34:47.448
То есть вот

00:34:48.453 --> 00:34:50.851
Кластеризация с помощью K-средних.

00:34:52.570 --> 00:34:56.926
Так, метод C-средних, представленный в
алгоритме 7—4, является упрощением

00:34:57.006 --> 00:35:01.482
EM-алгоритма. Главное отличие в том, что в
Е-М-алгоритме каждый объект X и T

00:35:01.882 --> 00:35:04.719
распределяется по всем кластерам
вероятностями.

00:35:05.079 --> 00:35:06.158
Соответственно, Sigma

00:35:08.041 --> 00:35:11.603
Ж и В равно P от р равно E.

00:35:11.643 --> 00:35:17.166
В алгоритме Ксредних, то есть K-минс,
каждый объект жёстко приписывается только

00:35:17.326 --> 00:35:21.728
к одному кластеру. Второе отличие в том,
что K-минс — форма кластеров не

00:35:21.928 --> 00:35:26.850
настраивается, однако, в отличие не столь
принципиально, можно предложить упрощённый

00:35:26.970 --> 00:35:31.853
вариант, соответственно, EM, в котором
форма кластеров также не будет

00:35:32.053 --> 00:35:36.135
настраиваться. Для этого достаточно взять
сферические гвасианы с корреляционными

00:35:36.215 --> 00:35:36.855
матрицами.

00:35:37.499 --> 00:35:41.501
Соответственно, с другой стороны, возможен
обобщённый вариант camins, в котором будут

00:35:41.581 --> 00:35:44.743
определяться параметры кластера вдоль
координатных осей.

00:35:45.423 --> 00:35:46.584
Для этого, соответственно,

00:35:51.903 --> 00:35:56.504
В алгоритме 73 достаточно убрать шаг пять
и изменить я шаг жёстким прописанием

00:35:56.624 --> 00:36:03.224
объектов кластером, соответственно, как
вот на этом фрагменте слайда показано.

00:36:03.304 --> 00:36:09.144
То есть X и T равно аргументу от минимуму
расстояние, соответственно

00:36:10.584 --> 00:36:12.264
игрек — это

00:36:12.664 --> 00:36:16.544
Как игрек равно равно игреку.

00:36:16.624 --> 00:36:21.024
Таким образом, соответственно, Ем и Каминс
довольно плавно перетекают друг в друга,

00:36:21.424 --> 00:36:28.024
позволяя строить различные промежуточные
ка-варианты этих двух алгоритмов.

00:36:28.144 --> 00:36:33.224
Затем заметим, что Ка-Минс похож только на
пояс центра кластера в алгоритме For.

00:36:34.452 --> 00:36:39.855
Отличие в том, что Farell-кластер — это
шар заданного радиуса F, тогда как камин с

00:36:39.935 --> 00:36:43.498
объект относится к кластеру по принципу
ближайшего соседа.

00:36:46.180 --> 00:36:49.142
Существует два канонических

00:36:49.955 --> 00:36:54.631
Вариант алгоритма Каминс, вариант,
соответственно, Бола Холда.

00:36:55.949 --> 00:36:57.308
Бола Холда.

00:36:57.588 --> 00:37:00.065
Прошу прощения, представлен в алгоритме
74.

00:37:00.145 --> 00:37:06.579
Вариант Маккина отличается тем, что всякий
раз, когда некоторые объекты XT переходит

00:37:06.778 --> 00:37:09.176
из одного кластера в другой, центры обоих
кластеров

00:37:09.986 --> 00:37:15.149
Пересчитываются. Для этого шаг четыре надо
перенести внутрь цикла, соответственно,

00:37:18.471 --> 00:37:20.752
по-и, выполняемого в шаге три.

00:37:20.832 --> 00:37:24.955
Маккин показал в 1967 году, что этот
вариант алгоритма

00:37:26.123 --> 00:37:29.764
приводит к локальному минимуму функционала
F0.

00:37:30.764 --> 00:37:32.084
Греческая F0.

00:37:33.004 --> 00:37:37.165
Алгоритм Каминс крайне чувствителен к
выбору начальных приближений центров.

00:37:37.245 --> 00:37:41.446
Случайная инициализация центров на шаге
один может приводить к плохим кластерным

00:37:42.390 --> 00:37:45.953
кластеризациям. Для формирования
начального приближения можно выделить

00:37:47.314 --> 00:37:49.235
наиболее удалённых точек выборки.

00:37:49.315 --> 00:37:51.796
Первые две точки выделяются по максимуму
всех

00:37:52.442 --> 00:37:53.722
...попарных расстояний.

00:37:53.802 --> 00:37:58.202
Каждая следующая точка выбирается так,
чтобы расстояние от неё до ближайшей, уже

00:37:58.923 --> 00:38:00.683
выделенной, было максимально.

00:38:00.803 --> 00:38:05.484
Другая рекомендация — выполнить
кластеризацию несколько раз из различных

00:38:05.604 --> 00:38:09.244
случайных начальных приближений и выбрать
кластеризацию с наилучшим значением

00:38:09.324 --> 00:38:10.804
заданного функционала качества.

00:38:11.084 --> 00:38:15.365
Кластеризация может оказаться неадекватной
в том случае, если число кластера будет

00:38:15.645 --> 00:38:18.045
изначально неверно угадано.

00:38:19.319 --> 00:38:20.917
Стандартизация рекомендаций.

00:38:20.997 --> 00:38:24.752
Стандартная рекомендация — провести
кластеризацию при разных значениях К и

00:38:24.872 --> 00:38:29.307
выбрать то, при котором достигается резкое
улучшение качества кластеризации по

00:38:29.387 --> 00:38:30.465
заданному функционалу.

00:38:31.513 --> 00:38:33.714
Кластеризация с частичным обучением.

00:38:33.874 --> 00:38:38.315
То есть алгоритм EM и Camins легко
приспособлен для решения задач кластер с

00:38:38.355 --> 00:38:44.276
частичным обучением. То есть семи
Supervased Leoning, когда для некоторых

00:38:44.396 --> 00:38:50.318
объектов Xn правильная классификация, то
есть обозначим через U под множество таких

00:38:50.438 --> 00:38:50.918
объектов.

00:38:55.847 --> 00:39:00.245
Пример такой задачи является рубрикация
текстовых документов, в частности, страниц

00:39:00.325 --> 00:39:04.323
в Интернете. Типичная ситуация, когда
имеется относительно небольшое множество

00:39:04.443 --> 00:39:07.002
документов, вручную классифицированных по
тематике.

00:39:07.322 --> 00:39:09.841
Требуется определить тематику большого
числа.

00:39:10.558 --> 00:39:16.435
Неклассифицированных документов сходство
документов, соответственно, ro X Xr может

00:39:16.794 --> 00:39:20.592
оцениваться по-разному в зависимости от
цели рубрикации, специфики самих

00:39:20.712 --> 00:39:25.830
документов, по частоте встречаемости
ключевых слов, по частоте посещаемости

00:39:25.949 --> 00:39:28.548
заданным множеством пользователей, по
количеству взаимных

00:39:29.544 --> 00:39:34.738
гипертекстовых ссылок или другими
способами Модификация обоих алгоритмов

00:39:34.857 --> 00:39:40.411
довольно проста. На e-шаге, шаг тре, для
всех, соответственно, X и D, принадлежащие

00:39:40.491 --> 00:39:41.889
у большое.

00:39:42.209 --> 00:39:43.807
Полагаем, что и В

00:39:45.831 --> 00:39:52.825
Определяется как игрек для игрек со
звёздочкой от X t для всех остальных,

00:39:53.144 --> 00:39:58.340
соответственно, определяется как разница X
и U.

00:39:59.630 --> 00:40:03.509
То есть разность множеств X и-у
переменных, соответственно, вычисляется

00:40:03.669 --> 00:40:08.347
как прежде. На практике частичная
классификация также небольшого количества

00:40:08.467 --> 00:40:11.466
объектов, существенно улучшает качество
кластеризации.

00:40:11.985 --> 00:40:13.785
Иерархическая классификация.

00:40:18.286 --> 00:40:22.362
Иерархические алгоритмы классификации,
называемые также алгоритмами таксономии,

00:40:22.442 --> 00:40:26.279
строят не одно разбиение выборки на
непересекающиеся классы, а систему

00:40:26.398 --> 00:40:29.396
вложенных разбиений. Вот как на картинке
показывали.

00:40:29.635 --> 00:40:32.673
Результат таксономии обычно представляется
в виде таксономического

00:40:32.792 --> 00:40:34.271
дерева-дендрограммы.

00:40:34.674 --> 00:40:37.958
Классическим примером такого рода дерева
является эррхическая классификация

00:40:38.119 --> 00:40:42.125
животных и растений. Среди алгоритмов
эрэрхической классификации различаются два

00:40:42.285 --> 00:40:43.086
основных типа.

00:40:44.775 --> 00:40:49.614
Дивизивные или нисходящие алгоритмы
разбивают выборку на всё более и более

00:40:49.894 --> 00:40:54.613
мелкие кластеры. Более распространены,
соответственно, агломеративные или

00:40:54.773 --> 00:40:58.731
восходящие алгоритмы, в которых объекты
объединяются во всё более и более крупные

00:40:58.851 --> 00:41:02.650
кластеры. Реализация этой идеи
представлена в алгоритме 7—5.

00:41:04.833 --> 00:41:08.390
Алгоритм 7:5, кластеризация Ланца
Уильямса.

00:41:09.109 --> 00:41:11.187
Ну вот, тоже даю без комментариев.

00:41:11.387 --> 00:41:16.062
Сначала инициализировать множество
классов, потом вычислительный процесс.

00:41:16.182 --> 00:41:22.455
Значит, находится аргумент с минимума от
UV.

00:41:23.999 --> 00:41:26.006
Видите, пересматривается Р.

00:41:26.809 --> 00:41:28.615
Что, допустим, тоже уже интересно.

00:41:32.053 --> 00:41:35.134
Сначала каждый объект считается отдельным
кластером.

00:41:35.254 --> 00:41:39.296
Для одноэтапных кластеров, для
одноэлементных кластеров естественным

00:41:39.376 --> 00:41:41.456
образом определяется функция расстояния.

00:41:41.576 --> 00:41:46.498
Соответственно, R от roa от X.

00:41:46.818 --> 00:41:49.059
Затем запускается процесс слияний.

00:41:49.219 --> 00:41:53.821
На каждой итерации вместо пары самых
близких кластеров W образуется новый

00:41:54.101 --> 00:41:55.301
кластер. Соответственно.

00:41:56.062 --> 00:41:59.983
Ю равняется, соответственно, разность
Ugreк.

00:42:00.063 --> 00:42:04.905
Расстояние от нового кластера дубleV до
любого другого кластера вычисляется по

00:42:04.985 --> 00:42:07.546
расстояниям, соответственно, R от UV.

00:42:07.666 --> 00:42:13.468
Соответственно, R-S, R отVS, которые к
этому моменту уже должны быть

00:42:13.828 --> 00:42:19.590
известны. Ну и таким образом,
соответственно, определяется R

00:42:21.769 --> 00:42:25.411
То объединение с ВС и так далее.

00:42:25.491 --> 00:42:30.293
Формула видна. Где, соответственно, А вот
и G, соответственно,

00:42:31.854 --> 00:42:38.138
Брек — числовые параметры — это

00:42:38.338 --> 00:42:39.618
универсальная формула.

00:42:40.325 --> 00:42:44.720
Обобщает практически все разумные способы
определить расстояние между кластерами.

00:42:44.760 --> 00:42:50.394
Она была предложена Лансом Юллиемсом в
1967 году.

00:42:50.554 --> 00:42:55.189
На практике используются следующие способы
вычисления расстояний между кластерами ВС.

00:42:55.229 --> 00:42:57.707
Для каждого из них доказано соответствие
формулы

00:42:58.459 --> 00:43:05.368
Ланса Вильямса при определении сочетаниях
форма параметров, значит, используется

00:43:06.406 --> 00:43:08.363
расстояние ближайшего соседа.

00:43:11.959 --> 00:43:17.921
Соответственно, как минимум роуд VS,
расстояние дальнего соседа, как максимум,

00:43:18.001 --> 00:43:22.042
роуд-BS. Среднее расстояние,
соответственно, вот

00:43:24.523 --> 00:43:27.684
единица делить на норму.

00:43:28.404 --> 00:43:30.885
Соответственно, расстояние между центрами.

00:43:37.447 --> 00:43:39.245
Расстояние Worda.

00:43:45.121 --> 00:43:50.797
Так, можно вернуться к этому слайду, тут
более красиво всё это дело изображается.

00:43:56.790 --> 00:44:00.310
Так, ну можно сделать паузу,
поразбираться, посмотреть, какие тут

00:44:00.430 --> 00:44:05.231
функционалы. Возможных вариантов слишком
много, и на первый взгляд все они кажутся

00:44:05.311 --> 00:44:08.631
достаточно разумными. Возникает вопрос:
какой из них предпочть?

00:44:08.951 --> 00:44:11.552
Рассмотрим несколько дополнительных
свойств, характеризующих

00:44:12.422 --> 00:44:13.863
Качество кластеризации.

00:44:13.983 --> 00:44:15.944
Прежде всего свойства монотонности.

00:44:16.425 --> 00:44:19.066
Обозначим через R с индексом T.

00:44:19.186 --> 00:44:24.790
Расстояние между ближайшими кластерами,
выбранными на Т-на шаге слияния, говорят,

00:44:24.830 --> 00:44:28.672
что функция расстояния R обладает
свойством монотонности, если при каждом

00:44:28.752 --> 00:44:31.234
слиянии расстояние между объединёнными
кластерами

00:44:32.116 --> 00:44:33.398
Только увеличивается.

00:44:34.000 --> 00:44:38.330
Соответственно, R2 меньше, чем R3, меньше,
чем RL.

00:44:42.437 --> 00:44:47.435
Свойство монотонности позволяет изобразить
процесс кластеризации в виде специального

00:44:47.475 --> 00:44:49.355
графика, называемого дендерограммой.

00:44:49.435 --> 00:44:52.834
По вертикальной оси откладываются объекты
по горизонтальные расстояние.

00:44:52.954 --> 00:44:56.593
Нетрудно доказать, что если кластеризация
обладает свойством монотонности,

00:44:57.090 --> 00:45:01.767
То дендрограмму можно построить так, что
она не имела сама пересечений.

00:45:01.887 --> 00:45:06.084
При этом любой кластер из множества C и T
представляется сплошной

00:45:06.244 --> 00:45:08.362
последовательностью точек на вертикальной
оси.

00:45:08.522 --> 00:45:12.199
Если же процесс кластеризации идёт не
монотонно, то вместо дендограммы

00:45:12.359 --> 00:45:16.516
получается запутанный клубок линий, в
котором трудно что-либо разобрать.

00:45:16.636 --> 00:45:20.114
Дендрограмма позволяет представить
кластерную структуру в виде плоского

00:45:20.354 --> 00:45:22.032
графика, независимо от того, как его

00:45:22.711 --> 00:45:24.352
Размерность исходного пространства.

00:45:24.432 --> 00:45:28.154
Существуют и другие способы двумерной
визуализации многомерных данных.

00:45:28.515 --> 00:45:35.359
Такие, как многомерное шкалирование или
карты кохонена, но они привносят

00:45:35.440 --> 00:45:40.963
картину искусственные искажения, влияние
которых довольно трудно оценить.

00:45:43.463 --> 00:45:49.346
Оказывается, что наиболее любое сочетание
коэффициента в формуле Ланса Уильямса

00:45:49.546 --> 00:45:51.988
приводит к монотонной кластеризации.

00:45:59.152 --> 00:46:03.074
Так, ну вот несколько какой-то небольшой
слайд.

00:46:03.814 --> 00:46:05.294
А карты Кокхина.

00:46:05.454 --> 00:46:11.376
Ну, конечно, это тоже желательно отдельно
рассмотреть такие графические цветовые

00:46:11.456 --> 00:46:18.017
изображения Терема Беликан в

00:46:18.057 --> 00:46:19.537
1979 году.

00:46:19.617 --> 00:46:23.978
Если выполняются следующие три условия, то
кластеризация является монотонной.

00:46:24.733 --> 00:46:29.375
Соответственно, вот на слайде они указаны,
что A больше, равно нулю.

00:46:30.135 --> 00:46:36.898
Соответственно, AV больше, равно

00:46:36.938 --> 00:46:39.219
нулю, Ау плюс AV +

00:46:40.789 --> 00:46:45.870
Бетта больше, равно единице, минимум AUB +
гамма больше, равна нулю.

00:46:45.990 --> 00:46:52.431
Из перечисленных выше расстояний только,
соответственно, Р не является

00:46:52.871 --> 00:46:54.151
монотонным.

00:46:55.431 --> 00:46:59.912
Расстояние Orda отличается от него
мультипликативной поправкой, которая

00:47:00.352 --> 00:47:01.632
делает его монотонным.

00:47:06.657 --> 00:47:08.817
Так, вот, на всякий случай эти расстояния.

00:47:09.097 --> 00:47:10.977
Далее — свойства растяжения-сжатия.

00:47:11.057 --> 00:47:14.858
Некоторые расстояния обладают свойствами
растяжения, по мере того, как кластер

00:47:15.418 --> 00:47:19.258
укрупняется, расстояние от него до других
кластеров увеличивается, как будто

00:47:19.338 --> 00:47:22.578
пространство вокруг кластера расширяется,
растягивается.

00:47:23.627 --> 00:47:27.627
На дендрограмме растягивающее расстояние
характеризуется повышенной плотностью

00:47:28.548 --> 00:47:33.188
линий слева, соответственно, в области
наименьших значений РТ.

00:47:34.011 --> 00:47:38.491
Свойство растяжения считается желательным,
так как оно способствует более чёткому

00:47:38.531 --> 00:47:42.291
отделению кластеров. С другой стороны, при
слишком сильном растяжении возможно найти

00:47:42.331 --> 00:47:46.891
кластеры там, где их изначально не было,
то есть растягивающим является расстояние

00:47:50.728 --> 00:47:53.770
Некоторые расстояния наоборот обладают
свойствами сжатия.

00:47:54.690 --> 00:47:58.572
По мере роста кластера расстояние от него
до других кластеров уменьшается, и

00:47:58.692 --> 00:48:02.054
кажется, что пространство вокруг кластера
сжимается.

00:48:02.174 --> 00:48:04.535
Естественно, кластеризация при этом может
исчезнуть.

00:48:04.695 --> 00:48:05.416
Для сжимающих

00:48:05.985 --> 00:48:11.149
Расстояние характерно уплотнению данграммы
справа в области наибольших значений РТ.

00:48:11.229 --> 00:48:16.072
Расстояние ближайшего соседа РБ является
сильно сжимающим.

00:48:17.273 --> 00:48:20.315
Опять же, можно вернуться на эти
расстояния.

00:48:24.478 --> 00:48:26.440
Расстояние ближайшего соседа.

00:48:36.965 --> 00:48:41.408
Свойства сжатия и растяжения определяются
через соотношение, соответственно, RT

00:48:41.608 --> 00:48:48.092
делить на расстояние от Mu до m, где,
соответственно, RT — это есть

00:48:49.172 --> 00:48:54.335
расстояние R от UV, расстояние между
ближайшими кластерами, объединёнными на

00:48:55.336 --> 00:48:56.577
Тэтом шаге, соответственно

00:48:56.977 --> 00:48:59.698
M и m — центры этих кластеров.

00:49:00.179 --> 00:49:06.222
Если это отношение на каждом шаге были
больше единицы, то расстояние R является

00:49:06.542 --> 00:49:10.104
растягивающим. Если оно всегда меньше
единицы, то сжимающим.

00:49:10.184 --> 00:49:14.146
Есть и такие расстояния, которые не
являются ни сжимающими, ни растягивающими.

00:49:14.467 --> 00:49:16.428
Например, RC и РЦ.

00:49:17.045 --> 00:49:19.004
РС и РЦ.

00:49:19.324 --> 00:49:22.322
Они говорят, что они сохраняют метрику
пространства.

00:49:22.482 --> 00:49:27.718
На практике часто применяют гибкое
расстояние, которое представляет собой

00:49:27.798 --> 00:49:31.436
компромисс между методами ближайшего
соседа, дальнего соседа, среднего

00:49:31.476 --> 00:49:35.633
расстояния. Оно определяется одним
параметром бетта вместо четырёх,

00:49:35.713 --> 00:49:36.313
соответственно.

00:49:37.322 --> 00:49:40.398
равно B равно единице минус Бетта пополам.

00:49:40.758 --> 00:49:43.155
Гамма равна нулю, бетта меньше единицы.

00:49:43.275 --> 00:49:47.630
Гибкое расстояние является сжимающим при,
соответственно, B больше нуля,

00:49:47.750 --> 00:49:49.548
растягивающим при B меньше нуля.

00:49:49.668 --> 00:49:53.903
И стандартная рекомендация Б -025.

00:49:55.120 --> 00:49:58.841
Следующее свойство. Свойство
редуктивности.

00:50:00.522 --> 00:50:05.764
Самой трудоёмкой операцией в алгоритме 75
являлось поиск пары ближайших кластеров на

00:50:05.844 --> 00:50:10.126
шаге три. Он требует, соответственно, O в
L в квадрате операций внутри основного

00:50:10.286 --> 00:50:11.407
цикла. Соответственно,

00:50:12.383 --> 00:50:16.420
Построение всего таксонометрического
дерева ОЭ в кубе операции — это

00:50:16.540 --> 00:50:21.057
ограничивает применимость алгоритма
выборками длины нескольких сотен объектов.

00:50:21.137 --> 00:50:25.654
Идея ускорения алгоритма заключается в
том, чтобы перебрать лишь наиболее близкие

00:50:25.734 --> 00:50:30.811
пары. Тут задаётся параметр дельта и
перебор ограничивается сокращённым

00:50:30.851 --> 00:50:32.170
множеством пар. ОВ

00:50:33.254 --> 00:50:39.472
Где расстояние между R большое ту В меньше
равно дельта.

00:50:41.070 --> 00:50:42.629
Соответственно, в заданной степени.

00:50:42.789 --> 00:50:46.907
Когда все такие пары будут исчерпаны,
например, дельта увеличится и

00:50:47.067 --> 00:50:51.665
функционируется новое сокращение множества
пар и так далее, в полном слиянии всех

00:50:51.745 --> 00:50:53.064
объектов в один кластер.

00:50:53.184 --> 00:50:56.662
Реализация проведена, соответственно, в
алгоритме 76.

00:50:56.822 --> 00:51:01.180
Доказано, что этот алгоритм приводит,
соответственно, к той же кластеризации,

00:51:01.220 --> 00:51:05.258
что алгоритм 75, если расстояние Р
обладает свойством редуктивности.

00:51:05.618 --> 00:51:08.456
Но при этом, как видите, более быстро
работает.

00:51:08.536 --> 00:51:10.015
Так, алгоритм 76.

00:51:15.512 --> 00:51:18.389
Видите, вот на этом шаге используется
дельта.

00:51:24.423 --> 00:51:27.740
Определение. 1978 год.

00:51:27.900 --> 00:51:32.895
Расстояние R называется редуктивным, если
для любого дельта больше или равна нулю,

00:51:32.975 --> 00:51:33.175
любая

00:51:34.309 --> 00:51:41.192
Любых дельта близких кластеров UVen д
окрестностей UV содержит в

00:51:41.272 --> 00:51:48.235
себе дельта-окружность кластера DV,
представляющую собой объединение U иW,

00:51:48.356 --> 00:51:49.356
соответственно.

00:51:50.036 --> 00:51:56.239
S умножить на R от U объединения с меньше
дельта, R у

00:51:56.800 --> 00:52:03.523
меньше равно дельта является подмножеством
S умножить на R ST меньше дельта или R

00:52:04.283 --> 00:52:05.804
S от меньше дельта.

00:52:07.515 --> 00:52:10.110
Теореме ДиддиМар, 1984 год.

00:52:10.229 --> 00:52:14.301
Если выполняются следующие три условия, то
расстояние Р является редуктивным.

00:52:14.900 --> 00:52:17.695
Соответственно, читать не буду, вот они
описаны.

00:52:18.479 --> 00:52:22.514
Сравнение условием теорем 72.71
показывает, что всякое редуктивное

00:52:22.634 --> 00:52:24.511
расстояние является монотонным.

00:52:24.631 --> 00:52:30.344
Следовательно, позволяет отобразить
процесс кластеризации в виде диаграммы.

00:52:30.464 --> 00:52:33.580
Из перечисленных выше расстояний только Р-

00:52:34.059 --> 00:52:38.653
не является редуктивным. В алгоритме 76
возможны различные эристические стратегии

00:52:38.773 --> 00:52:41.889
выбора параметра: Дельта на шагах 2.6.

00:52:42.009 --> 00:52:49.000
Общие соображения таковы, что если дельта
несколько велико, что настолько

00:52:49.120 --> 00:52:49.439
велико

00:52:50.856 --> 00:52:56.697
Что, соответственно, Pdelta содержит
практически все пары кластеров, то мы

00:52:56.857 --> 00:53:00.098
фактически возвращаемся к неэффективному
алгоритму 7—5.

00:53:00.218 --> 00:53:06.619
Если же дельта мало, то приходится слишком
часто формировать множество p от дельта.

00:53:06.699 --> 00:53:09.900
На практике поступают следующим образом:
если число кластеров ЦФ

00:53:10.583 --> 00:53:16.743
Соответственно, Т не превышает порог N1,
то в качестве ПОдельта берут множество

00:53:16.903 --> 00:53:20.904
всех возможных пар UV из C, соответственно
и T.

00:53:20.944 --> 00:53:24.824
В противном случае выбирается случайным
образом n2 расстояния.

00:53:25.264 --> 00:53:27.184
Соответственно, R-V и дельта

00:53:28.207 --> 00:53:30.009
Полагается равным наименьшему из них.

00:53:30.089 --> 00:53:35.936
В случае редуктивности параметры
алгоритма, соответственно, N1-2 влияют

00:53:36.016 --> 00:53:40.621
только на время выполнения алгоритма, но
не результат кластеризации.

00:53:40.701 --> 00:53:43.865
Оптимальные значения для этих, для них
выбираются.

00:53:44.721 --> 00:53:46.482
С помощью калибровочных тестов.

00:53:46.642 --> 00:53:48.522
Вообще говоря, зависит от компьютера.

00:53:48.922 --> 00:53:53.164
В качестве начального выбора можно
предложить N1 равно N2 равно 20.

00:53:53.404 --> 00:53:55.445
Ну, не слишком много, не слишком мало.

00:53:55.885 --> 00:53:57.325
Определение числа кластеров.

00:53:57.365 --> 00:54:01.287
Определение числа кластеров проще всего
производить путём отсечения

00:54:02.075 --> 00:54:03.673
Право участка дентрограммы.

00:54:03.713 --> 00:54:08.868
То есть на горизонтальной оси находится
интервал максимальной длины RT + 1 - RT.

00:54:08.948 --> 00:54:12.026
И в качестве результатирующей
кластеризации выдаётся множество кластеров

00:54:12.105 --> 00:54:17.620
ЦТ. Число кластеров равно K большое
равняется L -T + 1.

00:54:17.700 --> 00:54:20.937
При необходимости можешь задать
ограничение на минимальное и максимальное

00:54:20.977 --> 00:54:22.536
число кластеров — Knue.

00:54:23.280 --> 00:54:28.957
То есть K в каком-то интервале от K0 до K1
и выбрать Т, удовлетворяющее ограничениям.

00:54:29.477 --> 00:54:35.233
Соответственно, Т между L K1+1 и,
соответственно, L -

00:54:35.353 --> 00:54:36.912
C0+1.

00:54:41.030 --> 00:54:42.949
Расстояние ближнего соседа.

00:54:44.020 --> 00:54:49.258
Соответственно, вот дендерограмма
приведена вложения как пример

00:54:53.217 --> 00:54:58.975
расстояние дальнего соседа вот с такой
дендерограммой.

00:55:00.015 --> 00:55:02.854
Диаграмма вложения также имеет место быть.

00:55:03.333 --> 00:55:05.173
Групповое среднее расстояние.

00:55:11.212 --> 00:55:13.053
Расстояние worda.

00:55:16.897 --> 00:55:20.781
Так, ну вот такие иллюстрации к тем мерам,
которые мы рассматриваем.

00:55:21.221 --> 00:55:24.344
Достоинства и недостатки агломерной
кластеризации.

00:55:24.424 --> 00:55:28.228
Достоинства и недостатки агломеративной
кластеризации.

00:55:28.268 --> 00:55:31.791
Точный ответ на вопрос: какой алгоритм
кластеризации лучше не существует?

00:55:32.569 --> 00:55:37.446
Каждое из расстояний, перечисленных выше,
имеет свои недостатки и приходит-подходит

00:55:37.726 --> 00:55:42.482
не для всех задач. Метод ближайшего соседа
обладает цепочным эффектом, когда

00:55:42.922 --> 00:55:46.839
независимо от формы кластера, к нему
присоединяются ближайшие границы объекта.

00:55:46.879 --> 00:55:50.797
В некоторых случаях это приводит к тому,
что кластеры отращивают щупальца.

00:55:51.250 --> 00:55:55.165
В зависимости от задачи это свойство может
быть как полезным, так и мешающим.

00:55:55.245 --> 00:56:00.439
Метод ближайшего соседа хорошо подходит
для выделения кластера ленточной формы.

00:56:00.559 --> 00:56:07.111
Метод дальнего соседа, соседа цепочного,
эффекта не имеет, но на раннем этапе может

00:56:08.220 --> 00:56:10.662
Объединять довольно несхожие группы.

00:56:10.742 --> 00:56:14.986
Расстояние между центрами масс не
монотонно и не редуктивно, поэтому редко

00:56:15.066 --> 00:56:19.830
используется на практике, хотя интуитивно
кажется золотой серединой.

00:56:19.910 --> 00:56:23.234
Метод Worda оказывается наилучшим по
результатам экспериментального сравнения

00:56:23.354 --> 00:56:24.355
на представленном наборе

00:56:25.223 --> 00:56:29.698
...модельных задач. Но чаще всего других
методов строят интуитивно лучшую

00:56:29.817 --> 00:56:35.570
таксиномию. Так, ну давайте рассмотрим
использование методов

00:56:36.209 --> 00:56:37.287
кластеризации.

00:56:38.527 --> 00:56:39.886
В системе Rapidminer.

00:56:39.966 --> 00:56:44.043
Кластеризация — это англистический кластер
анализа, задача группировки множества

00:56:44.163 --> 00:56:45.882
объектов на подмножество кластеров.

00:56:45.962 --> 00:56:50.519
Таким образом, чтобы объекты из одного
кластера были похожи на друга друга, чем

00:56:50.719 --> 00:56:53.797
на объекты из других кластеров по
какому-либо критерию.

00:56:53.957 --> 00:56:57.514
Задача кластеризации относится к классу
задачи обучения без учителя.

00:56:57.990 --> 00:57:03.387
Для выполнения кластеризации необходимо
построить систему элементов, как показано,

00:57:03.466 --> 00:57:05.705
соответственно, на рисунке 19.

00:57:06.504 --> 00:57:12.100
Вот. Давайте мы построим в нашем так, ну
вот у нас здесь

00:57:13.220 --> 00:57:15.898
запущена программа Ropet Mier.

00:57:16.338 --> 00:57:18.536
Как видите, здесь вот есть элементы.

00:57:19.635 --> 00:57:25.440
Соответственно, источник данных элемент
Каминс к

00:57:25.760 --> 00:57:30.684
средний. Соответственно, тут показано
число 3, как параметр установлен.

00:57:30.885 --> 00:57:35.248
И, соответственно, плюс ещё отдельный
элемент.

00:57:36.537 --> 00:57:43.405
SVD-Redution, то есть SVD-преобразование с
использованием метода главных компонентов.

00:57:54.077 --> 00:57:57.920
В данной схеме исследования кластеризация
данных, полученные с помощью оператора

00:57:58.080 --> 00:58:02.925
RTV, производится непосредственно с
помощью оператора комвинций, и далее

00:58:03.045 --> 00:58:07.729
выполняется снижение размерности данных с
помощью оператора SVD Redution.

00:58:13.742 --> 00:58:18.702
Ну, в нашем случае, в качестве источника
данных можно посмотреть, мы используем

00:58:18.942 --> 00:58:25.062
известный файл Iris, Iris и Fisher, о
которых мы уже немножко говорили.

00:58:25.182 --> 00:58:31.822
То есть знаменитый файл набор данных для
статистических процедур,

00:58:32.022 --> 00:58:33.742
процедур машинного обучения.

00:58:34.363 --> 00:58:36.723
Вот он тут взял в качестве примера.

00:58:42.443 --> 00:58:47.123
Оператор Комиц выполняет кластеризацию
данных с помощью метода К-средник, о

00:58:47.203 --> 00:58:51.563
которых мы говорили. Имеет один входной
сигнал для получения данных.

00:58:52.362 --> 00:58:53.707
В формате Data Table.

00:58:54.550 --> 00:58:56.310
...и два выходных сигнала.

00:58:56.430 --> 00:59:02.590
Соответственно, сигнал кластер-модель
выделяет, выдаёт данные типа Centroid,

00:59:02.670 --> 00:59:07.230
кластер-модель, соответственно, определяет
модель полученных кластеров.

00:59:07.950 --> 00:59:13.510
Соответственно, сигнал кластер-сет выдаёт
данные типа Date Etable, представляющие

00:59:13.590 --> 00:59:18.230
собой входные данные с добавлением
обозначений кластера, которому...

00:59:18.909 --> 00:59:22.264
Относится объект данных после
кластеризации.

00:59:23.103 --> 00:59:25.860
Данный оператор имеет несколько
параметров.

00:59:26.059 --> 00:59:27.457
Ну, давайте посмотрим.

00:59:27.697 --> 00:59:30.893
Вот эти параметры здесь показаны.

00:59:35.130 --> 00:59:38.654
Значит, можно выделить особо K и Max
Rance.

00:59:38.734 --> 00:59:42.978
То есть, соответственно, К, понятно, это
число ближайших соседей, обозначающих

00:59:43.059 --> 00:59:47.303
количество кластеров и максимальное
количество шагов, соответственно.

00:59:47.823 --> 00:59:50.666
Для уменьшения размерности данных на
основе разложения

00:59:51.164 --> 00:59:55.927
По сингулярным числам используется
оператором SFD Reduction.

00:59:56.607 --> 01:00:01.771
Количество атрибутов в результирующих
данных указывается в параметрах.

01:00:01.851 --> 01:00:05.573
Данный оператор имеет один входной и три
выходных сигнала.

01:00:06.294 --> 01:00:11.057
Входной сигнал, соответственно, example
set Impot служит для получения данных в

01:00:11.097 --> 01:00:12.378
формате Data Table.

01:00:12.998 --> 01:00:18.760
Выходной сигнал example Set Outpoot,
выходной служит для получения

01:00:19.521 --> 01:00:20.881
изменённых данных.

01:00:21.481 --> 01:00:25.443
Выходной сигнал Original служит для
получения неизменённых данных.

01:00:25.803 --> 01:00:29.405
Выходной сигнал, соответственно,
препроцессинг, модель служит для

01:00:29.565 --> 01:00:33.366
представления модели предварительной
обработки, которая содержит информацию

01:00:34.159 --> 01:00:36.920
О параметрах этого оператора в текущем
процессе.

01:00:37.320 --> 01:00:42.082
По окончании выполнения процесса
классификации будет получен результат,

01:00:42.202 --> 01:00:44.523
приведённый на следующем рисунке.

01:00:47.044 --> 01:00:49.925
Так, ну давайте мы тоже попробуем
запустить модель.

01:01:09.080 --> 01:01:14.718
Соответственно, вот найдены главные
компоненты SVD-преобразование было

01:01:14.918 --> 01:01:21.157
выполнено Луис, вкладочка, то есть
собственные числа, они же дисперсии

01:01:21.237 --> 01:01:26.476
главных компонентов SVD-векторы.

01:01:31.213 --> 01:01:33.731
Кумулятивная диаграмма.

01:01:33.811 --> 01:01:40.444
Ну вот, как видно, что, соответственно,
практически две

01:01:43.761 --> 01:01:47.557
главные компоненты уже практически
собирают всю информацию.

01:01:52.132 --> 01:01:54.492
Так, ну мы вот тут попали в СВД.

01:01:55.132 --> 01:01:58.292
Давайте попробуем посмотреть кластер.

01:02:01.411 --> 01:02:07.691
Кластер-модель в текстовой форме
выделяются три

01:02:07.891 --> 01:02:11.610
кластера. Как видите, кластер 0, кластер
1, кластер два.

01:02:13.452 --> 01:02:19.375
Какие-то значения, соответственно, в
каждом кластере помещаются.

01:02:27.859 --> 01:02:31.101
Так, вот. Разбивка на три кластера.

01:02:32.639 --> 01:02:37.205
Такой, ну, довольно примитивный день, ну,
как пример, как иллюстрация.

01:02:39.087 --> 01:02:45.535
Значит, соответственно, вот Centroid Table
и Centroid Ploat.

01:03:07.536 --> 01:03:11.020
Так, данные. Вот они наши тут разбиты.

01:03:11.780 --> 01:03:16.665
Соответственно, помните, мы говорили
атрибуты.

01:03:17.026 --> 01:03:22.992
Можно, кстати, вернуться к модели,
посмотреть значения атрибутов.

01:03:23.632 --> 01:03:30.239
То есть A, а два, а три, а четыре, четыре
атрибута, величина, соответственно,

01:03:30.359 --> 01:03:35.084
измерений, то есть случаев КС 150
значений.

01:03:35.684 --> 01:03:38.607
Их, соответственно, разбили, как видите,
тут на три кластера.

01:03:45.290 --> 01:03:47.328
Так, ну вернёмся к результатам.

01:03:49.807 --> 01:03:54.723
Значит, вот результат это мы посмотрели

01:03:58.081 --> 01:04:00.359
кластер Plost, атрибуты.

01:04:03.500 --> 01:04:05.340
Собственно данные.

01:04:10.020 --> 01:04:15.460
Так, вот SVDAC

01:04:19.420 --> 01:04:21.700
Пока не показано, но мы сейчас это
сделаем.

01:04:24.125 --> 01:04:25.846
Так, вернёмся к описанию.

01:04:27.447 --> 01:04:30.088
Значит, входной сигнал при процессе
модель.

01:04:30.128 --> 01:04:33.530
По окончании выполнения процесса
кластеризации будет получен,

01:04:33.610 --> 01:04:36.812
соответственно, результат, приведённый на
рисунке 20.

01:04:37.372 --> 01:04:44.296
Как видите, тут нужно выбрать скат-плоид
3D, соответственно, X

01:04:47.854 --> 01:04:54.777
Выбрать D0 D1 D2 и, соответственно, колор
в зависимости

01:04:54.857 --> 01:04:58.299
от кластера. Вот интересно это
попробовать.

01:05:00.100 --> 01:05:06.863
Так, выбираем скатер 3D0.

01:05:10.011 --> 01:05:13.175
D1 кластер.

01:05:33.499 --> 01:05:36.301
Так, ну вот ярко выражены три кластера.

01:05:39.023 --> 01:05:43.827
Ага. Тут надо было ещё не просто 3D, а
3D-колор.

01:05:44.067 --> 01:05:49.912
Давайте попробуем, как рекомендуется взять
именно 3D-color?

01:06:21.592 --> 01:06:27.388
Так, в описании ещё и должна быть третья
компонента D2.

01:06:31.066 --> 01:06:35.943
Так, мы так построить не получилось,
поскольку тут у нас всего две компоненты.

01:06:36.542 --> 01:06:37.502
Укажем всё-таки

01:06:38.665 --> 01:06:42.023
Чтобы было видно на три компонента.

01:06:43.062 --> 01:06:45.261
Соответственно, пересчитаем модель.

01:06:47.219 --> 01:06:53.615
Вот у нас, в принципе, три тоже можно,
видите, тут практически первый, второй,

01:06:53.735 --> 01:06:54.374
третий уже.

01:06:55.871 --> 01:06:58.654
Всё равно достаточно существенно, хотя,
конечно, немного.

01:07:16.723 --> 01:07:23.525
Так, ну вот можно, соответственно,
построить у нас три цвета: разные

01:07:23.645 --> 01:07:29.927
цвета, то есть кластер: синий, зелёный,
красный и таким

01:07:30.047 --> 01:07:33.568
образом, соответственно, построили.

01:07:38.289 --> 01:07:40.402
Так, добавили третью компоненту.

01:07:41.896 --> 01:07:46.299
Соответственно, как видите, вот здесь вот
D0, D1, D2 появилось.

01:07:46.779 --> 01:07:52.903
Значит, для того чтобы появилось, как вот
мы поставили цифру 3, соответственно, в

01:07:53.024 --> 01:07:59.588
этот третье измерение было добавлено
непосредственно в размерность.

01:08:00.148 --> 01:08:03.150
Так, ну и, соответственно, вот видим
результат.

01:08:04.947 --> 01:08:08.384
Соответственно, ropedmier позволяет
повращать.

01:08:08.784 --> 01:08:12.940
Здесь вот кластеры при каком-то углу
поворота, видно, что они довольно хорошо

01:08:13.220 --> 01:08:18.775
разделяются. Зелёный и красный как-то не
очень, видите, у них совместно, но тем не

01:08:18.855 --> 01:08:20.414
менее кластеризация прошла.

01:08:21.704 --> 01:08:25.903
Классиво, наглядно видно вот это вот самое
разделение.

01:08:26.583 --> 01:08:28.862
То есть эту задачу мы с вами решили.

01:08:33.461 --> 01:08:37.980
Так, вот здесь тоже можем добиться точно
такого же расположения.

01:08:40.334 --> 01:08:41.735
Примерно такое.

01:08:49.460 --> 01:08:53.623
Значит, результат кластеризации наглядно
представляется графически: принадлежность

01:08:53.783 --> 01:08:58.146
элементов данных кластер визуализируется
цветом.

01:08:59.464 --> 01:09:02.618
Значит, рекомендуется вот следующее
задание выполнить.

01:09:05.145 --> 01:09:08.222
В качестве источника данных используйте
файл iris.

01:09:08.422 --> 01:09:11.380
Можно воспользоваться примером 4 из
руководства, как мы.

01:09:11.460 --> 01:09:15.856
Нажмите значок плей в панели значков в
верхней части кадра.

01:09:15.936 --> 01:09:20.013
Процесс должен начинаться, и через
некоторое время в строке просмотра

01:09:20.133 --> 01:09:24.290
сообщений в нижней части кадра появится
сообщение о том, что процесс был успешно

01:09:24.370 --> 01:09:25.049
завершён.

01:09:25.884 --> 01:09:30.125
Так, ну вот попробуйте заменить оператор
Каминс на другой оператор клавиши,

01:09:30.245 --> 01:09:35.447
попробуйте, соответственно, это сделать
после запуска изменённого процесса будет

01:09:35.727 --> 01:09:37.687
представлена новая модель.

01:09:43.048 --> 01:09:45.649
Так, ну вот, как видите, можно поменять
параметры.

01:09:54.358 --> 01:09:56.959
Тут основная вот эта вот процедура —
Comins

01:10:00.560 --> 01:10:02.441
нормализованную выбрать.

01:10:06.922 --> 01:10:08.042
Тип измерения.

01:10:13.467 --> 01:10:15.668
Посмотрим, что получится в эту сторону.

01:10:15.828 --> 01:10:18.230
Так, ну вот, как видите, тут не пошло.

01:10:22.552 --> 01:10:24.192
Проверим это.

01:10:24.312 --> 01:10:27.634
Да, тут методом тыка не всегда удобно это
сделать.

01:12:17.935 --> 01:12:23.771
— Не проливает. — Да мы здесь,

01:12:23.891 --> 01:12:28.408
здесь...

01:12:29.048 --> 01:12:30.127
— Ой, молодец!

01:12:35.467 --> 01:12:37.306
Я ему обрезала ногти.

01:12:51.819 --> 01:12:52.099
Ну, в общем

01:12:52.436 --> 01:12:57.640
Понедельник. В среду, наверное, всё-таки
после.

01:12:57.880 --> 01:13:00.362
Ну, посмотрим. Если с утра надо будет

01:13:00.562 --> 01:13:07.447
попытаться.

01:15:30.205 --> 01:15:36.162
Так, как можно попытаться изменить,
соответственно,

01:15:37.762 --> 01:15:41.920
модуль, блок вот с помощью
replace-оператор?

01:15:56.372 --> 01:15:59.133
Replays-оператор выбрать модели

01:16:05.695 --> 01:16:06.975
кластер.

01:16:07.536 --> 01:16:11.977
Ну и вот здесь предлагается, видите,
соответствующе можно какой-то вот

01:16:12.097 --> 01:16:17.459
родственный для начала взять метод тоже
Comins.

01:16:27.040 --> 01:16:28.680
Но немножко другой.

01:16:41.165 --> 01:16:42.765
Запустили уже обновлённый.

01:16:48.235 --> 01:16:50.073
Он разбил на два кластера.

01:16:50.673 --> 01:16:57.507
В принципе, там можно было указать и
другие методы, наверное, тут

01:16:57.787 --> 01:17:02.543
указать число кластеров, соответственно,
три.

01:17:08.519 --> 01:17:13.164
Вот у нас другим методом получено,
соответственно, тоже три кластера.

01:17:13.404 --> 01:17:18.290
Также можно посмотреть все результаты в
текстовой форме.

01:17:18.570 --> 01:17:23.856
Вот он, кластер один, кластер два, кластер
три.

01:17:26.182 --> 01:17:29.945
Граф Ю похожий, аналогичный.

01:17:30.905 --> 01:17:34.107
Что у нас потом по поводу снижения
размерности?

01:17:36.789 --> 01:17:43.673
В главных компонентах также может
попытаться построить вот такой плот-колор.

01:18:11.722 --> 01:18:16.206
Так вот. Как видите, картина как-то
немножко сместилась.

01:18:16.286 --> 01:18:20.931
Но тем не менее, всё равно три кластера,
те самые получились, хотя ведь уже не

01:18:21.051 --> 01:18:25.856
разделённые. То есть, там у нас, помните,
был красный с зелёным где-то близко.

01:18:26.296 --> 01:18:29.219
Здесь разбилось. А, так это у нас пока
двухмерный.

01:18:31.200 --> 01:18:33.239
Попробуем построить трёхмерный.

01:18:34.998 --> 01:18:41.993
В модели меняем, соответственно, три
измерения Demention, число

01:18:42.113 --> 01:18:42.593
измерений

01:18:51.268 --> 01:18:52.787
пересчитываем модель.

01:18:57.706 --> 01:19:01.381
Сдался

01:19:01.980 --> 01:19:06.694
Fish, может поставить D2.

01:19:07.174 --> 01:19:11.049
Так. Ну, в принципе, как видите, мало чем
изменилось.

01:19:11.622 --> 01:19:14.184
То есть, там у нас был элемент каминс.

01:19:15.064 --> 01:19:20.108
Здесь у нас элемент вернёмся к самой
программе.

01:19:24.700 --> 01:19:27.540
Так, тоже комиц уже.

01:19:27.860 --> 01:19:33.061
Ну, давайте попробуем провести
эксперимент, поменять на какой-то другой

01:19:33.221 --> 01:19:38.782
метод. Тоже вот, соответственно, берём,

01:19:39.822 --> 01:19:41.022
выделяем элемент.

01:19:43.020 --> 01:19:49.785
Реплейс-оператор модел, соответственно,

01:19:49.905 --> 01:19:56.751
кластер ну, давайте попробуем подключить
метод

01:19:56.871 --> 01:20:01.754
опорных векторов, который мы не успели
сегодня рассмотреть, рассмотрим на

01:20:01.835 --> 01:20:02.835
следующих занятиях.

01:20:05.166 --> 01:20:07.244
Соответственно, что у нас в итоге
получится?

01:20:07.324 --> 01:20:10.640
Совместимо? Оказалось вполне совместимо.

01:20:11.080 --> 01:20:17.633
Вот мы получили кластер-модель,
соответственно, кластер 0, кластер 1,

01:20:17.713 --> 01:20:19.551
кластер два.

01:20:20.230 --> 01:20:21.189
Соответственно, вот.

01:20:22.435 --> 01:20:26.353
Граф Ю похожий разбиение на три кластера.

01:20:26.393 --> 01:20:31.590
Ну, естественно, нам интересно посмотреть
результаты в формате

01:20:33.309 --> 01:20:34.588
опорных векторов.

01:20:36.547 --> 01:20:42.977
Так, вопрос: она их пересчитала или,
соответственно, просто старые данные

01:20:43.097 --> 01:20:45.813
стоят? Давайте посмотрим.

01:20:46.452 --> 01:20:48.449
Ну, вроде, по идее, должна пересчитать.

01:20:54.063 --> 01:20:58.697
Так, ну, как видите, вот метод, как ни
странно, довольно мощный метод опорных

01:20:58.817 --> 01:21:03.371
векторов. Видите, зелёный кластер куда-то
потерялся.

01:21:04.610 --> 01:21:06.927
Вот он находится где-то в разбиении.

01:21:09.557 --> 01:21:15.278
Красный синий видны хорошо, а зелёный мало
отличим от красного.

01:21:16.438 --> 01:21:18.399
Как бы сказать, в той же куче.

01:21:18.759 --> 01:21:21.760
По-моему, сколько-то ещё их внутри синего.

01:21:23.523 --> 01:21:26.883
Не очень хорошо, конечно. Может,
попытаться на двухмерный случай перейти.

01:21:26.923 --> 01:21:29.203
Вот в двухмерном случае лучше видно.

01:21:29.283 --> 01:21:31.003
Но и то видно разброс зелёного.

01:21:31.083 --> 01:21:34.643
Кстати, конечно, тут в какой-то степени
можно поэкспериментировать.

01:21:34.963 --> 01:21:41.763
Значит, вот всё-таки для этого примера
лучше было использовать метод К-средних.

01:21:44.661 --> 01:21:47.901
Как мы рассматривали. Так, ну ещё раз
вернёмся в модель.

01:21:48.461 --> 01:21:51.140
Можно поменять параметры,
поэкспериментировать.

01:21:51.220 --> 01:21:55.820
Да, вот тут получилось, что если подвести
мышку к выходу, видите, мы получаем

01:21:55.900 --> 01:21:59.939
мета-данные. Даже вот какой-то фрагмент
самих, собственно, данных.

01:22:00.579 --> 01:22:02.019
Вот у нас на выходе

01:22:02.979 --> 01:22:09.978
Блока информационного находится файл Iris,
там, где размеры листиков, чеше листиков,

01:22:10.178 --> 01:22:11.778
всего четыре параметра.

01:22:12.458 --> 01:22:17.137
Вот, соответственно, мы тут попытались
провести кластеризацию.

01:22:17.577 --> 01:22:21.177
Как раз наглядно она представляется на
графике.

01:22:23.855 --> 01:22:25.855
Так, ну давайте, наверное, всё-таки
вернёмся

01:22:32.375 --> 01:22:37.975
replay's оператора модели кластерин.

01:22:39.095 --> 01:22:41.375
Возьмём всё-таки какой-то тоже каминс.

01:22:41.455 --> 01:22:41.815
Ну, можно

01:22:45.192 --> 01:22:51.597
Какой-то X mince взять как вариант и
посмотреть, что в этом случае получится.

01:22:58.163 --> 01:22:59.525
Тоже разбили.

01:22:59.925 --> 01:23:03.048
Так, а в данном случае она выделила четыре
кластера.

01:23:03.866 --> 01:23:06.546
Так, а вопрос: какие тут получаются
параметры?

01:23:10.827 --> 01:23:15.787
От минимума до максимума 60 по умолчанию
стоит.

01:23:16.347 --> 01:23:23.068
Так, ну и вот метод результатов можно тоже
посмотреть, что в итоге у нас получилось.

01:23:24.938 --> 01:23:31.814
В итоге получилось четыре кластера,
несколько

01:23:32.294 --> 01:23:33.693
размазанных друг другом.

01:23:33.773 --> 01:23:37.730
Ну, конечно, мы тут несколько попробовали

01:23:39.445 --> 01:23:41.924
Несколько необдуманно какие-то методы
использовать.

01:23:41.964 --> 01:23:45.604
Ну, как видите, инструмент Robit Miner
позволяет наглядно представить.

01:23:45.724 --> 01:23:51.603
Ну и мы тут показали, что какие-то наборы
данных хорошо кластеризируются с помощью

01:23:51.683 --> 01:23:53.962
одного метода, какие-то наборы данных

01:23:54.746 --> 01:23:56.668
Соответственно, другим методом.

01:23:56.789 --> 01:23:59.952
Конечно, здесь можно было ещё какое-то
потратить время, чтобы пооптимизировать

01:24:00.152 --> 01:24:04.878
параметры. Вполне возможно, можно будет
при других параметрах добиться вполне

01:24:04.958 --> 01:24:07.241
приличной кластеризации с этим методом.

01:24:07.721 --> 01:24:10.284
Вот, наверное, всё-таки разбиение на три
класса было бы более

01:24:12.101 --> 01:24:15.584
Соответственно, наглядно и более чётко.

01:24:16.264 --> 01:24:19.026
Но на этом мы сегодня с вами заканчиваем.

01:24:19.146 --> 01:24:20.027
Спасибо за внимание.