Написано Айрис Фу и Дивьяа Равичандран, учеными в области компьютерного зрения, 19 апреля 2018 г.

GumGum Sports ежедневно обрабатывает огромное количество медиафайлов. Они поступают из различных источников и форм, включая сообщения в социальных сетях и транслируемые/потоковые видео. Наша цель – определить средства массовой информации, которые имеют отношение к нашим клиентам, чтобы оценить ценность их спонсорства и размещения.

Задача состоит в том, чтобы обрабатывать огромные объемы сообщений за короткий период времени. Например, чтобы оценить ценность показа каждого бренда в баскетбольном матче, нам нужно будет рассмотреть все доступные данные и метаданные, чтобы определить виды спорта, игроков, команды, расположение вывесок, арены и многие другие подобные критерии. Многие из них можно описать как проблему обнаружения объектов на изображениях. Одним из возможных способов решения этой проблемы может быть использование нейронных сетей, обученных в рамках обучения с учителем.

Для обучения модели обнаружения объектов при обучении с учителем необходимы аннотированные обучающие данные. Однако для многих задач аннотированные данные не существуют. Чтобы обойти эту проблему, подходы к обучению с частичным учителем и без учителя могут идентифицировать и объединять медиафайлы, которые визуально похожи. Этот подход может создавать только группы похожих медиа; однако он не может давать имена или ярлыки этим группам. Несмотря на это, его можно использовать — а) для повышения эффективности аннотаций и б) для выявления дубликатов постов.

Кластеризация K-средних — это популярный алгоритм кластеризации, который классифицирует набор данных с заранее определенным числом (k; может быть выбрано случайным образом в начале процесса) центроидов, соответствующих каждому из k кластеров. Количество центроидов выбирается случайным образом или эмпирическим путем, и можно учесть максимальное разделение кластеров в наборе данных. Затем каждая точка данных сравнивается с каждым из центроидов и на основе метрики ближайшего расстояния будет сгруппирована с наиболее похожим центроидом. Каждая итерация по набору данных потребует пересчета центроида до тех пор, пока все точки данных не будут отсортированы в кластер и не будут зафиксированы k центроидов.

В формате уравнения алгоритм k-средних должен минимизировать следующий вывод:

где

— евклидово расстояние между точкой данных xi и центроидом кластера vj.

iпроходит по кластерам (всего C), а jпроходит по каждому элементу кластера. J(V) – это целевая функция, которую мы хотим минимизировать. Она представляет собой внутрикластерное расстояние относительно центра тяжести кластера.

Чтобы пересчитать новый центр кластера для данного кластера, усредните точки данных, связанные с этим кластером:

Этот итеративный процесс вычисления расстояний внутри каждого кластера будет продолжаться до тех пор, пока а) центроиды кластера не перестанут изменяться или б) изменение центроидов кластера не станет ниже заданного порога. Это означает, что достигнута оптимальная кластеризация и расстояние внутри кластера больше не может быть минимизировано.

Кластеризация K-средних — хороший стартовый подход, но для выбора k-кластеров требуется некоторая интуиция в отношении набора данных. Вместо этого мы обратимся к альтернативному методу кластеризации: Алгоритму распространения сродства, который не требует знаний заранее, чтобы установить необходимое количество кластеров, но его основные принципы аналогичны K-средним. Самое главное, этот алгоритм уже реализован в Scikit Learn, модуле, доступном для Python.

Алгоритм Affinity Propagation находит репрезентативные центры кластеров из набора данных. Он назначает элементы этим кластерам на основе сходства точек данных друг с другом и продолжает кластеризовать набор данных в течение заданного количества итераций. Поскольку это режим поиска кластеров, управляемый данными, для него не требуется указывать начальный номер кластера. На основе порога изменения, известного как коэффициент демпфирования, две точки в n-мерном пространстве определяются как похожие друг на друга, если расстояние между ними находится в пределах порога. Используемая метрика расстояния теоретически может быть любой, подходящей для конкретного приложения; Евклидово расстояние, однако, является самой простой и наиболее популярной используемой метрикой.

Сценарий использования

Цель:

Сгруппируйте набор изображений спортивной тематики (полученных из сообщений в социальных сетях) с помощью Affinity Propagation.

Данные:

У нас есть около 100 изображений для NBA, NHL и MLB. Многие из них представляют собой не изображения самого вида спорта, а графические плакаты, посвященные игре, селфи людей на стадионах или даже пресс-конференции, связанные со спортом (рис. 1).

Хотя использование нейронной сети для классификации этих изображений было бы простым, на практике из-за разнообразного характера изображений классификатор нейронной сети неэффективен. Вместо этого мы пытаемся использовать кластерный подход, чтобы сгруппировать схожие виды изображений и упростить задачу аннотации, исходя из предположения, что все изображения в кластере должны иметь одинаковые аннотации.

Подход:

Векторы признаков для каждого изображения получаются из классификатора сцены. Классификатор сцен представляет собой нейронную сеть, использующую архитектуру GoogleNet, обученную на наборе данных Places365. Это было сделано для того, чтобы иметь представление для каждого изображения в домене, позволяющее группировать их. Предполагается, что каждый вид спорта имеет разную контекстуальную информацию, которая отличает их.

Предпоследний (до softmax) слой этой сети классификации сцен представляет собой 365-мерный вектор, а матрица n x 365 с образцами изображений n формирует набор данных для кластеризации.

Для кластеризации мы используем Алгоритм распространения сходства, включенный в модуль Python scikit-learn. Реализация кластеризации проста, и в итоге у нас осталось 25 кластеров. Некоторые репрезентативные кластеры показаны на рисунке 2.

Как и ожидалось, похожие изображения группируются вместе. Например, на рис. 2 синий кластер представляет собой группу пресс-конференций, зеленый кластер объединяет графические плакаты с изображением баскетбола на преимущественно черном фоне и так далее.

Важно иметь в виду, что есть некоторые кластеры, в которых будет меньше оптимальных выборок для формирования кластера обычного размера; некоторые кластеры с 2–3 изображениями, которые мы можем иначе классифицировать как выбросы в пространстве признаков. Что делает это полезным в конвейере аннотаций, так это то, что более связные кластеры могут быть помечены/аннотированы быстро и безболезненно, в то время как впоследствии можно будет посвятить больше времени аннотированию более смешанных кластеров.

Тот же подход можно применить для решения другой серьезной проблемы: при наплыве тысяч постов в социальных сетях высока вероятность дублирования постов. Фильтрация точных дубликатов постов — более простая задача, но как быть с постами, которые были слегка изменены?

Рассмотрите такие сообщения, как ретвит минутного клипа, который был разделен на несколько секунд, демонстрирующих ключевую игру, или клипы, которые были отредактированы, чтобы добавить другое вступление. Если бы можно было быстро идентифицировать эти типы постов, то можно было бы избежать избыточной обработки. Конечно, можно развернуть больше экземпляров в облаке или запросить более крупные и мощные машины, но здесь упор делается на алгоритмическую эффективность при минимальных затратах ресурсов.

Подход кластеризации, приведенный в качестве примера выше, также будет группировать похожие/точно такие же носители в один и тот же кластер, и может быть выполнено простое исследование кластеров и удалены дубликаты, чтобы избежать ненужных накладных расходов на обработку. Это также можно использовать для удаления небольших видео, которые являются частью больших видео, которые уже есть в наборе данных.

Например, это видео является частью этого большого видео.

Обработка обоих этих видео приведет к дублированию обработки перекрывающихся кадров, а при масштабировании до потребления миллионов медиафайлов в день накладные расходы на вычисления и затраты будут значительными. Этого можно просто избежать путем кластеризации и удаления дубликатов/почти дубликатов.

Мы всегда ищем новые таланты! Просмотр вакансий.

Следите за нами: Facebook | Твиттер | | Линкедин | Инстаграм