AN APPROACH TO USER FEEDBACK PROCESSING ORDER TO INCREASE QUALITY OF CLUSTERING RESULTS

Full Text

ВВЕДЕНИЕ Методы кластеризации традиционно относят к методам, обучающимся без учителя. Такое обучение возможно благодаря информации, содержащейся в самих данных, которую и призваны выявить методы кластеризации [14]. Тем не менее, на практике исследователь редко не обладает никакими знаниями об исследуемом наборе данных, будь то экономические данные [30], данные, собранные с датчиков, приборов [35] или каким-либо иным образом компьютерной программной [32]. Практически при каждом решении реальной задачи участие исследователя необходимо либо для построения корректного разбиения на группы, либо принятия решения о структуре иерархии, либо способно существенно повысить качество результата за счет знаний, не включенных в пространство признаков обрабатываемых данных. Особенно это актуально при обработке текстовой информации [31]. Тексты, являясь многомерными объектами, представляют особенную сложность для алгоритмов кластеризации [11]. Без участия эксперта, без выявления его скрытых интенций невозможно заранее определить, какое именно разбиение ожидается в результате работы алгоритма [33]. Помимо очевидной группировки по тематике, тексты могут быть сгруппированы на основании того, от чьего лица ведется повествование, по целевой аудитории текста, по правовому статусу текста или комбинации различных признаков. В этой области абсолютно верно высказывание: «не бывает правильной кластеризации, бывает полезная» [2]. Таким образом, включение эксперта в процесс кластеризации не является недостатком метода, а, наоборот, является желательным [34]. При этом важно, чтобы участие эксперта было органичной частью алгоритма кластеризации, не требовало бы понимания внутренних деталей работы алгоритма, и, при этом, причинно-следственная связь между действиями эксперта и результатами работы алгоритма была бы явной. Недавние исследования отмечают значительный рост в последние годы числа работ, посвященных алгоритмам кластеризации, предполагающим участие исследователя. Например, в работе [2] приводится статистика по годам, представленная на Рис. 1. В данной работе предлагается подход, позволяющий включить использование обратной связи от эксперта по результатам кластеризации в широкое семейство современных алгоритмов кластеризации, основанных на использовании нейронных сетей, в частности представлена реализация на основе алгоритма DEC (Unsupervised Deep Embedding for Clustering Analysis) [25]. Дальнейшее содержимое статьи организовано следующим образом: в первом разделе приводится обзор и анализ смежных работ, во втором разделе сформулирована задача настоящего исследования, в третьем разделе представлен предлагаемых подход, в четвертом - приведены эксперименты подтверждающие работоспособность и эффективность предлагаемого подхода, и в заключении подводятся итоги и описываются возможные направления развития. ОБЗОР И АНАЛИЗ СМЕЖНЫХ РАБОТ Для определения круга смежных работ следует уточнить определения и прояснить классификацию в области методов кластеризации. В современной научной литературе сложилась практика обозначения методов кластеризации, в которых используется та или иная дополнительная информация, не включенная в набор данных, методами кластеризации с частичным привлечением учителя (semi-supervised), кластеризацией с ограничениями (constrained clustering) [6]. При этом в подавляющем большинстве таких методов информация дана a priori и подается на вход алгоритму кластеризации совместно с набором данных в виде частично промаркированных объектов [5], заданных ограничений на пары объектов [9], ограничения на структуру иерархии кластеров, перенос знания в виде предобученной нейронной сети (transfer learning) [24], например, на задаче классификации в схожей предметной области и т.д. При этом и ограничения на объекты и метки могут быть заданы не жестко (soft labels) [20]. Однако, существуют методы предполагающие получение дополнительной информации непосредственно в процессе кластеризации. Их подробный обзор произведен в работе [2]. Такие методы называются методами интерактивной кластеризации. Одним из первых таких методов стал нечеткий метод [22]. От характера взаимодействия и получаемой информации они подразделяются на: активную кластеризацию как пример активного обучения [8, 12]; кластеризация с подкреплением, получаемой в виде обратной связи от среды в которой происходит кластеризация [3]; интерактивная кластеризация с обратной связью (interactive clustering under feedback, mixed-initiative clustering), подразумевающая получение обратной связи от пользователя в виде оценки результатов или указаний по корректировке алгоритма. Последние методы позволяют выявить скрытые интенции пользователя и получить по настоящему полезную кластеризацию, т.к. хорошо соответствуют тезису: «пользователь узнает правильный результат, когда увидит его». Исследователи отмечают, что к интерактивным методам зачастую ошибочно относят и методы кластеризации с интерактивными операциями: методы интерактивной визуализации результатов кластеризации, методы подбора выбора алгоритмов кластеризации и т.п. [2]. Для полноты картины следует упомянуть методы вспомогательной кластеризации (assisting clustering) [7], в которых ведущая роль отдана исследователю; именно он определяет количество кластеров и их характеристики, а алгоритм предлагает варианты их наполнения и корректировки структуры. Однако этим методы на данный момент не получили значительного распространения. Методы интерактивной кластеризации с обратной связью можно разделить на два множества по тому, на что направлена обратная связь от исследователя. В первом более многочисленном семействе методов исследователь интерактивно и итеративно может влиять на параметры алгоритма кластеризации, метрику схожести (близости), модифицировать пространство признаков [16]. Во втором множестве методов исследователь взаимодействует непосредственно с результатами кластеризации, указывая, какие кластеры необходимо объединить или разъединить, какие элементы добавить или исключить из кластера, каким образом образовать новый кластер или куда отнести элементы, выпадающие из кластеризации [2, 4]. Подход, предлагаемый в данной работе, относится именно ко второму множеству, что позволяет исследователю не погружаться в детали реализации алгоритма и использовать новые появляющиеся методы, не меняя характер своей работы. Первым этапом интерактивной кластеризации, очевидно, является обычная кластеризация без учителя. Таким образом, все методы интерактивной кластеризации базируются на методах без учителя, добавляя в них механизмы работы с обратной связью. Согласно исследованию [2] результаты, которого представлены на Рис. 1. Большинство методов интерактивной кластеризации основываются на классических методах кластеризации, таких как: k-means, c-means, вариациях иерархической кластеризации и кластеризации графов. Малое число методов использует нейронные сети, при этом используются сети SOM (Kohonen self-organized maps). Классические методы кластеризации успешно применяются на практике и показывают высокие результаты, тем не менее, существует большое количество современных методов, демонстрирующих намного лучшие результаты (state-of-the-art results). Большинство этих методов основываются на использовании сетей c глубинным обучением (deep neural network) [18, 23, 26, 27]. Такое превосходство объясняется способностью сетей обучаться на смежных предметных областях или схожих задачах (transfer learning, learning to cluster) и строить сложные нелинейные преобразования для получения пространства признаков (representation learning, embedding learning) одновременно содержащего максимум информации и «удобного» для алгоритма кластеризации (например, сильное понижение размерности входных данных) [29]. Но самым главным вкладом использования нейронных сетей в методы кластеризации является возможность построения непрерывной кластеризации (end-to-end clustering), в которой отсутствует явное разделение алгоритма на две фазы: построение пространства признаков и разбиения на группы [13, 19]. При таком подходе обучение сети подходящему представлению данных происходит одновременно с итерациями разбиения множества на кластеры или построения иерархии из них. В ряде методов авторы показывают возможность дальнейшего переноса полученных знаний сети на смежные задачи, например, использование сети, обученной для кластеризации одного вида изображений на другой вид изображений. Существуют работы, посвященные кластеризации с частично размеченным набором данных на базе нейронных сетей [15, 24], но они используют эту маркировку в процессе первоначального обучения сети, а не получают в виде обратной связи, т.е. не подстраиваются в процессе обработки результатов под нужды исследователя. ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ В своем исследовании [1] авторы предлагают обобщенную схему построения современных методов кластеризации с использованием нейронных сетей, в которую укладывается подавляющее большинство методов (Рис. 2.) [10, 25, 28]. Из этой схемы видно, что обработка обратной связи на уровне единой целевой функции (функции потерь, штрафной функции, loss function) позволит одновременно строить представление объектов в соответствии с интенцией исследователя, влияя на веса нейронной сети и корректировать ошибки кластеризации, влияя на результат следующей итерации кластеризации (например, смещая центры кластеров). Задачей данного исследования является построение метода интерактивной кластеризации с обратной связью на базе современных методов кластеризации, укладывающихся в выше обозначенную обобщенную схему. В качестве основы могут быть использованы методы кластеризации на базе нейронной сети с единой целевой функцией, основанной на метрике Кульбака-Лейблера (Kullback-Leibler). В частности, будет представлена реализация на базе метода кластеризации DEC (Unsupervised Deep Embedding for Clustering Analysis) [25]. Встраивание обработку обратной связи в этом случае возможно благодаря тому, что данная целевая функция, по сути, управляет силой притяжения между элементами и центрами кластеров. Таким образом, оказывая точечное воздействие на эту силу, можно предсказуемо управлять результатом кластеризации. ПОДХОД К ОБРАБОТКЕ ОБРАТНОЙ СВЯЗИ Придерживаясь идеи, что для исследователя наиболее простой и точной обратной связью будет критика полученных результатов кластеризации, в данном подходе предполагается обратная связь двух видов: «элемент Xi должен принадлежать кластеру Cj» и «элементу Xi не следует находиться в кластере Xj». Одновременно может быть получено произвольное количество таких ограничений, в частности, легко задается ограничение «поменять местами элементы Xi и Xj» комбинацией двух ограничений первого вида. Как уже было указано выше, в качестве базового был выбран метод кластеризации DEC (Unsupervised Deep Embedding for Clustering Analysis), при этом аналогичный подход может быть применен ко множеству других алгоритмов, например, к DEPICT [10]. Входной набор данных X={xi | i ∈ [0, N) }, N - кол-во элементов в наборе. Это множество с помощью энкодера, являющегося частью заранее обученного автоэнкодера, отображается в пространство меньшей размерности: fθ: X → Z, где θ - параметры нейронной сети, Z - скрытое пространство признаков. Пространство признаков называется в данном случае скрытым, т.к. его построение происходит в процессе обучения нейронной сети и затем оно формируется неявным образом в процессе обучения автоэнкодера и решения задачи кластеризации. В данной работе используется энкодер следующей структуры: d-50-50-20-k, где d-размерность входного набора данных, k - число кластеров. Результатом работы алгоритма является набор центров кластеров в пространстве Z: {µj ∈ Z| j ∈ [0, k)}, где k - заданное число кластеров. Инициализация центров кластеров происходит при помощи алгоритма k-means, который применяется к представлению векторов, полученному в результате обучения автоэнкодера. Процессы определения оптимального расположения центров кластеров и построения пространства признаков происходят одновременно за счет определения общей функции потерь. Для этого в качестве меры расстояния между элементом и центром кластера используется метрика, основанная на распределении Стьюдента с одной степенью свободы. Целевая функция (функция потерь, loss function) или штрафная функция строится как метрика Кульбака-Лейблера (Kullback-Leibler divergence) между фактическим и целевым распределением. В качестве целевого распределение используется следующее распределение: Это распределение обладает следующим свойствами: усиливает вклад от элементов с большой долей принадлежности кластеру и нормализует влияние больших кластеров, не позволяя им чрезмерно притягивать к себе удаленные элементы за счет своего размер (аналог гравитации). Нетрудно заметить, что целевая функция направлена на то, чтобы qij было больше pij. Если посмотреть на частные производные для обновления весов нейронной сети и векторов центров кластеров. то можно понять, что в случае отрицательной разницы (pij-qij) будет происходить «выталкивание» элемента из кластера, несмотря на отсутствие штрафа со стороны целевой функции. Для учета обратной связи предлагается использовать следующие формулы градиентов: где T = {tij} - матрица обратной связи (подсказок пользователя, tips), в которой: Абсолютное значение tij определяет скорость (силу притяжения), с которой элементы и центры кластера будут стремиться друг к другу или отталкиваться друг от друга. Также на эту скорость влияет выставленный уровень обучения (learning rate) у нейронной сети. В данной работе в экспериментах использовалось значение 1000 для обоих видов обратной связи. При этом эксперименты показали, что для случая выталкивания элемента из кластера имеет смысл использовать большие абсолютные величины, чем при притяжении. ОПИСАНИЕ ЭКСПЕРИМЕНТОВ И АНАЛИЗ РЕЗУЛЬТАТОВ В данном разделе для демонстрации работоспособности предложенного подхода представлены два вида экспериментов. Вначале показывается работа на сгенерированном наборе данных из простых векторов, процесс кластеризации которых является тривиальным. При этом в силу вариативности исследовательского намерения, любой алгоритм кластеризации может расположить их неправильно. В экспериментах показывается, каким образом исследователь может уточнить свое намерение, и кластеризация подстраивается под него. Во втором разделе эксперимент проводится на каноническом наборе данных - «Ирисы Фишера», для демонстрации того, как исследователь может добавить информацию, не содержащуюся в данных, и тем самым улучшить результаты кластеризации, и на наборе данных новостного агентства Reuters для сравнения эффективности предлагаемого подхода с аналогичным методом. Демонстрация работы на синтетическом наборе данных. Для демонстрации работы был сгенерирован набор данных из 400 элементов, следующим образом: 1. За основу взяты 4 вектора {(1,0,0,0); (0,1,0,0); (0,0,1,0); (0,0,0,1)}. 2. Для каждого из 4-х векторов сгенерированы 125 векторов добавлением к каждой компоненте случайной величины из равномерного распределения U[0, 1/10]. Добавленный случайный шум совсем небольшой, т.к. в данном эксперименте задачей ставится показать влияние обратной связи, а не качество работы алгоритма самого по себе. 3. Векторы в выборке расположены последовательно четверками, таким образом, первые 4 вектора содержат по 1 представителю от каждого базового класса. В результатах экспериментов детально будут показаны только первые 12 векторов для краткости и ясности картины результата. Для указанного набора данных был запущен алгоритм кластеризации с разбиением множества на 2 кластера. Результаты работы алгоритма кластеризации представлены в Таблице 1, при этом для автоэнкодера достигнутое значение функции потерь на проверочной выборке равно 0.000341. На Рисунке 3 показано распределение первых 12 векторов по кластерам. Далее будут показаны три эксперимента для различных видов обратной связи: указание о необходимости включения вектора X0 в кластер C0; указание о необходимости исключения вектора X1 из кластера C1; комплексная обратная связь по замене векторов X2 и X3 местами в кластерах C0 и С1 соответственно. Все эксперименты выполняются как первая итерация после первоначальной кластеризации, а не последовательно, исключительно для более удобного сравнения. Последовательное применение, очевидно, возможно, без каких либо ограничений или особенностей в работе алгоритма. В первом эксперименте предположим, что исследователь обладает информацией, о том, что вектор X1 семантически ближе к векторам X2 и X3, чем к вектору X0. Поэтому для алгоритма кластеризации формируется обратная связь в виде матрицы T[500, 4] = {tij | i ∈ [0, 500), j ∈ [0, 4)}, указывающей, что вектор X1 должен перейти в кластер C1. Результаты 100 эпох работы алгоритма кластеризации представлены на Рис. 4. Вместе с вектором X1 в кластер C1 переместились и все остальные векторы 2 класса, при этом можно заметить, что взаимное расположение между 3-м и 4-м классами сохранилось. Также сохранилось взаимное расположение большинства векторов внутри каждого класса и относительно центра соответствующего кластера. Во втором эксперименте предположим, что исследователь обладает информацией, о том, что вектор X2 семантически далек от вектора X3, поэтому он должен выйти из кластера С1. При этом кластер реципиент неизвестен исследователю, в случае более чем 2-х кластеров предпочтение никакому из кластеров исследователь не отдает. Для алгоритма кластеризации формируется обратная связь в виде матрицы T[500, 4] = {tij | i ∈ [0, 500), j ∈ [0, 4)} указывающей, что вектор X2 должен выйти кластера C1. Результаты 100 эпох работы алгоритма кластеризации представлены на Рис. 5. Вектор X2 покинул кластер С1 и вместе с вектором X2 в кластер C1 переместились и все остальные векторы 3 класса. При этом можно заметить, что т.к. исключение из кластера это, по сути, ослабление силы притяжения между вектором и центром кластера, то исключаемый класс оказался максимально далеко от центра кластера С1 и достаточно далеко от центра кластера С0. Также можно заметить предсказуемую более низкую скорость сходимости алгоритма кластеризации при операции исключения из кластера, чем при операции включения в кластер. В третьем эксперименте предположим, что исследователь обладает информацией о необходимости изменить расположение сразу двух векторов. Вектор X1 требуется перемесить в кластер С1, а вектор X2 переместить в кластер С0. Для алгоритма кластеризации формируется обратная связь в виде матрицы T[500, 4] = {tij | i ∈ [0, 500), j ∈ [0, 4)} следующего вида. Результаты 100 эпох работы алгоритма кластеризации представлены на Рис. 6. Классы 2 и 3 поменялись местами вслед за своим представителями векторами X1 и X2. В четвертом эксперименте изменим набор данных, увеличив уровень шума в векторах в десять раз добавлением к каждой компоненте случайной величины из равномерного распределения U[0, 1]. Первые 4 вектора и результат кластеризации указаны в Таблице 2. На Рисунке 7а показаны первые 12 векторов и результат кластеризации. Видно, что векторы X0 и X2 соотнесены с кластерами неверно. Для исправления результата алгоритма кластеризации формируется обратная связь в виде матрицы T[500, 4] = {tij | i ∈ [0, 500), j ∈ [0, 4)} следующего вида: Результаты 100 эпох работы алгоритма кластеризации представлены на Рис. 7b. Ошибочно соотнесенные векторы перешли в корректные классы, при этом остальные представители классов по-прежнему соотнесены корректно, т.к. внесенные изменения объективно улучшили качество кластеризации, и изменения оказали точечное воздействие, в отличие от предыдущих экспериментов. Демонстрация работы на примере набора данных «Ирисы Фишера». Набор данных “Ирисы Фишера” является классическим для задач классификации и кластеризации [17]. В наборе представлены длина и ширина наружной и внутренней долей околоцветника для трех видов (‘setosa’, ‘versicolor’, ‘virginica’). В Таблице 3 представлены примеры 3-х векторов по одному для каждого вида. К исходным данным к каждой компоненте добавлена случайная величина из равномерного распределения U[0, 1/10] для усложнения задачи и генерации 600 примеров из 150 имеющихся. На Рисунке 8a. представлены результаты работы алгоритма кластеризации для 3-х кластеров. Кластер, соответствующий виду ‘setosa’, отчетливо и безошибочно отделен, а в кластерах двух других видов имеется 13 и 16 перепутанных местами векторов. Виды ‘versicolor’ и ‘virginica’ являются близкими, и даже в задачах классификации их не удается однозначно разделить. Тем не менее, предположим, что исследователь обладает информацией о двух векторах (экземплярах цветка, видовая принадлежность которых ему вполне могла быть известна), которые необходимо поменять местами. В данном примере это векторы с порядковым номером 7 и 50. Для этого формируется обратная связь в виде матрицы T[600, 3] = {tij | i ∈ [0, 600), j ∈ [0, 3)} следующего вида: Результаты 100 эпох работы алгоритма кластеризации представлены на Рис. 8b (для проекции на плоскость 3-х мерных данных использовался алгоритм t-SNE, реализованный в python библиотеке sklearn [21]). Ошибочно соотнесенные векторы перешли в корректные классы, при этом большая часть ошибок также исправилась. Перепутанными остались 8 и 2 векторов во 2-ом и 3-м классах соответственно. Это дает точность (accuracy), равную 0.98(3). Такие результаты трудно достижимы даже для алгоритмов классификации, средним результатов для лучших из которых является 0.971. Алгоритмы кластеризации зачастую полностью не способны различить 2-ой и 3-ий виды [17]. Демонстрация работы на примере набора данных Reuters (RCV1-v2/LYRL2004). Набор данных RCV1-v2 содержит 810 000 новостей на английском языке новостного агентства Reuters. Новости классифицированы по 103 категориям, которые, в свою очередь, сгруппированы по 4-м крупным тематикам: государство и социальная сфера, экономика, корпоративные новости и производство, биржевые рынки и акции. Данный набор данных является классическим для проведения сравнения эффективности алгоритмов кластеризации. В частности в книге [6] в главе “Semi-supervised Clustering with User Feedback” алгоритм кластеризации без учителя применялся к набору данных Reuters, из которого были отобраны 5 групп по 25 новостных статей по различным подгруппам. Т.к. в статье не описывается принцип формирования групп, а в ряде других статей [25] используется кластеризация текстов по 4-м корневым категориям, для проведения эксперимента было отобрано 4 группы по 32 новостных статьи в каждой. Были выбраны статьи из следующих тематик: • C21 - продукты и производство, поставки, сервисы и мероприятия, минеральная и сельскохозяйственная промышленность (products and production, output, services and activities, mineral and agricultural production) • E41 - трудоустройство, безработица, взаимоотношения с работодателями (employment, unemployment, labour and labour relations) • GCRIM - Гражданское и уголовное право, правовые нарушения, нарушения порядка, преступления в сфере оборота наркотиков, преступления в сфере бизнеса, преступления, мошенничество, убийства, преступники, мафия, полиция (civil and criminal law; law and order issues, drug related crime, corporate crime; crime; fraud; murder; criminals; mafia; police) • M11 - Рыночные курсы, биржевые котировки (stock exchanges, performance of equities) В качестве векторов признаков были использованы стандартные векторы набора данных RCV1-v2 на основе TF-IDF, т.к. именно такой способ был использован экспериментах для сравнения. Эти векторы имеют размерность 47 236. Первая итерация алгоритма показала чистоту кластеров в 25-50%. На рисунке 9 представлены результаты после преобразования t-SNE к двумерному пространству. Как видно, явное разделение кластеров отсутствует. Для сравнения в [6] приводятся следующие результаты: на первом этапе кластеризации без учителя чистота кластеризации колеблется от 44-50% и далее при получении 5-15 ограничений виде обратной связи чистота кластеров повышается и достигает 70-80%. В проводимом эксперименте кластеризации с помощью представленного в данной работе метода, применение 5-10 ограничений приводит к повышению чистоты кластеров в 75-85%. Что в среднем на 5% выше результатов в работе, выбранной для сравнения, при этом объем необходимых дополнительных ограничений в 1,5-2 раза меньше. При этом стоит отметить, что достигнутый результат сравним с результатами классификации (обучение с учителем), как в случае, если бы все значения меток для всего набора данных, использованного в обучении, были бы известны. ЗАКЛЮЧЕНИЕ В данной работе показана актуальность проблемы разработки методов интерактивной кластеризации с обратной связью, особенно с учетом большого числа современных методов кластеризации без учителя, демонстрирующих выдающиеся результаты. В связи с этим, представлен подход к построению метода интерактивной кластеризации с учетом обратной связи на базе современных непрерывных методов кластеризации с использованием нейронных сетей. В частности представлена реализация на основе метода кластеризации DEC, и продемонстрирована работоспособность и эффективность подхода. При этом замечена недостаточная чувствительность алгоритма к обратной связи вида «исключить из кластера». В качестве следующих этапов работы предполагается продолжить исследования вариантов выбора целевого вспомогательного распределения и его влияния на качество и эффективность кластеризации. Также планируется провести доработку подхода для включения дополнительных видов обратной связи, например, попарной связи и желаемой структуры кластеров, в частности, равномерности распределения элементов по кластерам и повышению эффективности уже используемых ограничений. БЛАГОДАРНОСТИ Исследование выполнено при финансовой поддержке РФФИ и Правительства Ульяновской области в рамках научного проекта № 18-47-00019

About the authors

P. V Dudarin

Ulyanovsk State Technical University

Email: p.dudarin@ulstu.ru
Ulyanovsk, Russia

V. G Tronin

Ulyanovsk State Technical University

Email: v.tronin@ulstu.ru
Ulyanovsk, Russia

N. G Yarushkina

Ulyanovsk State Technical University

Email: jng@ulstu.ru
Ulyanovsk, Russia

References

Supplementary files