Разработка алгоритмов на базе FRiS-функции

Записаться

После введения в когнитивный анализ данных, после рассказа Николая Григорьевича о том, какие задачи возникают в рамках анализа данных, какие задачи решаются с помощью функции конкурентного сходства, мы уже рассмотрим более подробно, как это происходит. Начнем с такой вот картиночки, которая может немножко повторится, может немножечко более понятным сделает то, как вообще выглядит и вычисляется функция конкурентного сходства задачи распознавания, когда у нас имеются объекты в пространстве описывающих признаков, эти объекты относятся в данном случае к двум классам. Класс фиолетовых кружочков и красных квадратиков - это может быть класс здоровых и больных людей, это может быть класс работающих и с браком каких-то выпускаемых приборов, это могут быть классы людей, которые возвращают кредиты и имеют склонность не возвращать их, то есть в различных областях классы могут быть самыми разными. Тут формально два класса и, соответственно, если мы используем функцию конкурентного сходства и пытаемся оценить конкурентное сходство некоторого нового объекта с двумя классами, представленными какими-то наборами каких-то объектов, то мы вычисляем расстояние, во-первых, до первого класса, это расстояние r1, расстояние до второго класса, а дальше уже, чтобы получить количественную величину конкурентного сходства, мы ее вычисляем по следующей функции. Эта величина, она у нас хороша тем, что она нормируемая, то есть она изменяется от минус единицы до единицы. На границе, где эта величина равна нулю, где объект одинаково похож и не похож на оба класса, величина конкурентного сходства принимает значение 0, то есть вот такая вот симметричная величина. И на основе этой функции конкурентного сходства, такой базовый гипотезы, которая кажется совершенно примитивной, элементарной, удалось построить целую серию алгоритмов для решения различных задач анализа данных. На данном слайде приводится список задач, название алгоритмов, которые для их решения разработаны, тут и задачи таксономии с алгоритмом FRiS-Tdx, задача построения решающего правила, задача выбора информативной системы признаков, задача обобщенной классификации, задача прогнозирования, комбинированные задачи, задача заполнения пробелов, то есть эти алгоритмы, они немножечко на разном уровне доработанности, но какие-то рабочие модели уже есть для всех этих задач.

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

Если проводить какую-то классификацию существующих подходов, то их, наверное, можно разделить в первую очередь на статистические, эвристические и немножечко в стороне находятся подходы к распознаванию, основанные на использовании нейронных сетей. Статистические подходы основаны на том, что у нас предполагается, что все объекты в пространстве признаков - это реализации некоторой случайной величины, целевой признак, имя класса, который мы должны прогнозировать - это тоже случайная величина. Предполагается, что у описывающих и целевого признака есть какое-то совместное распределение совместной плотности и, если нам их удается восстановить, то дальше уже оказывается, что существует готовый ответ на то, как распознавать объекты в такой ситуации, этот ответ — это Байесово решающие правило, оно обеспечивает минимальную ошибку распознавания, но для его успешной работы требуется знание стратегии природы, знание совместных распределений, соответственно, статистические подходы, они нацелены на то, чтобы эти распределения, эти плотности восстанавливать. Подразделяют параметрические подходы - это оценка параметров распределения, когда тип распределения задается с точностью до какого-то количества параметров, и дальше на основе обучающей выборки необходимо эти параметры восстановить. Непараметрические подходы - они не ограничивают класс распределений, они пытаются восстанавливать плотность, как бы по окрестности, берут для каждой точки какую-то окрестность достаточного объема, чтобы там сделать какие-то прогнозы и оценивают локальные участки плотности.

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

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

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

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

Теперь, как уже непосредственно алгоритм FRiS-Stolp работает. На первом этапе ищется базовое множество столпов, состоящее из наилучшего кандидата на роль столпа первого класса и наилучшего кандидата на роль столпа второго класса, при этом функция конкурентного сходства вычисляет предположение, что у нас этот образ, для которого мы ищем сейчас наиболее наилучший столб, описывается ровно одним столпом, а образ конкурента, так как мы не знаем положение столпа конкурента, описывается пока всеми объектами, все объекты выступают в роли столпов, то есть рассматривается самый такой сложный случай. И после того, как в таких условиях выбраны по наиболее типичному столпу для каждого класса, система столпов продолжает наращиваться до достижения одного из условий остановки. Условия остановки могут быть разными, одно из них - это достижение заданного уровня точности распознавания обучающей выборки. Я считаю, что он не очень удачен, потому что в задачах, сложных задачах, где у нас выборки небольшие, классы сильно пересекаются, это приводит к очень серьезному переобучению. Построение такого решающего правила, которое хорошо работает на обучающей выборке, потому что оно подгонялось под обучающую выборку, однако при появлении независимой контрольной выборки оно дает гораздо более плохие результаты и перестает работать именно за счет того, что на слишком малом объеме данных строилось слишком сложное решающее правило. Соответственно, считаю более целесообразным наращивать число столпов до достижения какого-то максимального значения, которое зависит от объема выборки, то есть для выборки большого объема мы можем себе позволить строить большее качество столпов, для выборок малых объемов мы себе уже такого позволить не можем, у нас банально потому здесь десять процентов выборки, не больше, может использоваться в роли столпов.

И чуть более подробно, как мы оцениваем качество объекта в роли столпа. Если у нас множество объектов a, вот этот класс - это объекты первого образа, отделенный такой немножечко класс - это объекты второго образа и, соответственно, для оценки, насколько хорош объект ai в роли столпа, мы для каждого объекта из этого класса в качестве расстояния до ближайшего своего используем расстояние до ai, качестве расстояния до ближайшего столпа конкурентов, до ближайшего объекта образа b, второго образа. Соответственно, так, перебирая все объекты образа a вычисляем защищающую способность объекта ai, когда мы вычисляем величину толерантности, то есть того, насколько объект ai мешает нам в процессе правильного распознавания объектов второго образа, мы, соответственно, по аналогии, в качестве расстояния до своего столпа используем расстояние до ближайшего объекта образа b, а в качестве расстояния до столпа конкурента, соответственно, расстояние до объекта ai. Вот из двух таких компонент и складывается общее качество объекта в роли столпа, из защищающей способности, насколько он хорошо защищает свои объекты от неправильного распознавания, и толерантности, насколько этот столп не мешает правильному распознаванию объектов конкурирующего образа.

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

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

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

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

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

Если мы рассмотрим классификацию методов таксономии, которые уже разработаны, разрабатывается они уже довольно давно, то все методы, с одной стороны, можно разделить по типу разделения, то есть алгоритмы таксономии бывают иерархические, когда у нас на разных уровнях иерархии рассматриваются разные разбиения: более детальные, менее детальные, то есть начинается от всех объектов и заканчивается ситуацией, когда все объекты относятся к одному таксону, к одному кластеру. Другая большая группа алгоритмов, она дает один вариант таксономии, не иерархию, а одну таксономию, там различные методы есть, вот тут перечислены: k-Means, который очень популярен в мировом сообществе, Forel, разработанный в Новосибирске, логический алгоритм таксономии - их огромное количество. С другой стороны, все алгоритмы таксономии, так же, как и алгоритмы распознавания, можно разделить с точки зрения базовой гипотезы, то есть их можно разделить на вероятностные, статистические и геометрические. Когда речь идёт о вероятностном подходе к решению задачи таксономии, там предполагается, что у нас имеется некоторая смесь распределений простой формы, образует эта смесь всю выборку, а соответственно, каждый компонент этой смеси простой формы - это какой-то класс, кластер. И нам надо восстановить параметры каждого кластера, вес каждого кластера, соответственно, вот решается такая же задача в каком-то смысле, как и в задаче построение решающего правила статистической постановки задачи оценки плотности по выборке. Чаще всего для этого используются expectation–maximization алгоритм, соответственно, он вот хорошо срабатывает именно когда у нас, во-первых, достаточно большая статистика, есть возможность оценивать параметры этой смеси и предположение, что вот наши кластеры, наши компоненты действительно распределены по тому закону, по которому мы предполагаем.

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

Будем рассматривать алгоритм FRiS-Tax, он у нас работает именно в геометрическом пространстве в виде функции конкурентного сходства, то есть этой тернарной мере сходства. В качестве критерия похожести объектов внутри таксона использует похожесть объектов на некоторого типичного представителя этого таксона, на столп. Это место занимает алгоритм FRiS-Tax. Действительно, задачи распознавания и таксономии, они довольно-таки сильно похожи, поэтому принципы функционирования алгоритма одни и те же по сути, точно так же строится небольшое количество столпов в наиболее ключевых точках в районах сгустков объектов, в их число попадают наиболее типичные представители выборки, и дальше полученный набор, во-первых, может использоваться для разбиения выборки на кластеры, на классы, то есть просто любой объект выборки относится к тому кластеру, на столп которого он максимально похож. Этот набор столпов также может использоваться для оценки компактности выборки, вот такой геометрической компактности, возможности разделить эту выборку на какие-то геометрические компактные сгустки. Наконец, это же множество столпов может использоваться для отнесения уже к построенным кластерам каких-то новых объектов, то есть мы сразу решаем и задачу распознавания вот по этой новой классовой структуре, которую мы сами же создали, то есть это реально оказывается задача комбинированного типа, задача таксономии и построение решающего правила одновременно решается.

Как это происходит? Прежде, чем перейти непосредственно к тому, как работает алгоритм FriS-Tax, я хочу заметить, что в отличие от задачи распознавания, где у нас всегда есть объекты первого образа, объекты второго образа, объекты какого-то k-того образа, то есть всегда можно сказать - этот свой, этот чужой, то в задаче таксономии изначально своих и чужих нет, вся выборка предполагается единообразной, однородной, на ней потом мы построим какую-то классовую структуру, но на начальном этапе она нам неизвестна, поэтому сказать, кто свой, кто чужой мы ещё не можем. Соответственно, чтобы как-то вычислять конкурентное сходство, нам нужен конкурент. Так как среди текущих объектов заранее заданных конкурентов нет, мы придумываем конкурентов сами. Мы вводим такое понятие виртуального конкурента, который находится от каждого объекта на расстоянии r*, то есть, рассматривая это как геометрическую задачку, вводим дополнительное измерение, и в нем размещаем антипространство, в котором находятся конкуренты для каждого объекта. Соответственно, когда мы ввели в функцию конкретного сходства виртуального конкурента, мы уже можем вычислять и функцию конкурентного сходства, про свой мир мы еще ничего не знаем, зато всегда у нас есть конкуренты чужого мира, ближайший конкурент - это собственное отражение в чужом пространстве, то есть мы просто заменяем расстояние до ближайшего конкурента на r*.

Работа алгоритма FRiS-Tax состоит из двух этапов. Во-первых, это этап FRiS-Cluster при котором у нас формируются множество столпов .Очевидно, что, когда мы сформируем множество столпов, то все кластеры, которые порождают этими столпами, будут линейно разделимы, то есть форма максимально простая. Но при этом на практике может оказаться, что форма классов естественная для данной задачи, она сложнее, чем просто линейно разделимая, то есть она может быть достаточно сложной геометрической формы, и для этого, соответственно, предназначается второй этап работы алгоритма этап FRiS-Class, когда у нас эти наши простой формы кластеры объединяются в более сложные структуры, классы, форма которых может быть уже какой угодно, лишь бы она удовлетворяла условиям связанности. Соответственно, если рассматривать, как работает этап FRiS-Cluster, то у нас похожим образом оценивается качество каждого объекта выборки в роли столпа, который максимально описывает эту выборку, и выбирается объект с максимальным качеством. Оказывается, что этот объект выбирается в зоне локального сгущения объектов, при этом в зависимости от того, какой коэффициент, какое расстояние до виртуального конкурента мы используем, сгусток будет либо более локальной окрестности рассматриваться, либо более глобальный взгляд на выборку. Соответственно, после того, как первый столп установлен, мы ищем роль на лучшего второго столпа, и после того, как второй столп появился, мы уже переставляем первый столп, потому что у нас уже выборка описывается двумя столпами, условия задачи другие и может оказаться, что первый столп уже не адекватен, надо его куда-то переместить, именно чтобы лучше всего работал в паре со вторым. Происходит такое наращивание выборки, наращивание множества столпов, происходит перераспределение объектов между столпами, происходит перемещение этих столбов в рамках кластера и, соответственно, критерии остановки тут чуть чуть более хитрые, чем в задаче распознавания, но тут тоже для начала мы дойдем до какого-то максимального количества кластеров, которое мы готовы рассмотреть, а потом уже из них будем выбирать оптимальные.

Тут картиночка, то есть исходная выборка имеет такую достаточно сложную форму, на взгляд человек довольно легко решает такую задачу, однако видно, что с помощью линейно разделимых кластеров ее решить не получится . Посмотрим, как справляется с этой задачей алгоритм FRiS-Tax. Вот выбрался один столп, потом добавился к нему второй столп, после этого добавился третий, а первые два, соответственно, после появления третьего переместились так, чтобы друг другу уже не мешать. Добавился четвертый столп, снова произошло перемещение центров, и так происходило, восемь столпов таким образом распределились по выборке. После этого мы переходим к этапу FRiS-Class и пытаемся объединять кластеры в классы. Естественно, что два кластера, если у них граница пустая, объектов там нет, нету смысла объединять в один класс, они разделены, то есть проверяем вот эту границу между кластерами, если там никого нет, то гипотеза о том, что эти два кластера надо объединить в один класс, отвергается. Зато, если у нас на границе есть объекты и их характер распределения примерно такой же, как внутри этих кластеров, соответственно, это нам дает основание предполагать, что эти два кластера, они относятся к единой структуре более сложной формы, к единому классу. Соответственно, эти два кластера объединятся в один класс, а после этого попарно перебираются все столпы, и часть из них объединяется, соответственно, вот получается такое разделение выборки на четыре класса, то есть было восемь кластеров и четыре класса. Визуально человек-эксперт с таким решением алгоритма соглашается. Но вопрос - как выбирать количество кластеров, как выбирать количество классов? Этот вопрос всегда возникает, когда решается задача таксономии. В каких-то методах количество устанавливается экспертом, в каких-то методах ищутся какие-то локальные скачки, ступенечки в качестве увеличение качества критерия с ростом количества таксонов, в каких-то отыскиваются самые плохие таксоны и пытаются их объединить с хорошими, либо слишком большие таксоны разделять на большее количество таксонов, то есть тут разные подходы. Здесь мы следим за изменением качества таксономии, за изменением компактности нашей выборки в зависимости от того, сколько столпов мы построили. То есть тут справа кривая качества в зависимости от количества столпов, и на ней мы отыскиваем локальные экстремумы. Локальным экстремумам, оказалось, соответствует такая кластеризация, которая кажется подходящей опять же эксперту, то есть тут верификация алгоритма происходила именно на глаз. Хотелось, чтобы алгоритм работал так же, как работает человек-эксперт, работая с подобными данными, сталкиваясь с подобными данными. Соответственно, вот ищется в динамике изменения качества с ростом числа кластеров, с ростом числа столпов такие локальные экстремумы, и этап объединения кластеров в классы выполняется для таких локальных оптимумов. Соответственно, дальше уже выбирается такой вариант таксономии, который обеспечивает максимальный критерий.

Пример задачки - кольцо и центр. Тоже очевидно, что если мы будем строить линейно разделимые кластеры, то никакого хорошего решения мы тут не получим, так работает алгоритм FRiS-Tax с этой задачей, но если присмотреться внимательно, то вот тут у нас до 15 строилось количество столпов, и вот первый локальный экстремум появился на семи объектах, на семи столпах. Вот семь столпов 1, 2, 3, 4, 5, 6, 7, соответственно, после объединения их на этапе FRiS-Class, у нас осталось два таксона - центральный сгусток и кольцо, то есть произошло то самое объединение объектов, которое кажется наиболее естественным человеку.

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

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

Какие основные подходы можно выделить для решения этой задачи? Если речь идет о статистической постановке этой задачи, то тут также используются все эти алгоритмы восстановления смеси распределений, EM-алгоритм активно используя для этой задачи. В Интернет-технологиях довольно широкую популярность приобрел алгоритм Co-training, Co-learning, где используются две независимые системы описания одной и той же выборки, и на их основе производится уже какое-то разнесение каких-то страниц, каких-то ресурсов по каким-то категориям, дальнейшая их обработка, дальнейшее их распознавание. Также выделяют в отдельный класс графовые методы с опорой на классифицированные объекты, примером является алгоритм таксономические решающие функции. Также для решения задач частичного обучения используется широко довольно-таки метод опорных векторов. Он, соответственно, тоже активно используется для решения многих задач анализа данных.

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

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

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

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

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

В конце этой лекции я хочу показать, а почему все-таки оказывается полезным оперировать именно не надёжностью распознавания, а останавливаться на локальном максимуме функции конкурентного сходства. Тут такая игрушечная, опять же, двухмерная задачка, где классы достаточно сложной формы и, если мы будем наращивать систему столпов и следить за качеством, у нас кривая качества будет выглядеть следующим образом, и экстремуму локальному девять столпов соответствует вот такое разделение на такие столпы: 1, 2, 3, 4, 5, 6, 7, 8, 9, то есть у нас каждый вот этот локальный сгусток описывать своим столпом, а вытянутый класс описывается тремя столпами. Но, в принципе, мы могли обойтись меньшим количеством столпов, но при этом обратите внимание, что тут на картинке есть два явно выраженных кластера, в которых нету представителей ни первого образа, ни второго, то есть про них информации нет и, чтобы ее как-то добыть, мы, во-первых, можем именно по этим двум кластерам какую-то дополнительную формацию запросить у заказчика, можем предположить, что эти два кластера - это реализация какого-то нового третьего класса. Тут вот у нас появляется некоторая дополнительная информация о том, как выглядит у нас структура данных, то есть есть какие-то кластеры, про которые у нас информации нет, и мы это знаем и мы уже с ними каким-то образом дополнительно работаем.

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