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