Прикладная кластеризация. Выделение объективных ниш мобильных приложений Apple App Store.

 

Введение

Когда очень много приложений – это проблема.

Растущий из года в год рынок мобильных приложений к 2020 году достигнет объема $189 млрд. Только в Apple App Store количество мобильных приложений превысило 3 миллиона, из которых 783 000 приходится на игры, а остальное - на неигровые приложения. И если все игры распределены по 19 игровым категориям (в среднем 41 000 игр на каждую категорию), то 2,3 млн неигровых приложений заключены в рамки всего 24 категорий (почти 96 000 приложений в среднем на категорию).

Проблема пользователя. Приложений очень много, а категорий мало.

С одной стороны, разработчики часто вынуждены размещать свои приложения в категориях, лишь очень приблизительно описывающих их функционал, а с другой - пользователи вынуждены примерять свои потребности к ограниченному количеству статичных категорий, которые существуют в магазинах приложений в практически неизменном виде с момента их открытия. Не найти, не заметить или пропустить нужное приложение в такой ситуации очень просто. И поиск App Store здесь не большой помощник, по нескольким причинам. Поиск App Store ищет только по названию приложений и ключевым словам (не более 100 знаков), о которых должен был подумать разработчик при публикации своего приложения. Если задуматься над тем, как человек знакомится с любым новым понятием или явлением, станет понятно, что шансов на успех у нового интересного приложения, не имеющего аналогов и открывающего новую нишу, очень мало. Ведь у человека потребность возникает только в отношении знакомых ему понятий или явлений. Человек, не знающий о существовании самолёта и возможности воздушного сообщения, никогда не задумается о необходимости куда-то полететь.

Проблема разработчика. Разработчики вынуждены тратить огромные ресурсы на то, чтобы рассказать о новом продукте.

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

Проблема инвестора. Системно находить свежие интересные проекты среди 3 млн приложений невозможно.

 

Постановка задачи

Распределение приложений по объективным группам, отражающим реальную суть и особенности приложений. Исходный материал - тексты описаний приложений, так как именно в описаниях разработчики стараются максимально полно раскрыть идею и преимущества продукта. На входе мы имеем около 20 тысяч описаний iOS приложений, достаточно равномерно распределенных по 20 категориям Apple App Store USA.  Нужно выявить объективные категории приложений и их оптимальное количество.

Первым шагом задач по анализу текста является его предобработка. Из текста должны быть удалены так называемые стоп-слова, малозначащие символы и большинство знаков препинания. Причем стоп-слова могут быть как общими, не зависящими от тематики текстового корпуса (предлоги, причастия, междометия, цифры, частицы), так и специфичными (app, http, www, email ...). Все остальные слова с помощью алгоритмов лемматизации или стемминга должны быть приведены в начальную форму.

 

Методы решения

Для решения задачи нам нужно понять, какие приложения, уже размещенные в сторах, наиболее близки между собой. То есть, наша задача -  это задача кластеризации и мы должны придумать, как сделать кластеризацию для текстов описаний приложений.

Алгоритмы кластеризации, такие как k-means, ничего не знают про тексты и хотят получить на вход массив численных векторов. Значит мы должны из текста сделать вектор. Рассмотрим, какие методы позволяют нам это сделать.


TF-IDF

TF-IDF - это статистический показатель, который используется для оценивания важности конкретного слова в контексте описания каждого приложения.

TF или частота слова - это отношение количества вхождения конкретного слова к суммарному набору слов в исследуемом тексте. Этот показатель отражает важность слова внутри одного описания.

IDF или обратная частота документа - это инверсия частотности, с которой определенное слово фигурирует в текстовом корпусе. Благодаря этому показателю можно снизить весомость наиболее широко используемых слов (предлогов, союзов, общих терминов и понятий).

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

Результат работы алгоритма - вектор размерностью N, где N - количество уникальных слов в текстовом корпусе. Размерность вектора для типичных текстов составляет порядка 50000-100000 слов. Для дальнейшего анализа требуется снижение размерности.

Word2Vec, Glove, FastText

Алгоритмы представления слов текстового корпуса в векторном пространстве. Размерность пространства не превышает нескольких сотен.

Суть метода упрощенно описывается следующим образом: алгоритм пытается предсказать текущее слово по окружающим его словам. В результате работы алгоритма получаемые векторы взаимосвязанных слов оказываются в пространстве достаточно близко. Например, у слова king наиболее близкие слова это queen, princess.

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

Другой недостаток метода - это зависимость качества модели от того, какой текстовый корпус использовался для обучения. Для русского языка, чтобы качественно обучить модель, особенно в какой-то определенной области, нужно собрать достаточно большой тематический текстовый корпус, как правило больше 10 миллионов слов.

Разреженный автоэнкодер

Автоэнкодер - это алгоритм обучения без учителя, который использует нейронную сеть для того, чтобы входной вектор признаков X вызывал отклик сети Y, равный входному вектору, т.е. Y = X. 

Пример автоэнкодера:

Причем на архитектуру сети накладываются специальные условия:

• Количество нейронов скрытого слоя L2, должно быть меньше, чем размерность входных данных (как на рисунке);

• Активация нейронов скрытого слоя должна быть разреженной (количество неактивных нейронов в скрытом слое должно значительно превышать количество активных). Как правило доля активных нейронов не превышает 5%.

Достоинство метода заключается в том, что  полученный вектор (обычно это выход скрытого слоя L2) довольно точно передает смысл текста, признаки которого были поданы на вход. Недостаток метода: для обучения также нужен большой, качественный текстовый корпус.

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

Итак. Мы получили вектор из текста описания. Что дальше?

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


PCA

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


Truncated SVD

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


Self-organizing map

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

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

Достоинства карт Кохонена - устойчивость к зашумленным данным и быстрое обучение. Недостатком является то, что окончательный результат работы нейронных сетей зависит от начальных установок сети.


t-SNE

Это очень популярный алгоритм, который также позволяет снижать размерность данных. Этот алгоритм может свернуть сотни измерений к всего двум, сохраняя при этом важные отношения между данными: чем ближе объекты располагаются в исходном пространстве, тем меньше расстояние между этими объектами в пространстве сокращенной размерности. t-SNE неплохо работает на маленьких и средних реальных наборах данных и не требует большого количества настроек гиперпараметров.

Для нашей задачи снижения размерности наилучшие результаты показал алгоритм t-SNE 2D.

Результат работы алгоритма t-SNE показан на следующей картинке

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

 

Выбор количества кластеров

Существует несколько приближенных методов для поиска этого значения. Один из них - пожалуй, самый понятный и наглядный - это так называемый метод “elbow” или метод локтя. Суть данного метода заключается в построении графика зависимости дисперсии качества разбиения от количества кластеров k.

В самом начале добавление новых кластеров очень сильно помогает модели, но начиная с определенного момента, увеличение количества кластеров перестает существенно улучшать качество разбиения. Тогда, условно, это количество можно назвать оптимальным. Условно потому, что качество полученной модели нужно проверить визуально. Например, в нашем случае, судя по картинке выше, оптимальное k равно 40-50, но при проверке полученных кластеров многие приложения с явно разным смыслом все же попали в одни и те-же кластеры. Поэтому было принято решение увеличить k до 100.

Итак, проводим кластеризацию алгоритмом K-means при k = 100 и смотрим на описание приложений с учетом разбиения на кластеры.

На картинке мы видим раскрашенные и пронумерованные кластерные группы. Что можно заметить сразу? Некоторые кластеры расположены обособленно, рядом с ними нет «соседей». Но есть кластеры, которые имеют ярко выраженную границу. Например, в выделенной части изображения мы можем видеть кластеры 0 и 60, которые делят пополам большую группу приложений. Делаем предположение, что здесь в результате кластеризации образовалось две объективных категории.

Посмотрим, какие приложения попали в эти два кластера и попробуем понять, достигли мы своей цели или нет. Для начала построим гистограммы маркет-категорий приложений, которые находятся в кластерах 0 и 60.

Теперь посмотрим на несколько приложений и топ 50 слов описаний приложений в каждом из кластеров.

кластер 0

Babbel – Learn Italian
Innovative 101 Learn Languages
Learn Danish: Language Course
Page: English Grammar Checker
Oxford Spanish Dictionary

 

word phrase learn language speak english vocabulary dictionary spanish lessons native grammar audio babbel sentence speech pronunciation travel sign search help chinese course practice voice nemo translate study rhyme write italian term phrasebook hear time french speakers asl feature odyssey korean categories like record review spell read period text japanese

кластер 60

Live Translator HQ
Offline Translator Pro 8 lang
Translator with Speech Pro
Spanish Dictionary +
Arabic Dictionary Elite

word english translate dictionary languages text language translation phrase spanish translator voice french chinese speech translations pronunciation japanese portuguese italian german speak russian arabic offline sentence search learn korean dutch support danish polish turkish dictionaries swedish norwegian finnish czech greek definitions hebrew romanian hindi vocabulary internet thai hungarian connection catalan

Если по топ 50 словам определить характер приложения довольно трудно, то по названиям достаточно просто понять, что кластер 0 состоит из приложений, преимущественно предназначенных для изучения языков, а кластер 60 состоит главным образом из переводчиков.

Таким образом, если взять из гистограммы кластера топ 3 маркет-категории и соединить их, то мы получим название объективной псевдо-категории, соответствующей данному кластеру. Выглядеть это будет, например, вот так:

• кластер 0   - education_travel_reference
• кластер 60 - reference_travel_books

Первой будет идти основная маркет-категория, следом за ней - уточняющие категории, придающие основной категории дополнительную смысловую окраску.

Для того чтобы оценить качество разбиения и посмотреть, как в кластерах распределены маркет-категории, существует еще один способ визуализации - тепловая карта (heatmap). Она показывает, как и в каком количестве маркет-категории распределены в кластерах. Также тепловая карта позволяет увидеть иерархию кластеров, т.е. как кластеры связаны с друг другом.

Вот как она выглядит в нашем случае.

Здесь можно увидеть как самостоятельные кластеры, так и целые группы тесно связанных кластеров. Группы кластеров характеризуют основные маркет-категории, которые имеют разную смысловую окраску. Например, группа Entertainment, в правом нижнем углу имеет дополнительные, уточняющие категории - Photo&Video, Shoping, Music, Lifestyle.

Выводы

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

Разработанная модель кластеризации реализована в партнерстве с сервисом Robolitica и будет использована для анализа рынка мобильных приложений.