Классификация задач. Функция конкурентного сходства

Записаться

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

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

Какие конкретно задачи обнаружения и усиления гипотез решаются? Самая простая задачка - задача редактирования. Есть протокол наблюдений, рассматриваем здесь простой случай - двойная гипотеза, плоская таблица, причем признаки измерены в каких-то характеристиках, пока не будем уточнять, а вот есть еще одна целевая характеристика - самый крайний, последний столбик, в котором указана некоторая классификация: объекты - это строчки, а в этом столбце указано единичкой - это строчки, принадлежащие одному классу, а нолики - принадлежащие другому классу. На самом деле задача реальная содержит не просто два класса, а много — неважно, будем рассматривать случай — два класса. Задача такая — проверить, если описывающие характеристики — это, скажем, показатели пациента, симптомы его, а целевой столбик - это диагноз заболевания, болен или здоров, то надо проверить, нет ли ошибок диагнозе. Как это делается? Берется, закрывается как бы от машины каждая клеточка целевого признака, каждое значение, и делается такое предсказание, что же там должно стоять, ориентируясь на сходство с имеющимся остальными строчками. Выбирается подмножество компетентных строчек и дальше некая решающая функция, как использовать информацию с этих компетентных похожих строчек, позволяет заполнить эту клеточку. Если в исходной таблице стояла единица, а в результате этого прогнозирования получился ноль, значит надо проверять. Первый ряд - это формальный такой диагноз, неправильный. Это касается не только целевой характеристики - это касается и всех описывающих характеристик. По-очереди можно клеточку закрывать и предсказывать, и смотреть, правильно там все или нет. Такие задачи - задачи редактирования, и они интерес представляют в реальности. Например, есть такое хорошо развивающееся направление, называется Fraud Detection - обнаружение мошенничества. В свое время мы решали много задачи для гос. плана Российской Федерации, и им очень нравилось, когда наши методы указывали, а вот некая область - тут что-то несоответствие, указывают там урожайность такую-то в отчётах, а на самом деле закономерной должна быть другая, судя по площадям, по качеству почвы, количеству удобрений - что-то не то. Либо завышают искусственно, либо занижают искусственно из каких-то соображений. Сотрудники гос. плана говорили «Так я и знал, это же они всегда стараются нас обмануть». Так что задача Fraud Detection очень актуальна была и есть - обнаружение ошибок или умышленных искажений. Это один тип задач.

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

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

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

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

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

Фактически направление Data mining было рождено именно потребностью решать такие задачи, как вот один американец говорил: «Как появился Data mining? Вот приходит заказчик, у которого там накоплено огромное количество информации, и он не знает, что с ней делать, с какой стороны подойти к этой куче. Он говорит - ну помогите разобраться, разложите по каким-то кучкам, да скажите, что важно, что не важно и как отличать одну кучку от другой? Это как раз задача SDX».

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

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

В свое время мы опубликовали статью, это было в 2007 году, в журнале, статью про Онтология Data Mining, где мы расписали, из чего эта проблема состоит, из каких ветвей, какие тут направления, вот целый путь — это распознавание образов, эти вот задачи базового типа, скажем, это разные алгоритмы для решения каждой задачи, а зеленые квадратики - это реальные программы или алгоритмы, описанные в литературе. Видите, сколько много методов решения этих задач, и это только самая выжимка, а на самом деле их на порядок больше, каждый алгоритм свою программу делают обычно, и это пышное дерево может произвести впечатление того, что это направление процветает, оно бурно развивается, все хорошо. Но мы пришли к заключению, что это признак слабости, это признак, как говорил Велихов по поводу таких задач, что это не мускулатура, а это раковая опухоль. Так вот, это заболевание объясняется тем, что нет единого подхода, который бы позволял уменьшить это разнообразие. Чем же оно порождается в реальных алгоритмах? Мы пришли к заключению, что главный элемент, который плодит все эти варианты - это разные способы оценки сходства. Это главное, чем люди занимаются. Я хочу сказать, что в области выращивания этого дерева большой вклад имеется наших отечественных ученых. Я хотел бы отметить некоторые школы: алгебраический подход развивается под руководством Юрия Ивановича Журавлева и Константина Владимировича Рудакова, в учебном центре в Москве очень сильный, хороший коллектив. Статистический подход - это классик, так сказать, Айвазян и многие другие ученики Колмогорова этим занимаются, и очень эффективно занимались и сейчас, но не только. Здесь также надо отметить вклад Вапника и Червоненкиса, это их монография на эту тему послужила таким большим толчком, учебником к пониманию самой проблемы. Построение решающих правил - Воронцов Константин Владимирович, тоже из коллектива Журавлева. Эвристические подход - тут заложил, я думаю, главное Ивахненко Алексей Григорьевич, в Киеве был такой очень интересный человек, и я его считаю моим учителем заочным, но потом наши сотрудники, мы со Лбовым тут приложили руку, Миркин Борис Григорьевич, Воронин Юрий Александрович, Дорофеюк Александр Александрович. Можно было бы назвать еще десятки уважаемых людей, которые развивали и развивают эти подходы.

Все эти подходы, в статистике, например, основываются на том или ином способе измерения сходства, и все эти меры сходства грешат одним - сходство между объектами a и b, как мы видим из этих формул, зависит только от этих двух объектов, и ни от чего другого. Есть самые разнообразные формы - в брошюрке Воронина на эту тему приведено более 40 таких способов. А человек, по нашему мнению, не занимается тем, что разные методы, у него какой-то есть свой природный механизм, и вот надо бы посмотреть, как он это делает. Представим себе такую задачу: верхняя часть рисунка, два шарика на расстоянии r. Задаю вопрос - похожи они друг на друга настолько, чтобы можно было их объединить в один класс? Ответа на это разумного получить не удается - одному кажется, похоже, другому — нет, и какое-то сомнение у каждого на эту тему. Вторая строчка - три шарика, а и b остаются на том же расстоянии, но около b появился объект c близко. Теперь можно ли а и b в один класс объединять? Ну, скажет зритель, вряд ли, скорее уж b и c объединить в один класс, а a отдельно, ну есть основание для этого утверждения. Третья строчка, а и b на том же расстоянии, но объект c на большом удалении. Теперь похожи а и b настолько, чтобы их объединить? Да, пожалуй можно. Таким образом, ответ на этот вопрос зависит от ответа на следующий вопрос, по сравнению с чем? Есть такая бытовая, совершенно, кажется, бессмысленная фраза - «Все познается в сравнении», но это так, между делом все говорят. На самом деле это колоссальный закон природы. Действительно, только в сравнении чего-то мы и познаём, чего бы это ни касалось. Так вот, в классификации нужно именно принимать решение не по абсолютному значению расстояния, как бы хитро мы его там не вычисляли, а именно по тому, по сравнению с чем это рассматривается.

Мы формализовали это следующим образом - вот представьте себе, что средний шарик находится между шариком левым и правым, и нужно решить, к какому из этих верхних шариков его надо присоединить, объединить в класс. Для этого мы измеряем два расстояния: r1 до первого шарика, r2 до второго шарика, и потом очень простая формула: в числителе r2 минус r1, а в знаменателе их сумма для нормировки. И эта функция принимает значение от плюс единицы до минус единицы. Плюс единица в том случае, если контрольный этот средний шарик совпадает с левым шариком, совсем совпадает, r1 равно нулю. Тогда, как мы видим из этой формулы, F равно единице. А если этот шарик, мы смотрим, не похож ли он на первый, а он совпал со вторым, то мы скажем — нет, абсолютно не похож, при этом формула говорит минус единица, это максимальное расхождение, максимальная непохожесть. Ну а если он посередине находится, такой F принимает 0,5, то есть одинаково правильно и туда, и туда, или наоборот, одинаково правильно ни туда, ни сюда. То есть эта функция позволяет весь этот спектр возможностей отразить. Она называется функцией конкурентного сходства, сокращенно мы это назвали FRiS-функция.

Относительные меры сходства. Они применяются у нас во всех ныне используемых нами алгоритмах, но надо сказать, что они не являются открытием нашим собственным. Дело в том, что относительные меры на самом деле использовались другими авторами раньше. В каком виде? Известное классическое правило Байеса, когда решение принимается по отношению вероятностей друг к другу двух гипотез. Объект z относится к классу A, если вероятность принадлежности к A больше вероятности принадлежности к B. Неважно, насколько больше, то есть в шкале порядка это рассматривается. Участвует не просто расстояние до A или вероятность A, а обязательно еще конкуренция, с B сравнивается, это очень важно, то есть это уже тернарные меры.

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

Количественная мера стала применяться, алгоритм Relief, это уже очень похоже на то, что я вам показывал — в числителе r2 минус r1, но в знаменателе d - диаметр обучающей выборки, но это нам не понравилось, потому что диаметр может быть большим, а нас интересуют локальные ситуации вокруг распознаваемого образа, и надо посмотреть, кто рядом находится, куда ему отнести, при чем тут большой диаметр или маленький, нам нужно вот такую задачу решить, поэтому мы от этого отказались. Ну вот еще и ширина профиля, это значит, это эти работы я узнал только в прошлом году, это мне подсказал Борис Глебович Миркин, работа, в которой применяется вот такая мера - числитель тот же самый, но знаменатель - максимум из этих двух r2 или r1, то есть нормировка относительно локальной ситуации. Не очень хорошо, что эта нормировка разная, и поэтому как-то не очень предсказуемо, сама количественная оценка в диапазоне от плюс единицы до минус единицы. Поэтому мы придерживаемся все-таки нашей формулы и считаем, что главная заслуга не в том, какую из этих формул взять, потому что формула ширина профиля дает результаты, очень близкие к тому, что и мы получаем со своей мерой сходства. Главное, что мы к этому моменту наработали уже много алгоритмов на базе этой меры, поэтому наши программы ориентированы на этой мере. Дело вкуса, можно всюду в наших алгоритмах один блочок поменять, на ширину профиля, если это кому-то больше нравится и может, но наши алгоритмы будут также работать.

Дальше мы переходим к рассмотрению вот этих самых алгоритмов.