2. К р и ц м а н В. А., Р о з е н Б. Я., Д м и т р и е в И. С. К тайнам строения вещества. – Вышейшая школа, 1983.

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

§ 9. Теоретические методы исследования

Урок-лекция

На свете есть вещи поважнее

самых прекрасных открытий –

это знание методов, которыми

они были сделаны

Лейбниц

https://pandia.ru/text/78/355/images/image014_2.gif" alt="Подпись: !" align="left" width="42 height=41" height="41">Метод. Классификация. Систематизация. Систематика. Индукция. Дедукция.

Наблюдение и описание физических явлений. Физические законы. (Физика, 7 – 9 кл.).

Что такое метод. Методом в науке называют способ построения знания, форму практического и теоретического освоения действительности. Фрэнсис Бэкон сравнивал метод со светильником, освещающим путнику дорогу в темноте: «Даже хромой, идущий по дороге, опережает того, кто идет без дороги». Правильно выбранный метод должен быть ясным, логичным, вести к определенной цели, давать результат. Учение о системе методов называют методологией .

Методы познания, которые используют в научной деятельности – это эмпирические (практические, экспериментальные) методы: наблюдение , эксперимент и теоретические (логические, рациональные) методы:анализ , синтез , сравнение , классификация , систематизация , абстрагирование , обобщение , моделирование , индукция , дедукция . В реальном научном познании эти методы используют всегда в единстве. Например, при разработке эксперимента требуется предварительное теоретическое осмысление проблемы, формулирование гипотезы исследования, а после проведения эксперимента необходима обработка результатов с использованием математических методов . Рассмотрим особенности некоторых теоретических методов познания.

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

Например, всех учеников школы можно разделить на подклассы – «девушки» и «юноши». Можно выбрать и другой признак, например рост. В этом случае классификацию возможно проводить по-разному. Например, выделить границу роста 160 см и классифицировать учеников на подклассы «низкие» и «высокие», или разбить шкалу роста на отрезки в 10 см, тогда классификация будет более детальная. Если сравнить результаты такой классификации по нескольким годам, то это позволит эмпирическим путем установить тенденции в физическом развитии учеников. Следовательно, классификация как метод может быть использована для получения новых знаний и даже служить основой для построения новых научны теорий.

В науке обычно используют классификации одних и тех же объектов по разным признакам в зависимости от целей. Однако признак (основание для классификации) выбирается всегда один. Например, химики подразделяют класс «кислоты» на подклассы и по степени диссоциации (сильные и слабые), и по наличию кислорода (кислородсодержащие и бескислородные), и по физическим свойствам (летучие – нелетучие; растворимые – нерастворимы) и по другим признакам.

Классификация может изменяться в процессе развития науки.

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

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

БОЛЬШИЕ ПЛАНЕТЫ СОЛНЕЧНОЙ СИСТЕМЫ

ПЛАНЕТЫ ЗЕМНОЙ ГРУППЫ	ПЛАНЕТЫ - ГИГАНТЫ

ПЛУТОН

МЕРКУ-	ВЕНЕ-		МАРС	ЮПИТЕР	САТУРН	УРАН

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

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

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

Индукция и дедукция. Путь познания, при котором на основе систематизации накопленной информации – от частного к общему – делают вывод о существующей закономерности, называют индукцией. Этот метод как метод изучения природы был разработан английским философом Ф. Бэконом. Он писал: «Надо брать как можно больше случаев – как таких, где исследуемое явление есть налицо, так и таких, где оно отсутствует, но где его можно было бы ожидать встретить; затем надо расположить их методически... и дать наиболее вероятное объяснение; наконец, постараться проверить это объяснение дальнейшим сравнением с фактами».

Мысль и образ

Портреты Ф. Бэкона и Ш. Холмса

Почему портреты ученого и литературного героя расположены рядом?

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

Рене Декарт, французский философ и ученый.

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

В реальной исследовательской деятельности методы научных исследований взаимосвязаны.

1. ○ Объясните, что такое метод исследования, методология естественных наук?

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

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

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

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

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

2. Методы решения основной задачи кластерного анализа (классификации без учителя) – нахождение группировок объектов (кластеров) в заданной выборке многомерных данных. Приведен краткий обзор основных подходов для решения задачи кластерного анализа и описание комитетного метода синтеза коллективных решений.

3. Программная система интеллектуального анализа данных, распознавания и прогноза РАСПОЗНАВАНИЕ. В основу требований к системе положены идеи универсальности и интеллектуальности. Под универсальностью системы понимается возможность ее применения к максимально широкому кругу задач (по размерностям, по типу, качеству и структуре данных, по вычисляемым величинам). Под интеллектуальностью понимается наличие элементов самонастройки и способности успешного автоматического решения задач неквалифицированным пользователем. В рамках Системы РАСПОЗНАВАНИЕ разработана библиотека программ, реализующих линейные, комбинаторно-логические, статистические, нейросетевые, гибридные методы прогноза, классификации и извлечения знаний из прецедентов, а также коллективные методы прогноза и классификации.

1. Алгоритмы распознавания, основанные на вычислении оценок. Распознавание осуществляется на основе сравнения распознаваемого объекта с эталонными по различным наборам признаков, и использования процедур голосования. Оптимальные параметры решающего правила и процедуры голосования находятся из решения задачи оптимизации модели распознавания - определяются такие значения параметров, при которых точность распознавания (число правильных ответов на обучающей выборке) является максимальной.

2. Алгоритмы голосования по тупиковым тестам. Сравнение распознаваемого объекта с эталонными осуществляется по различным «информативным» подмножествам признаков. В качестве подобных подсистем признаков используются тупиковые тесты (или аналоги тупиковых тестов для вещественнозначных признаков) различных случайных подтаблиц исходной таблицы эталонов.

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

4. Алгоритмы статистического взвешенного голосования.

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

5. Линейная машина.

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

6. Линейный дискриминант Фишера.

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

7. Метод к-ближайших соседей.

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

8. Нейросетевая модель распознавания с обратным распространением

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

9.Метод опорных векторов.

Метод построения нелинейной разделяющей поверхности с помощью опорных векторов. В новом признаковом пространстве (спрямляющем пространстве) строится разделяющая поверхность, близкая к линейной. Построение данной поверхности сводится к решению задачи квадратичного программирования.

10. Алгоритмы решения задач распознавания коллективами различных распознающих алгоритмов.

Задача распознавания решается в два этапа. Сначала применяются независимо различные алгоритмы Системы. Далее находится автоматически оптимальное коллективное решение с помощью специальных методов-«корректоров». В качестве корректирующих методов используются различные подходы.

11. Методы кластерного анализа (автоматической классификации или обучения без учителя).

Используются следующие известные подходы:

Алгоритмы иерархической группировки;

Кластеризация c критерием минимизации суммы квадратов отклонений;

Метод к-средних.

Возможно решение задачи классификации как при заданном, так и неизвестном числе классов.

12. Алгоритм построения коллективных решений задачи классификации.

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

Классификацией называется процедура, в которой объекты распределяются по группам (классам) в соответствии с численными значениями их переменных, характеризующими свойства этих объектов. Исходными данными для классификации является матрица X , в которой каждая строка представляет один объект, а каждый столбец – одну из переменных. Эта матрица называется исходным набором данных. Число объектов (строк в матрице X ) мы будем обозначать буквой I , а число переменных (строк в матрице X ) – буквой J . Число классов мы будем обозначать буквой K .

Классификацией называют не только саму процедуру распределения, но и ее результат. Употребляется также термин распознавание образов (pattern recognition) , который можно считать синонимом. В математической статистике классификацию часто называют дискриминацией .

Метод (алгоритм), которым проводят классификацию, называют классификатором . Классификатор переводит вектор признаков объекта x в целое число, 1, 2, … , соответствующее номеру класса, в который он помещает этот объект.

1.2. Обучение: с учителем и без

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

1.3. Типы классов

Классификация может делаться для разного числа классов .

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

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

Многоклассовая классификация часто сводится к последовательности: либо одноклассных (SIMCA), либо двухклассных (LDA) задач и является наиболее сложным случаем.

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

1.4. Проверка гипотез

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

Пусть имеется смесь слив и яблок, которую надо автоматически разделить. Очевидно, что в среднем сливы меньше яблок, поэтому задачу можно легко решить, используя подходящее сито. Анализ размеров объектов показал, что они хорошо описываются нормальными распределениями со следующими параметрами. Сливы: среднее 3, дисперсия 1.4. Яблоки: среднее 8, дисперсия 2.1. Таким образом, разумно будет выбрать сито диаметром 5. .

Рис. 1 Распределение объектов по размерам

С точки зрения математической статистики в этой задаче мы проверяем гипотезу о том, что среднее нормального распределения равно 3 (слива), против альтернативы 8 (яблоко). Проверка происходит по одному единственному наблюдению x . Критическое значение равно 5: если x <5 (область принятия гипотезы), то гипотеза принимается (объект – слива), если x >5, то принимается альтернатива (объект – яблоко).

1.5. Ошибки при классификации

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

α=1–Φ(5| 3, 1.4)=0.05 β=Φ(5| 8, 2.1)=0.01

Величинаα (ложное отклонение) называется ошибкой первого рода , а величинаβ (ложное принятие) – ошибкой второго рода. Если поменять местами гипотезу и альтернативу, то ошибка 1-го рода станет ошибкой 2-го рода, и наоборот.

Таким образом, при этом критическом уровне, 5% слив будет потеряно, и 1% яблок примешается к сливам. Если уменьшить критическое значение до 4, то примеси яблок практически не будет, зато потери слив достигнут 20%. Если же его увеличить до 6, то потери слив уменьшатся до 1%, но примесь яблок будет уже 5%. Понятно, что в этой задаче невозможно выбрать такое сито, которое правильно разделяло бы сливы и яблоки – всегда будут ошибки.

При проверке гипотезы (классификации) важно понимать, какую ошибку важнее минимизировать. Приведем два классических примера. В юриспруденции, при гипотезе "невиновен", руководствуясь презумпцией невиновности, необходимо минимизировать ошибку 1-го рода – вероятность ложного обвинения. В медицине, при гипотезе "здоров", необходимо минимизировать ошибку 2-го рода – вероятность не распознать болезнь.

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

1.6. Одноклассовая классификация

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

1.7. Обучение и проверка

Классификатор (помимо вектора переменных x ) зависит от свободных (неизвестных) параметров. Их надо подобрать так, чтобы минимизировать ошибку классификации. Подбор параметров называется обучением классификатора . Эта процедура проводится на обучающем наборе X c . Помимо обучения, необходима еще и проверка (валидация) классификатора. Для этого должен использоваться новый проверочный набор данных X t . Альтернативой валидации с помощью проверочного набора является проверка с помощью метода кросс-валидации .

1.8 . Проклятие размерности

В задачах классификации имеет место проблема, которая поэтически называется проклятием размерности (Curse of dimensionality). Суть дела в том, что при увеличении числа переменных J сложность задачи возрастает экспоненциально. Поэтому, даже относительно скромное их число (J >10) может доставить неприятности. Заметим, что в хемометрических приложениях (например, при анализе спектральных данных) может быть и 1000 и 10000 переменных.

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

2. Модельные данные

2.1. Пример

Для иллюстрации различных методов классификации мы будем использовать знаменитый пример – Ирисы Фишера , помещенный в рабочую книгу Iris.xls . Этот набор данных стал популярным после основополагающей работы , в которой Роберт Фишер предложил метод линейного дискриминационного анализа (LDA).

Набор данных включает три класса по 50 образцов в каждом. Каждый класс соответствует виду ириса: Iris Setosa (класс 1), Iris Versicolour (класс 2) и Iris Virginica (класс 3). .

Рис. 4 Ирисы Фишера (слева направо): Setosa , Versicolour и Virginica

В своей работе Р. Фишер использовал данные, собранные американским ботаником Э. Андерсоном, который измерил следующие характеристики цветков каждого из 150 образцов:

• Длина чашелистика (англ. sepal length);
• Ширина чашелистика (англ. sepal width);
• Длина лепестка (англ. petal length);
• Ширина лепестка (англ. petal width).

Все эти значения (в см) приведены в таблице на листе Data . Пытаясь понять, где у ирисов чашелистики, а где лепестки, естественно заглянуть в Wikipedia . Там сказано следующее.

"Соцветия ириса имеют форму веера и содержат один или более симметричных шестидольных цветков. Растут они на коротком стебельке. Три чашелистика направлены вниз. Они расширяются из узкого основания в обширное окончание, украшенное прожилками, линиями или точками. Три лепестка, которые иногда могут быть редуцированными, находятся в вертикальной позиции и частично скрыты основанием чашелистика. У более мелких ирисов вверх направлены все шесть доль. Чашелистики и лепестки отличаются друг от друга. Они объединены у основания в цветочный цилиндр, который лежит над завязью"

2.2. Данные

Исходный массив данных (3 класса по 50 образцов) был разбит на две части: обучающую и проверочную. В первое подмножество X c вошли по 40 первых образцов из каждого класса (всего 120 образцов), а во второе подмножество X t – оставшиеся в каждом классе 10 образцов (всего 30 образцов). Очевидно, что первую часть мы будем использовать для обучения разных классификаторов, а вторую часть – для их проверки. Обучающую выборку мы будем называть Training , а проверочную Test .

Классы называются в соответствие с их латинскими наименованиями: Setosa , Versicolor и Virginica , а переменные обозначаются двумя буквами, соответственно: SL – длина чашелистика (sepal length); SW – ширина чашелистика (sepal width), PL – длина лепестка (petal length), PW – ширина лепестка (petal width).

Рис. 5 Статистические характеристики обучающего и проверочного наборов

На Рис. 5 показаны основные статистические характеристики обучающего и проверочного наборов. Средние значения (m ) каждой переменной (SL, SW, PL и PW ) показаны точками, а их среднеквадратичные отклонения (s ) – отрезками. Цвет значков соответствует классу: красный – Setosa , голубой – Versicolor и зеленый – Virginica . Форма значка соответствует набору, которому принадлежит образец: круг – обучающий набор, треугольник – проверочный набор. Мы и в дальнейшем будем использовать эту систему обозначений на графиках.

Из Рис. 5 видно, что переменные в разных классах отличаются как по m , так и по s . Кроме того, мы можем заключить, что разбиение на обучающий и проверочный наборы было сделано правильно – соответствующие графики похожи.

2.3. Рабочая книга Iris.xls

Это пособие сопровождает файл Iris.xls – рабочая книга Excel

Эта книга включает в себя следующие листы:

2.4. Анализ данных методом главных компонент

Метод главных компонент (PCA) – один из главных инструментов, применяемых в хемометрике. В задачах классификации он используется с двумя целями. Во-первых, PCA понижает размерность данных, заменяя многочисленные переменные на небольшой набор (обычно 2-5) главных компонент. Во-вторых, он служит основой для построения многих методов классификации, например метода SIMCA, который рассмотрен .

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

Графики первых счетов приведены на Рис. 6.

Рис.6 Результаты PCA-анализа данных

Графики старших компонент (PC3 – PC4) приведены .

Для того, чтобы определить сколько главных компонент достаточно для моделирование данных, нужно исследовать график, на котором объясненная дисперсия (ERV) для обучающего и проверочного изображается в зависимости от числа главных компонент (PC).

Рис.7 Графики объясненной (ERV) дисперсии остатков для обучающего и проверочного наборов

Из Рис. 7 видно, что двух PC достаточно для моделирования данных – они объясняют 98% вариаций, как для обучающего, так и для проверочного наборов.

3. Классификация "с учителем"

3.1. Линейный дискриминатный анализ (LDA)

Линейный дискриминантный анализ или LDA (Linear Discriminant Analysis) это старейший из методов классификации, разработанный Р. Фишером, и опубликованный им в работе, которую мы уже упоминали . Метод предназначен для разделения на два класса.

Обучающий набор состоит из двух матриц X 1 и X 2 , в которых имеется по I 1 и I 2 строк (образцов). Число переменных (столбцов) одинаково и равно J . Исходные предположения состоят в следующем:

Классификационное правило в LDA очень простое – новый образец x относится к тому классу, к которому он ближе в метрике Махаланобиса

На практике неизвестные математические ожидания и ковариационная матрица заменяются их оценкам

Величины, стоящие в разных частях уравнения называются LDA-счетами , f 1 и f 2 . Образец относится к классу 1, если f 1 > f 2 , и, наоборот, к классу 2, если f 1 < f 2 .

Главной проблемой в методе LDA является обращение матрицы S . Если она вырождена, то метод использовать нельзя. Поэтому часто, перед применением LDA, исходные данные X заменяют на матрицу PCA-счетов T , которая уже не вырождена.

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

Т.к. LDA – это двухклассовый дискриминатор, то мы проведем классификацию в два шага. Сначала построим классификатор, который отделяет класс 1 (Setosa ) от всех других ирисов, объединенных в класс 23 (Versicolor + Virginica ). Затем построим второй классификатор, разделяющий классы 2 (Versicolor ) и 3 (Virginica ). Вычисления показаны на листе PCA-LDA .

Начнем с вычисления средних значений для всех классов по обучающим наборам. Нам надо вычислить средние значения по классу 1 (I 1 =40), объединенному классу 23 (I 23 =80), и классам 2 (I 2 =40) и 3 (I 3 =40). Значения приведены в массивах с локальными именами: m1c , m23c , m2c и m3c . .

Рис.8 Расчет средних значений

Вычислим ковариационные матрицы, составленные из классов 1 и 23, а также из классов 2 и 3 и обратим их. Результаты представлен в массивах с локальными именами Sinv123 и Sinv23 . Используя формулы вычислим все необходимые нам величины.

Рис.9 Расчет матриц ковариациий и других параметров LDA

Рис.14 Результат первой дискриминации между классами 1 и 23

На Рис. 14 и Рис. 15 показаны результаты LDA классификации.

Рис.15 Результат второй дискриминации между классами 2 и 3

Т.к. переменных теперь не две, а четыре, то графики, иллюстрирующие результаты, можно построить только в координатах LDA-счетов (f 1 , f 2) и дискриминирующая прямая - это биссектрисаf 1 = f 2 первого квадранта. Вторая дискриминации в обучающем наборе проведена с ошибками: два образца из класса 2 ошибочно отнесены к классу 3, и один образец из класса 3 ошибочно отнесен к классу 2. Эти точки показаны квадратными значками. В проверочном наборе ошибок нет

Недостатки LDA.

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

Не пригоден, если ковариационные матрицы классов различны.

Не позволяет менять уровни ошибок 1-го и 2-го родов.

Достоинства LDA:

Прост в применении.

3.2. Квадратичный дискриминатный анализ (QDA)

Квадратичный дискриминантный анализ, QDA (Quadratic Discriminant Analysis) является естественным обобщением метода LDA. QDA– многоклассный метод и он может использоваться для одновременной классификации нескольких классов k =1,…, K .

Обучающий набор состоит из K матриц X 1 ,…, X K , в которых имеется I 1 ,…, I K строк (образцов). Число переменных (столбцов) одинаково и равно J . Сохраняя первое предположение LDA в , откажемся от второго, т.е. допустим, что ковариационные матрицы в каждом классе различны. Тогда QDA-счета вычисляются по формуле

В этих формулах обозначает центрированную матрицу X k . Поверхность, разделяющая классы k и l определяется квадратичным уравнением

f k =f l

поэтому метод и называется квадратичным.

Рассмотрим, как метод QDA применяется к задаче классификации ирисов. Все расчеты приведены на листе QDA . Обучающий массив состоит из трех классов (с локальными именами X1c , X2c , X3c ), по 40 образцов в каждом. Для каждого массива вычисляются средние значения (локальные имена m1c , m2c и m3c ) .

Рис.16 Расчет средних значений

Потом вычисляются и обращаются ковариационные матрицы (локальные имена Sinv1 , Sinv2 и Sinv3 .

Рис.17 Расчет матриц ковариаций

Рис.18 Расчет QDA-счетов и принадлежности к классам

Результаты классификации представлены графиками QDA-счетов, показанными на Рис. 19 .

Рис.19 Результаты QDA классификации

Из этих рисунков (а также из анализа QDA-счетов) видно, что классификация в обучающем наборе проведена с ошибками: три образца из второго класса (Versicolor ) отнесены к третьему (Virginica ). В проверочном наборе ошибок нет.

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

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

Неявно использует предположение о нормальности распределения.

Не позволяет менять уровни ошибок 1-го и 2-го родов. .

3.3. PLS дискриминация (PLSDA )

Рис.20 Построение PLS2 регрессии

Заметим, что при получении PLS2-счетов для проверочного набора используется несколько другая формула.

Для вычисления прогнозных значений откликов Y hat применяется функция ТЕНДЕНЦИЯ ( TREND ) . В версии Excel 2003 эта функция иногда дает неправильный результат . Чтобы предотвратить эту ошибку, мы используем центрированные значения фиктивных откликов в обучающем наборе.

Рис.21 Расчет прогноза фиктивных откликов

Результаты PLSDA классификации на обучающем наборе таковы: 15 образцов из второго класса (Versicolor ) ошибочно отнесены к третьему классу (Virginica ), четыре образца из третьего класса (Virginica ) ошибочно отнесены ко второму классу (Versicolor ). В проверочном наборе тоже есть ошибки: один образец из первого класса ошибочно отнесен ко второму, и два образца из второго класса ошибочно отнесены к третьему классу. Таким образом, мы можем заключить, что PLSDA классификация удовлетворительных результатов не дала. Однако ситуацию можно значительно улучшить, если отказаться от плохого правила классификации () и продолжить вычисления дальше.

Рис.22 Результаты PLSDA классификации

Будем рассматривать найденные величины прогнозных значений фиктивных откликов Y hat не как окончательные, а как промежуточные данные, и применим к ним какой-нибудь другой метод классификации, например LDA. Напрямую это сделать нельзя, поскольку матрица Y c hat имеет ранг K –1, и матрицы ковариаций будут вырождены. Поэтому, до применения LDA, необходимо использовать метод главных компонент (PCA), так же, как мы делали в разделе . Соответствующие вычисления приведены на листе PLSDA-PCA-LDA .

Рис.23 Результаты PLSDA -PCA-LDA классификации

Этим способом мы получаем результат, в котором имеется всего одна ошибка в обучении: один образец из второго класса (Versicolor ) ошибочно отнесен к третьему классу (Virginica ). В проверочном наборе ошибок нет.

В этом методе PLS2-регрессия на матрицу фиктивных откликов с последующей PCA проекцией (PLSDA-PCA) является предварительной подготовкой исходных данных X , т.е. некоторым фильтром, выявляющим в этих данных новые характеристики, непосредственно связанные с различиями между классами. Здесь принципиально важно, что в PCA-LDA метод применяется к матрице предсказанных фиктивных откликов Y hat , не к матрице PLS2-счетов.

Недостатки PLSDA

Требует предварительного регрессионного анализа данных.

Результат зависит от выбора числа PC в PLS 2регрессии.

Достоинства PLSDA

Не использует вид распределения.

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

(12 )

где h 0 и v 0 – это средние значения величин h и v , а N h , и N v – это числа степеней свободы соответственно для h и v .

Используя обучающий набор X c =(x 1 ,…x I ) t , можно найти I значений размахов h 1 ,….,h I и отклонений v 1 ,….,v I . По ним можно оценить соответствующие средние значения

(13 )

Первым делом применим PCA, используя в качестве обучающего набора матрицу X1c (часть матрицы X c относящуюся к классу 1), а в качестве проверочного набора всю матрицу Xt . Также как и в других методах, мы используем две PCA компоненты.

Рис.25 Вычисление счетов и нагрузок PCA

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

Затем вычисляем значения размахов h по формуле для обучающего и проверочного наборов. .

Рис.26 Вычисление размахов

Рис.27 Вычисление отклонений

Вычисление отклонений для проверочного набора проводится по аналогичной формуле с заменой X1c на Xt , и Tc на Tt.

Рис.30 Вычисление числа степеней свободы

На Рис. 30 показаны результаты классификации. График для проверочного набора модифицирован так, чтобы показать на нем все имеющиеся образцы. Для этого оси координат трансформированы степенным преобразованием x 1/p , p =3.

Все образцы обучающего набора классифицированы правильно. В проверочном наборе один образец из первого класса (Setosa ) не распознан.

Аналогично делается классификация для других классов. При этом для класса 2 (лист SIMCA_2 ) обучающей является подматрица X2c , а для класса 3 (лист SIMCA_3 ) – подматрица X3c . Соответственно меняются и средние значения mean2

Недостатки SIMCA

Требует предварительного анализа данных методом PCA .

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

Чувствителен к выбросам., однако они легко распознаются самим методом.

Плохо работает для малого числа образцов в обучающем наборе.

Достоинства SIMCA

4. Классификация без учителя

4.1. Опять PCA

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

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

Рис.35 . PCA анализ обучающего набора

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

Удалим все эти образцы из обучающего набора и применим PCA к оставшимся образцам. На графике PC1-PC2 счетов, показанных на Рис. 36 можно (при большом воображении) различить два кластера, показанные эллипсами. Но уже на графике старших счетов PC1-PC3, мы ничего похожего на классы не видим.

Рис.36 . PCA анализ укороченного обучающего набора

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

4.2. Кластеризация с помощью K -средних (kMeans )

Существует большой класс методов, выполняющих так называемую кластеризацию . Кластеризация состоит в том, чтобы разделить образцы на подмножества (называемые кластерами) так, чтобы все образцы в одном кластере были в каком-то смысле похожи друг на друга. Оценка схожести образцов x 1 и x 2 обычно основана на анализе расстояний d (x 1 , x 2) между ними. Для измерения расстояний чаще всего используют Эвклидову метрику.

Самым простым (и поэтому – популярным) является метод K -средних (K -means ). Этот метод разбивает исходный набор образцов на заранее известное число K кластеров. При этом каждый образец xi обязательно принадлежит к одному из этих кластеров S k ., k =1,…, K . Каждый кластер k характеризуется своим цетнроидом m k – точкой, являющейся центром масс всех образцов кластера. Метод K-средних – это итерационный алгоритм, в котором на каждом шаге выполняются следующие операции.

1. Определяются расстояния от всех образцов до центроидов d (x j , m k ), j =1,…J ; k =1,…,K .

2. Образцы относятся к кластерам в соответствии с тем, какой из центроидов оказался ближе.

3. По этому новому разбиению вычисляются центроиды m k для каждого из кластеров

где J k – это число образцов в кластере S k .

Операции 1-3 повторяются до сходимости.

Для инициализации алгоритма нужно задать исходные значения всех центроидов m k . Это можно сделать произвольно, например, положить их равными первым K образцам.

m 1 = x 1 , m 2 = x 2 ,…., m K = x K

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

Рис.40 . Расчет новых значений центроидов

Чтобы замкнуть итерационную последовательность надо скопировать значения из области KMeansNew и вставить их (как значения!) в область KMeans . И это надо повторять столько раз, сколько потребуется, пока все значения kMeans – kMeansNew не станут равными нулю. На листе kMeans имеется кнопка Calculate . Она запускает простейший VBA макрос , который копирует содержание области KMeansNew и вставляет значения в область KMeans . Эта операция повторяется столько раз, сколько указано в клетке P2 . Тем самым реализуется заданное число итераций.

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

Если выбрать в качестве начального приближения первые две точки: ve01 и ve02 , то получится результат, представленный на Рис. 41. Левый график показывает, как образцы распределялись в начале работы алгоритма, а правый график – как они распределились в итоге.

Рис.41 . Кластеризация методом K-средних. Начало и конец работы алгоритма.
Начальная точка – первые два образца

На Рис. 42 показан результат кластеризации, который получается, если в качестве начального приближения берутся последние два образца: vi39 и vi40 . Во-первых, видно, что кластеры поменялись местами. Во-вторых, заметно, что некоторые точки ушли в другие кластеры.

Рис.42 . Кластеризация методом K-средних. Начало и конец работы алгоритма.
Начальная точка – последние два образца

Для того, чтобы понять какое решение лучше, используют целевую функцию

которая должна быть минимальна. В первом случае S =52.830, а во втором S =52.797. Таким образом, второе решение предпочтительнее.

Естественно отождествить первый кластер с классом 2 (Versicolor ), а второй кластер с классом 3 (Virginica ). Тогда полученные результаты можно интерпретировать так: два образца класса 2 идентифицированы неправильно, а среди образцов класса 3 одиннадцать неверно отнесены к классу 2.

Метод K-средних имеет несколько недостатков.

Число кластеров K неизвестно и как его найти непонятно. Можно только наращивать это значения и исследовать результаты.

Результат зависит от начального выбора центроидов. Нужно перебирать разные варианты.

Результат зависит от выбора метрики.

Заключение

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

Несколько методов классификации достойны специального изучения. Это методы опорных векторов и искусственных нейронных сетей. Им будут посвящены отдельные пособия

В прошлом году компания «Авито» провела целый ряд конкурсов. В том числе - конкурс по распознаванию марок автомобилей, победитель которого, Евгений Нижибицкий, рассказал на тренировке о своём решении.

Постановка задачи . По изображениям автомобилей необходимо определить марку и модель. Метрикой служила точность предсказаний, то есть доля правильных ответов. Выборка состояла из трёх частей: первая часть была доступна для обучения изначально, вторая была дана позже, а на третьей требовалось показать финальные предсказания.

Вычислительные ресурсы . Я воспользовался домашним компьютером, который обогревал мою комнату всё это время, и предоставленными на работе серверами.

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

Заметим, что наилучшее качество достигается на архитектурах и .

Fine-tuning сетей . Обучать глубокую нейронную сеть с нуля - довольно затратное по времени занятие, к тому же не всегда эффективное с точки зрения результата. Поэтому часто используется техника дообучения сетей: берётся уже обученная на ImageNet сеть, последний слой заменяется на слой с нужным количеством классов, а потом продолжается настройка сети с низким темпом обучения, но уже на данных из конкурса. Такая схема позволяет обучить сеть быстрее и с более высоким качеством.

Первый подход к дообучению GoogLeNet показал примерно 92% точности при валидации.

Предсказания на кропах . Используя нейронную сеть для предсказания на тестовой выборке, можно улучшить качество. Для этого следует выреза́ть фрагменты подходящего размера в разных местах исходной картинки, после чего усреднять результаты. Кроп 1x10 означает, что взят центр изображения, четыре угла, а потом всё то же самое, но отражённое по горизонтали. Как видно, качество возрастает, однако время предсказания увеличивается.

Валидация результатов . После появления выдачи второй части выборки я разбил выборку на несколько частей. Все дальнейшие результаты показаны на этом разбиении.

ResNet-34 Torch . Можно воспользоваться готовым репозиторием авторов архитектуры, но, чтобы получить предсказания на тесте в нужном формате, приходится исправлять некоторые скрипты. Кроме того, нужно решать проблемы большого потребления памяти дампами. Точность при валидации - около 95%.

Inception-v3 TensorFlow . Тут тоже использовалась готовая реализация, но была изменена предобработка изображений, а также ограничена обрезка картинок при генерации батча. Итог - почти 96% точности.

Ансамбль моделей . В итоге получилось две модели ResNet и две модели Inception-v3. Какое качество при валидации можно получить, смешивая модели? Вероятности классов усреднялись с помощью геометрического среднего. Веса (в данном случае - степени) подбирались на отложенной выборке.

Результаты . Обучение ResNet на GTX 980 занимало 60 часов, а Inception-v3 на TitanX - 48 часов. За время конкурса удалось опробовать новые фреймворки с новыми архитектурами.

Задача классификации клиентов банка

Ссылка на Kaggle .

Станислав Семёнов рассказывает, как он и другие участники топа Kaggle объединились и заняли призовое место в соревновании по классификации заявок клиентов крупного банка - BNP Paribas .

Постановка задачи . По обфусцированным данных из заявок на страхование необходимо предсказать, можно ли без дополнительных ручных проверок подтвердить запрос. Для банка это процесс автоматизации обработки заявок, а для аналитиков данных - просто задача машинного обучения по бинарной классификации. Имеется около 230 тысяч объектов и 130 признаков. Метрика - LogLoss . Стоит отметить, что команда-победитель расшифровала данные, что помогло им выиграть соревнование.

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

Почему так? Дело в том, что на этапе анонимизации и зашумления данных ко всем значениям прибавлялся случайный шум, а потом проводилось масштабирование на отрезок от 0 до 20. Обратное преобразование было проведено в два шага: сначала значения округлялись до некоторого знака после запятой, а потом подбирался деноминатор. Требовалось ли это, если дерево всё равно подбирает порог при разбиении? Да, после обратного преобразования разности переменных начинают нести больший смысл, а для категориальных переменных появляется возможность провести one-hot кодирование.

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

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

Кодирование категориальных переменных . Бросилось в глаза то, что некая переменная V22 имеет большое число значений, но при этом, если взять подвыборку по некоторому значению, число уровней (различных значений) других переменных заметно уменьшается. В том числе имеет место хорошая корреляция с целевой переменной. Что можно сделать? Самое простое решение - построить для каждого значения V22 отдельную модель, но это всё равно что в первом сплите дерева сделать разбиение по всем значениям переменной.

Есть другой способ использования полученной информации - кодирование средним значением целевой переменной. Другими словами, каждое значение категориальной переменной заменяется средним значением таргета по объектам, у которых данный признак принимает то же самое значение. Произвести такое кодирование напрямую для всего обучающего множества нельзя: в процессе мы неявно внесём в признаки информацию о целевой переменной. Речь идёт об информации, которую почти любая модель обязательно обнаружит.

Поэтому такие статистики считают по фолдам. Вот пример:

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

Останутся ли проблемы ещё с чем-нибудь? Да - с редко встречающимися категориями и с кросс-валидацией.

Редко встречающиеся категории . Допустим, некоторая категория встретилась всего несколько раз и соответствующие объекты относятся к классу 0. Тогда среднее значение целевой переменной тоже будет нулевым. Однако на тестовой выборке может возникнуть совсем другая ситуация. Решение - сглаженное среднее (или smoothed likelihood), которое вычисляется по следующей формуле:

Здесь global mean - среднее значение целевой переменной по всей выборке, nrows - то, сколько раз встретилось конкретное значение категориальной переменной, alpha - параметр регуляризации (например, 10). Теперь, если некоторое значение встречается редко, больший вес будет иметь глобальное среднее, а если достаточно часто, результат окажется близким к начальному среднему по категории. Кстати, эта формула позволяет обрабатывать и неизвестные ранее значения категориальной переменной.

Кросс-валидация . Допустим, мы посчитали все сглаженные средние для категориальных переменных по другим фолдам. Можем ли мы оценить качество модели по стандартной кросс-валидации k-fold? Нет. Давайте рассмотрим пример.

К примеру, мы хотим оценить модель на третьем фолде. Мы обучаем модель на первых двух фолдах, но в них есть новая переменная со средним значением целевой переменной, при подсчёте которой мы уже использовали третий тестовый фолд. Это не позволяет нам корректно оценивать результаты, но возникшая проблема решается подсчётом статистик по фолдам внутри фолдов. Снова обратимся к примеру:

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

Построение признаков . Мы использовали не только уже упомянутые сглаженные средние значения целевой переменной, но и weights of evidence. Это почти то же самое, но с логарифмическим преобразованием. Кроме того, полезными оказались фичи вида разности количества объектов положительного и отрицательного классов в группе без какой-либо нормировки. Интуиция тут следующая: масштаб показывает степень уверенности в классе, но что делать с количественными признаками? Ведь если их обработать похожим образом, то все значения «забьются» регуляризацией глобальным средним. Одним из вариантов является разделение значений на бины, которые потом считаются отдельными категориями. Другой способ заключается просто в построении некой линейной модели на одном признаке с тем же таргетом. Всего получилось около двух тысяч признаков из 80 отфильтрованных.

Стекинг и блендинг . Как и в большинстве соревнований, важной частью решения является стекинг моделей. Если кратко, то суть стекинга в том, что мы передаём предсказания одной модели как признак в другую модель. Однако важно в очередной раз не переобучиться. Давайте просто разберём пример:

Взято из блога Александра Дьяконова

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

На первом уровне у команды было 200-250 различных моделей, на втором - ещё 20-30, на третьем - ещё несколько. Результат - блендинг, то есть смешивание предсказаний различных моделей. Использовались разнообразные алгоритмы: градиентные бустинги с разными параметрами, случайные леса, нейронные сети. Главная идея - применить максимально разнообразные модели с различными параметрами, даже если они дают не самое высокое качество.

Работа в команде . Обычно участники объединяются в команды перед завершением конкурса, когда у каждого уже имеются свои наработки. Мы объединились в команду с другими «кэглерами» ещё в самом начале. У каждого участника команды была папка в общем облаке, где размещались датасеты и скрипты. Общую процедуру кросс-валидации утвердили заранее, чтобы можно было сравнивать между собой. Роли распределялись следующим образом: я придумывал новые признаки, второй участник строил модели, третий - отбирал их, а четвёртый управлял всем процессом.

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

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

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

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

Задача распознавания категории объявления

Ссылка на DataRing .

Это ещё один конкурс «Авито». Он проходил в несколько этапов, первый из которых (как, впрочем, ещё и третий) выиграл Артур Кузин .

Постановка задачи . По фотографиям из объявления необходимо определить категорию. Каждому объявлению соответствовало от одного до пяти изображений. Метрика учитывала совпадения категорий на разных уровнях иерархии - от общих к более узким (последний уровень содержит 194 категории). Всего в обучающей выборке был почти миллион изображений, что близко к размеру ImageNet.

Сложности распознавания . Казалось бы, надо всего лишь научиться отличать телевизор от машины, а машину от обуви. Но, например, есть категория «британские кошки», а есть «другие кошки», и среди них встречаются очень похожие изображения - хотя отличить их друг от друга всё-таки можно. А как насчёт шин, дисков и колёс? Тут и человек не справится. Указанные сложности - причина появления некоторого предела результатов всех участников.

Ресурсы и фреймворк . У меня в распоряжении оказались три компьютера с мощными видеокартами: домашний, предоставленный лабораторией в МФТИ и компьютер на работе. Поэтому можно было (и приходилось) обучать по несколько сетей одновременно. В качестве основного фреймворка обучения нейронных сетей был выбран MXNet , созданный теми же ребятами, которые написали всем известный XGBoost . Одно это послужило поводом довериться их новому продукту. Преимущество MXNet в том, что прямо из коробки доступен эффективный итератор со штатной аугментацией, которой достаточно для большинства задач.

Архитектуры сетей . Опыт участия в одном из прошлых соревнований показал, что лучшее качество показывают архитектуры серии Inception. Их я и задействовал здесь. В GoogLeNet была добавлена , поскольку она ускоряла обучение модели. Также использовались архитектуры Inception-v3 и Inception BN из библиотеки моделей Model Zoo , в которые был добавлен дропаут перед последним полносвязным слоем. Из-за технических проблем не удавалось обучать сеть с помощью стохастического градиентного спуска, поэтому в качестве оптимизатора использовался Adam.

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

Точность и скорость обучения . Сначала я разделил выборку на три части, но потом отказался от одного из этапов валидации для смешивания моделей. Поэтому впоследствии вторая часть выборки была добавлена в обучающее множество, что улучшило качество сетей. Кроме того, GoogLeNet изначально обучался на Titan Black, у которого вдвое меньше памяти по сравнению с Titan X. Так что эта сеть была дообучена с большим размером батча, и её точность возросла. Если посмотреть на время обучения сетей, можно сделать вывод, что в условиях ограниченных сроков не стоит использовать Inception-v3, поскольку с двумя другими архитектурами обучение идёт заметно быстрее. Причина в числе параметров. Быстрее всех учится Inception BN.

Построение предсказаний .

Как и Евгений в конкурсе с марками автомобилей, Артур использовал предсказания на кропах - но не на 10 участках, а на 24. Участками послужили углы, их отражения, центр, повороты центральных частей и ещё десять случайных.

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

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

Обучение с нуля vs. fine-tuning . Уже после завершения конкурса выяснилось, что несмотря на большой размер выборки стоило обучать сеть не с нуля, а при помощи предобученной сети. Этот подход демонстрирует более высокие результаты.

Задача обучения с подкреплением

Соревнование Black Box Challenge, о котором , было не совсем похоже на обычный «кэгл». Дело в том, что для решения было недостаточно разметить некоторую «тестовую» выборку. Требовалось запрограммировать и загрузить в систему код «агента», который помещался в неизвестную участнику среду и самостоятельно принимал в ней решения. Такие задачи относятся к области обучения с подкреплением - reinforcement learning.

О подходах к решению рассказал Михаил Павлов из компании 5vision. В конкурсе он занял второе место.

Постановка задачи . Для среды с неизвестными правилами нужно было написать «агента», который взаимодействовал бы с указанной средой. Схематично это некий мозг, который получает от чёрного ящика информацию о состоянии и награде, принимает решение о действии, после чего получает новое состояние и награду за совершённое действие. Действия повторяются друг за другом в течение игры. Текущее состояние описывается вектором из 36 чисел. Агент может совершить четыре действия. Цель - максимизировать сумму наград за всю игру.

Анализ среды . Изучение распределения переменных состояния среды показало, что первые 35 компонент не зависят от выбранного действия и только 36-я компонента меняется в зависимости от него. При этом разные действия влияли по-разному: некоторые увеличивали или уменьшали, некоторые никак не меняли. Но нельзя сказать, что вся среда зависит от одной компоненты: в ней могут быть и некие скрытые переменные. Кроме того, эксперимент показал, что если совершать более 100 одинаковых действий подряд, то награда становится отрицательной. Так что стратегии вида «совершать только одно действие» отпадали сразу. Кто-то из участников соревнования заметил, что награда пропорциональна всё той же 36-й компоненте. На форуме прозвучало предположение, что чёрный ящик имитирует финансовый рынок, где портфелем является 36-я компонента, а действиями - покупка, продажа и решение ничего не делать. Эти варианты соотносились с изменением портфеля, а смысл одного действия понятен не был.

Q-learning . Во время участия основной целью было попробовать различные техники обучения с подкреплением. Одним из самых простых и известных методов является q-learning. Его суть в попытке построить функцию Q, которая зависит от состояния и выбранного действия. Q оценивает, насколько «хорошо» выбирать конкретное действие в конкретном состоянии. Понятие «хорошо» включает в себя награду, которую мы получим не только сейчас, но и будущем. Обучение такой функции происходит итеративно. Во время каждой итерации мы пытаемся приблизить функцию к самой себе на следующем шаге игры с учётом награды, полученной сейчас. Подробнее можно почитать . Применение q-learning предполагает работу с полностью наблюдаемыми марковскими процессами (другими словами, в текущем состоянии должна содержаться вся информация от среды). Несмотря на то, что среда, по заявлению организаторов, не удовлетворяла этому требованию, применять q-learning можно было достаточно успешно.

Адаптация к black box . Опытным путём было установлено, что для среды лучше всего подходил n-step q-learning, где использовалась награда не за одно последнее действие, а за n действий вперёд. Среда позволяла сохранять текущее состояние и откатываться к нему, что облегчало сбор выборки - можно было из одного состояния попробовать совершить каждое действие, а не какое-то одно. В самом начале обучения, когда q-функция ещё не умела оценивать действия, использовалась стратегия «совершать действие 3». Предполагалось, что оно ничего не меняло и можно было начать обучаться на данных без шума.

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

Модели . В решении использовались три регрессии (каждая по одному разу в расчёте на каждое действие) и две нейронных сети. Были добавлены некоторые квадратичные признаки и взаимодействия. Итоговая модель представляет собой смесь всех пяти моделей (пяти Q-функций) с равными весами. Кроме того, использовалось онлайн-дообучение: в процессе тестирования веса́ старых регрессий подмешивались к новым весам, полученным на тестовой выборке. Это делалось только для регрессий, поскольку их решения можно выписывать аналитически и пересчитывать достаточно быстро.

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

Итоги . Команда 5vision заняла второе место, но с совсем небольшим отрывом от обладателей «бронзы».

Итак, зачем нужно участвовать в соревнованиях по анализу данных?

• Призы. Успешное выступление в большинстве соревнований вознаграждается денежными призами или другими ценными подарками. На Kaggle за семь лет разыграли более семи миллионов долларов.
• Карьера. Иногда призовое место .
• Опыт. Это, конечно, самое главное. Можно изучить новую область и начать решать задачи, с которыми вы раньше не сталкивались.

Сейчас тренировки по машинному обучению проводятся по субботам каждую вторую неделю. Место проведения - московский офис Яндекса, стандартное число гостей (гости плюс яндексоиды) - 60-80 человек. Главным свойством тренировок служит их злободневность: всякий раз разбирается конкурс, завершившийся одну-две недели назад. Это мешает всё точно спланировать, но зато конкурс ещё свеж в памяти и в зале собирается много людей, попробовавших в нём свои силы. Курирует тренировки Эмиль Каюмов, который, кстати, помог с написанием этого поста.

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

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

Как правильно провести анализ и классификацию данных? Зачем нужны графики и диаграммы?

Урок-практикум

Цель работы . Научиться проводить классификацию и анализировать данные, полученные из текста.

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

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

Иван Крамской. Д. И. Менделеев

Чьими портретами ученых-систематизаторов вы бы дополнили этот ряд?

ПОРТРЕТ ШАРОВОЙ МОЛНИИ . «Портрет загадочного феномена природы - шаровой молнии выполнили специалисты главной геофизической обсерватории им. А. И. Воейкова, воспользовавшись услугами ЭВМ и., методами криминалистики. «Фоторобот» таинственной незнакомки был составлен на основе данных, опубликованных в печати за три столетия, итогов исследовательских опросов и сообщений очевидцев разных стран.

Какие же из своих секретов сообщил ученым парящий сгусток энергии?

Замечают его большей частью во время гроз. Во все времена встречались четыре формы шаровой молнии: сфера, овал, диск, стержень. Порождение атмосферного электричества, естественно, большей частью возникало в воздухе. Однако, по данным американских опросов, с равной частотой молнию можно увидеть и осевшей на различных предметах - телеграфных столбах, деревьях, домах. Размеры удивительной спутницы гроз от 15 до 40 см. Цвет? Три четверти очевидцев следили за сверкающими шарами красного, желтого и розового цвета.

Жизнь сгустка электрической плазмы по истине мотыльковая, как правило в пределах пяти секунд. Дольше этого срока, но не более 30 с, ее видело до 36 % очевидцев. Почти всегда и кончина ее была одинаковой - она самопроизвольно взрывалась, иногда натыкаясь на различные препятствия. «Коллективные портреты», сделанные наблюдателями разных времен и народов, совпали».

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

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

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

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

Представим разрозненный набор данных в виде таблицы, затем в виде графика и диаграммы (рис. 5, 6). Найдите закономерности в распределении температуры. Ответьте на вопросы:

1. Каковы особенности распределения температур по месяцам в разных городах? Чем различаются эти распределения?
2. В чем причина процессов, которые приводят к такому распределению?
3. Помогла ли вам выполнить задание систематизация материала с помощью графика, диаграммы?

Среднемесячные дневные температуры за один год для Санкт-Петербурга и Сочи

Рис. 5. График хода среднемесячных дневных температур за один год для Санкт-Петербурга и Сочи

Рис. 6. Диаграмма: среднемесячные дневные температуры за один год в городах Санкт-Петербург и Сочи

Важными ступенями к овладению методами научного познания являются:

1. Логический анализ текста.
2. Составление плана, схем, выделение структуры материала.
3. Конспектирование текста или написание тезисов.
4. Выделение нового знания и его использование в дискуссиях, выступлениях, в решении новых задач, проблем.

Литература для дополнительного чтения

1. Эйнштейн А. Без формул / А. Эйнштейн; сост. К. Кедров; пер. с англ. - М.: Мысль. 2003.
2. Методология науки и научный прогресс. - Новосибирск: Наука. 1981.
3. Фейрабенд П. Избранные труды по методологии науки / П. Фейрабенд. - М.: Прогресс, 1986