Полусупервизорный метод K-ближайших соседей
- Автор метода
- Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
- Год
- 2002 (semi-supervised extension); 1967 (KNN base)
- Тип
- Semi-supervised classifier / label propagation
- Семейство
- Machine learning
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Полусупервизорный KNN расширяет классический алгоритм K-ближайших соседей, используя большие объемы неразмеченных данных наряду с небольшим размеченным набором.
Построив граф KNN для всех наблюдений и распространяя известные метки через ребра графа, метод выводит метки для неразмеченных точек без необходимости дорогостоящей ручной аннотации каждого образца.
Интуиция метода
Представьте себе класс, где лишь у нескольких учеников есть именные таблички, а остальные анонимны. Стандартный KNN может классифицировать анонимного ученика, только глядя на несколько ближайших соседей с табличками. Полусупервизорный KNN вместо этого отображает всю комнату как сеть — каждый ученик связан со своими ближайшими соседями — и распространяет метки от размеченных учеников, подобно тому как чернила растекаются по влажной бумаге. Поскольку сеть отражает общую структуру данных, метки достигают неразмеченных точек принципиальным образом, который учитывает базовую геометрию, а не игнорирует неразмеченное большинство.
История
Распространение меток на графах KNN было систематизировано Zhu и Ghahramani в 2002 году, основываясь на трансдуктивном SVM Вапника и более ранних идеях диффузии на основе графов. Фреймворк был консолидирован в томе MIT Press «Semi-Supervised Learning» (Chapelle et al., 2006), который остается стандартным справочником. Масштабируемые библиотеки приближенного KNN (FAISS, Annoy) позже сделали подход практичным для миллионов точек, и он продолжает использоваться в качестве сильного базового метода для полусупервизорной классификации изображений и текста.
Когда применять
Используйте полусупервизорный KNN, когда у вас есть небольшой размеченный набор и большой неразмеченный пул из одного и того же распределения, данные находятся в относительно низкоразмерном пространстве (менее 50 признаков), и вы считаете, что соседние точки принадлежат к одному классу. Он хорошо подходит для классификации фрагментов изображений, категоризации текста с редкими аннотациями и задач медицинского скрининга, где экспертная разметка является дорогостоящей. Избегайте его, когда размеченные и неразмеченные данные поступают из разных распределений (сдвиг ковариат), пространство признаков очень высокоразмерно (граф KNN становится ненадежным), набор данных достаточно мал, чтобы полностью супервизорный KNN уже был достаточен, или границы классов не совпадают с локальной структурой плотности данных.
Ограничения и замечания
- Построение графа масштабируется квадратично с размером набора данных, если не используются методы приближенного поиска ближайших соседей.
- Производительность резко падает в высокоразмерных пространствах, где метрики расстояния теряют дискриминационную способность.
- Предполагает, что размеченные и неразмеченные данные взяты из одного и того же распределения; сдвиг ковариат нарушает работу метода.
- Требует тщательной настройки k, ширины полосы пропускания весов ребер и параметра смешивания распространения.
- Распространение меток может усиливать начальные ошибки разметки на больших участках графа.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Использует дешевые неразмеченные данные для повышения точности сверх того, что возможно только с размеченным набором.
- Отсутствие предположений о параметрической модели: опирается только на геометрию локального соседства.
- Естественным образом обрабатывает многоклассовые задачи без модификаций.
- Построение графа KNN прозрачно и легко проверяется.
- Хорошо работает, когда классы образуют компактные, хорошо разделенные кластеры в пространстве признаков.
Применение
- Классификация изображений с небольшим набором размеченных изображений и большим неразмеченным корпусом.
- Категоризация текста и документов, где ручная разметка является дорогостоящей.
- Классификация медицинских записей или патологических слайдов с ограниченными экспертными аннотациями.
- Обнаружение мошенничества, когда доступно лишь небольшое количество подтвержденных случаев мошенничества.
- Разметка данных датчиков в промышленных IoT-системах с редкими событиями истинности.
Как это работает
Как это работает
Граф строится для всех наблюдений — как размеченных, так и неразмеченных. Каждый узел соответствует одной точке данных, а направленные или ненаправленные ребра соединяют каждый узел с его k ближайшими соседями в пространстве признаков. Выбор k определяет, насколько локально или глобально будут распространяться метки: малое k обеспечивает плотное распространение; большое k позволяет меткам перескакивать через большие промежутки.
Веса ребер отражают степень сходства между связанными узлами, обычно с помощью гауссова (RBF) ядра, применяемого к евклидову расстоянию между векторами признаков. Параметр ширины полосы пропускания sigma контролирует, как быстро сходство убывает с расстоянием. Более сильные ребра легче передают метки во время распространения.
Формула
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)Метки итеративно распространяются от размеченных узлов к неразмеченным соседям. На каждой итерации каждый узел обновляет свое распределение мягких меток как взвешенную комбинацию текущих распределений своих соседей и своей собственной начальной метки (если она размечена). Параметр смешивания alpha балансирует влияние структуры графа и жестких меток, и итерация продолжается до сходимости распределений.
Формула
F \leftarrow \alpha W D^{-1} F + (1-\alpha) YПосле сходимости распространения каждому неразмеченному узлу присваивается класс с наивысшим баллом мягкой метки в его сошедшемся распределении. Размеченные узлы фиксируются на своих истинных метках на протяжении всего процесса, поэтому известные метки никогда не перезаписываются.
Формула
\hat{y}_i = \arg\max_c F_{ic}Частые ошибки
- Построение графа KNN без нормализации признаков, что приводит к доминированию высокодисперсных признаков в расчетах расстояний.
- Установка слишком большого k, что сглаживает истинные границы классов и приводит к чрезмерно сглаженным распределениям меток.
- Игнорирование возможности того, что неразмеченные данные находятся вне распределения относительно размеченного набора.
- Сообщение точности на неразмеченных узлах, как если бы это была несмещенная оценка тестового набора — неразмеченные узлы просочились в граф во время обучения.
- Пропуск проверок сходимости и использование фиксированного, произвольного числа итераций распространения.
Часто задаваемые вопросы
Как мне выбрать k?
Начните с k в диапазоне 5-15 и настройте его по точности валидации на отложенном размеченном наборе. Меньшее k дает более четкие, более локальные границы; большее k позволяет меткам распространяться дальше, но рискует пересечь истинные границы классов.
Могу ли я честно оценить метод, когда большинство данных неразмечены?
Выделите специальный размеченный тестовый набор, который никогда не добавляется в граф. Узлы в графе — даже неразмеченные — являются частью обучения, поэтому любой размеченный узел, участвующий в построении графа, не должен также служить тестовой точкой.
Что делать, если мой набор данных слишком велик для построения полного графа KNN?
Используйте библиотеки приближенного поиска ближайших соседей, такие как FAISS или Annoy, для построения графа за O(n log n) вместо O(n^2), а затем примените распространение меток на разреженном приближенном графе.
Всегда ли полусупервизорный KNN превосходит супервизорный KNN?
Не обязательно. Если неразмеченные данные находятся вне распределения или пространство признаков очень высокоразмерно, граф становится зашумленным, и распространение может ухудшить производительность. Всегда сравнивайте с базовым супервизорным KNN, прежде чем заявлять о преимуществах неразмеченных данных.
Это то же самое, что распространение меток (label spreading) или распространение меток (label propagation) в scikit-learn?
Очень близко. LabelPropagation и LabelSpreading в scikit-learn реализуют фреймворк Zhu и Ghahramani, используя граф KNN или RBF-ядра, поэтому они являются прямыми реализациями описанного здесь метода.
Похожие методы
Источники
Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.
Открыть ссылку на публикациюСкопировано.Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.
ISBN: 978-0-262-03358-9Скопировано.