[ЗАСТАВКА] Итак, узнав про задачу кластеризации, мы бросились обсуждать разные интересные методы кластеризации. В то же время, возможно, можно придумать что-нибудь очень простое. Сейчас мы поговорим именно об этом. Итак, мы вспомним, что такое связные компоненты в графе и придумаем, как можно решать задачу кластеризации с помощью выделения связных компонент. После этого мы поговорим про минимальное остовное дерево, вспомним алгоритм Крускала и разберемся с кластеризацией с помощью минимального остовного дерева. Итак, начнем. Связные компоненты — это подграфы в графе, которые обладают свойством связности, и в то же время никакие вершины из графа нельзя добавить в этот подграф, сохранив свойства связности. Что такое связность? Связность — это свойство, заключающееся в том, что из любой вершины графа можно попасть в любую другую вершину графа по ребрам. Таким образом, часто встречается ситуация, когда граф состоит из нескольких связных компонент, и может быть полезно выделить эти связные компоненты. Это поможет нам и для кластеризации. Давайте просто соединим ребром те объекты, расстояние между которыми меньше какой-то зафиксированной константы R, и дальше в полученном графе выделим компоненты связности. Если граф сразу получился связным, то есть компонента связности одна, то тогда можно взять R поменьше. Однако непонятно, как же нам выбрать R, если нам нужно какое-то конкретное число кластеров, ну, например, K кластеров. Здесь больше подойдет другой простой графовый подход. Минимальным остовным деревом в графе называется такой связный граф без циклов, ну то есть такое дерево, что все вершины этого графа являются вершинами исходного графа, все ребра тоже являются ребрами исходного графа, но при этом все вершины исходного графа задействованы. Вот если мы хотим построить минимальное остовное дерево, нам будет очень полезен алгоритм Крускала, или Краскала, в зависимости от того, как вам больше нравится. Изначально множество уже найденных ребер будет пустым. Затем на первом шаге мы добавим ребро с минимальным весом. Мы рассматриваем случай взвешенного графа, потому что наша задача — получить именно минимальное остовное дерево, то есть дерево, для которого суммарный вес ребер будет минимальным, и в то же время это будет остовное дерево. На каждом шаге мы добавляем ребро, одна из вершин которого уже принадлежит множеству выбранных вершин, а другая еще не принадлежит. И при этом среди всех таких ребер вес у добавляемого ребра должен быть самым маленьким. В тот момент, когда у нас задействованы все вершины графа, мы получаем остовное дерево, и оказывается, можно доказать, что это будет минимальное остовное дерево. Легко придумать, как решить задачу кластеризации с помощью остовного дерева. Давайте построим взвешенный граф, в котором веса ребер — это расстояния между объектами. Построим минимальное остовное дерево для этого графа и просто удалим K − 1 ребро с максимальными весами, ну то есть с максимальным расстоянием. В итоге мы получим K компонент связности, и именно их и будем интерпретировать как кластеры. Итак, мы с вами вспомнили, что такое связные компоненты, и придумали, как решать задачу кластеризации с их помощью. Также мы поговорили про минимальное остовное дерево, алгоритм Крускала и кластеризацию с помощью минимального остовного дерева.