Метод комплексной оценки моделей данных для автоматизации машинного обучения без учителя тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Баймуратов Ильдар Раисович

• Баймуратов Ильдар Раисович
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Баймуратов Ильдар Раисович

Содержание

Реферат

Synopsis

Введение

Глава 1. Анализ проблемы автоматизации обучения без учителя

1.1. Ограничения автоматизации обучения без учителя

1.2. Анализ формальных моделей машинного обучения

1.2.1. Теория вероятностно приблизительно корректного обучения

1.2.2. Теория оккамовского обучения

1.2.3. Применимость формальных моделей к обучению без учителя

1.2.4. Оптимальная модель обучения

1.3. Анализ методов оценки моделей обучения

1.3.1. Оценка признакового пространства

1.3.2. Оценка регрессионных моделей

1.3.3. Оценка кластеризации

1.3.4. Меры информативности

1.4. Анализ методов автоматизации машинного обучения

1.4.1. Методы оптимизации гиперпараметров

1.4.2. Системы автоматизированного машинного обучения

1.4.3. Критерии принятия решений в условиях неопределенности

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

1.6. Итог

Глава 2. Формальная модель обучения без учителя

2.1. Теоретико-множественная модель обучения

2.1.1. Структура множества входных данных

2.1.2. Структура множества выходных значений

2.1.3. Структура объяснительной модели

2.2. Формальный анализ обучения без учителя

2.3. Формальный анализ мер информативности

2.3.1. Комбинаторная информация

2.3.2. Колмогоровская информация

2.3.3. Информационная энтропия

2.4. Итог

Глава 3. Методы оптимизации обучения без учителя

3.1. Метод комплексной оценки информативности моделей обучения

без учителя

3.1.1. Оценка информативности разбиения

3.1.2. Оценка информативности факторизации

3.1.3. Оценка информативности композиции

3.2. Метод автоматизации обучения без учителя

3.2.1. Автоматизация на основе критерия Лапласа

3.2.2. Автоматизация на основе критерия Байеса

3.3. Итог

Глава 4. Апробация методов оптимизации обучения без учителя

4.1. Апробация метода оценки информативности моделей обучения

без учителя

4.2. Апробация метода автоматизации обучения без учителя

4.3. Итог

Заключение

Список рисунков

Список таблиц

Список литературы

Приложение Л

Приложение B

Публикации

Реферат

Введение диссертации (часть автореферата) на тему «Метод комплексной оценки моделей данных для автоматизации машинного обучения без учителя»

Общая характеристика работы

На сегодняшний день область знаний, к которой применимы такие понятия как наука о данных (data science), анализ данных, машинное обучение и т.д. активно развивается. С каждым днем, с одной стороны, растут объемы собираемых данных, с другой, появляются новые алгоритмы, а существующие усложняются. В следствие этого непрерывно растет потребность в труде квалифицированных специалистов, что рано или поздно приведет к их дефициту [52]. Решением этой проблемы могут стать системы автоматизированного машинного обучения без учителя, которые полностью не зависят от экспертных оценок. Однако реализация этого решения в свою очередь также влечет ряд проблем.

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

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

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

— проанализировать существующие решения выявленных проблем автоматизации обучения без учителя;

— разработать формальную модель обучения без учителя;

— разработать метод оценки результатов применения различных алгоритмов машинного обучения без учителя;

— разработать вычислительно эффективный метод автоматизации машинного обучения без учителя;

— произвести экспериментальную проверку разработанных методов.

Объектом исследования являются методы машинного обучения без учителя.

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

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

— методы машинного обучения;

— методы оценки моделей данных;

— методы автоматизации машинного обучения.

Новые научные результаты выносимые на защиту:

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

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

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

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

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

Достоверность изложенных в работе результатов подтверждается корректностью используемых апробированных подходов и непротиворечивостью полученных результатов.

Апробация работы. Основные результаты работы докладывались на международных и всероссийских научных конференциях и семинарах: Inter-national Conference on Control, Artificial Intelligence, Robotics & Optimization (Прага,

2017), 22nd Conference of Open Innovations Association FRUCT (Ювяскюля,

2018), 24th Conference of Open Innovations Association FRUCT (Москва, 2019), The 20th International Conference on Computational Science and its Applications (Санкт-Петербург, 2019).

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

Публикации. Основные результаты по теме диссертации изложены в 6 печатных изданиях [13] [11] [12] [107] [95] [9], 5 из которых изданы в журналах и сборниках докладов конференций, индексируемых в Scopus или Web of Science.

Объем и структура работы. Диссертация состоит из введения, четырех глав и заключения.

Содержание работы

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

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

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

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

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

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

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

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

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

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

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

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

оккамовского обучения была разработана общая формальная модель машинного обучения. Она включает в себя

— множество входных данных X;

— множество выходных значений Y;

— множество факторизаций Fact : X ^ X;

— множество композиций Comp : X ^ Y;

— множество разбиений Part : Y ^ Y;

— набор критериев Cpact : Fact ^ R, ссотр : Comp ^ R, cpart : Part ^ R.

На основе этой модели предложено формальное определение модели обучения 1т

Im =< fact, comp, part >

Отображения Fact, Comp, Part также в свою очередь обладают определенной структурой. В результате анализа и обобщения различных моделей обучения были выявлены следующие структуры:

— Fact : X ^ Х1 х ... х Хп

— Comp : F ^ Fi о ... о Fi

— Part : Y ^ Yi U ... U Yk

Следовательно, более подробное представление модели обучения имеет вид

< fact, comp, part >= Х1 х ... х Хп Yi U ... U

Интерпретируя полученные структуры на языке машинного обучения, Факто-ризациям соответствуют различные признаковые пространства, композициям — объяснительные модели, разбиениям — классификации и кластеризации.

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

А : Fact х Comp х Part ^< fact, comp, part >

Формализованы модели ВПК обучения

comp = argmincomp eCompsize(comp) и оккамовского обучения.

comp = argmiricompeCompL{comp, S) Формализованы задачи обучения с учителем

< fact, Comp,part >

и без учителя.

< fact, Comp, Part >

Далее, предложено формальное определение оптимальной модели обучения

Im* =< f act*, comp*, pari* >= <

fact* = argmaxfacteFactR(cFact(fact)) comp* = argmaXcompeCompR(ccomp(comp)) pari* = argmaxPartePartR{cpart{part))

Установлено, что оптимальная модель ВПК обучения выразима в разработанном формализме и подпадает под общее определение оптимальной модели обучения

1 к •

argmirij L(A3X, Dl^, Dltest) е агдтахЫеьм R(C (Im))

l=1

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

— Информация Хартли 1одтЫ е Сраа,

— Колмогоровская сложность К(у\х) е Ссотр

— Информация Шэннона Н(У) е СРаг^

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

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

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

Dkl(р(Х)\\q(X)) = £ Ш logw \Х)\

г

где q(X) — исходное распределение, р(Х) — конечное распределение, X — случайная величина, Xi — значение случайной величины. Для краткости будем обозначать величину Dkl(p(X)\\q(X)) как Н(X).

Применяя базовый метод оценки информативности к отображениям Fact, Comp, получаем систему мер

- cFact : HF (X ) = E, Щ log \ x \\ X, \

- CCornp : He (F) i \FT l0g iF\ \\

- cPart : Hp (Y) = log \У \ \ \

Однако эти меры все еще не являются устойчивыми. Для примера на Рисунке 1 представлен график зависимости величины Hp (Y) от количества кластеров к = 2,..., 49 при кластеризации сгенерированного набора данных размера п = 50 алгоритмом k-means. Как видно, величина достигает максимума при минимальном количестве кластеров к = 2. Таким образом, необходимо модифицировать базовый метод оценки информативности для достижения устойчивости.

Рисунок 1 - Значение Н(Y) для k-means при п = 50 и к = 2,..., 49

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

- d-кратная факторизация factd(X) е Factd(X)

- /-местная композиция comp1 ( F) е Compl(F)

- ^-частное разбиение partк (Y) е Partk (Y)

Затем на их основе задаются соответствующие распределения

- Р(fact.d(X)) = jj^

- P{comp1 (F)) = ]cJlHx),

- P(part"(Y)) = ip^y,,

и определяется ожидаемая информативность

- HF(Factd(X)) = E, HF(factd(X))

- Hc(Comp1 (F)) = Y,i \Comp1 (F)\ He(Comp\(F))

- Hp (Partk (Y) ) = E, ipdra Hp (partk (Y) ) Наконец, определяется устойчивая информативность

- RHf(factd(X)) = HF(factf(X)) - HF(Factd(X))

- RHC(comp1 (F)) = Hc(comp\(F)) - Hc(Comp1 (F))

- RHP(partk(Y)) = Hp(partf (Y)) - HP(Partk(Y))

Таким образом, предлагаемый метод комплексной оценки информативности моделей обучения заключается в нахождении оптимальной модели обучения 1т* путем максимизации устойчивых мер информативности

fact* = argmaXiRHF (factd(X)) Im* = < comp* = argmaxiRHC(compi(F)) part* = argmaxiRHP (partk (Y))

Разработанный метод обладает следующими преимуществами:

- полнота оценки;

- усточивость к недообучению и переобучению;

- независимость от модели обучения.

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

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

Адаптируя критерий Лапласа к проблеме оптимизации гиперпараметров, получаем определение оптимального значения гиперпараметра по Лапласу h*

h* = — c(lmj (hi))

i n

Критерий Лапласа предполагает равномерное вероятностное распределение. В соответствии с этим определяются распределения

- Р (Factd' (X )) = Ei jF-Jmi

- P(Comp'(F)) = E.ic^mt

- P(Partx-(Y)) = Y,,

Подставляя в критерий Лапласа распределения Р(Factdi (X)), Р(Compli (F)) и Р(Partki (Y)) в качестве распределения ^, базовые меры информативности Hp(X), Не(F) и Hp(Y) в качестве критерия c(lmj(hi)) и параметризируя значения к, I и d, получаем следующие критерии:

- оптимальная по Лапласу кратность фаткоризации

d* = агдтах{Р (Factd (X ))HF (Factd (X))

- оптимальная по Лапласу длина композиции

= argmaXiP (Compli (F ))HC (Compli (F))

- оптимальное по Лапласу количество частей разбиения

к* = argmaXiP (Par tki (Y ))HP (Par tki (Y))

На Рисунке 2 представлен расчет величины Р(Partki(Y))Нр(Partki(Y)) для n = 75 и к = 1,..., 75. Как видно, величина достигает максимум при к = 10, следовательно, критерий устойчив.

Критерий Байеса в применении к проблеме оптимизации гиперпараметров имеет вид

h* = m&xy^Pj c(l nij (h))

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

- \Part(Y)\ = \Y\iy\

- \Comp(F)\ = \YР\

Рисунок 2 - Р(Partki(Y))НР(Partki(Y)) для n = 75 и к =—,..., 75

\Fact(X )\ = \Х РI

Затем количества элементарных исходов

\partk(п)\ -\comp1 (п)\ \factd(n)\ ■■

vi

k!

ni!...nfc! k!(n-k)! k\!...km!

, n! m!(n-m)!

n!__n!__d!

ni!...nrf! d!(n-d)! di!...dm!

где n — объем соответствующего множества, X, F или Y соответственно. Далее, определяются ожидаемые информативности

- EHf(Factd(X)) = Ei P(factd(X))Hf(Jactdd(X))

- EHc(Comp1 (F)) = P(compi(F))Hc(compi(F))

- EHp(Partk(Y)) = Etp(P*rtk(Y))Hp(partk(Y))

и, наконец, критерии

- d* = argmaXiEHF(Factdi (X))

- /* = argmaXiEHc(Compli(F))

- к* = агдтах.ЕНр(Partki (Y))

На Рисунке 3 представлен расчет величины ЕНр(Partk(X)) для п = 75 и к = 1,..., 75. Как видно, величина достигает максимума при к = 47, следовательно, критерий устойчив.

0.012 -0.010 -0.008 -0.000 -0.004 -0.002 -0.000 -

0 10 20 30 40 50 60 70

Рисунок 3 - ЕНр(Partk(X)) для п = 75 и к = 1,..., 75

Чтобы проверить, что разработанная модель априорного распределения корректна, сравним его с постериорным распределением, полученным методом Монте-Карло. Для получения постериорного распределения смоделируем случайным образом s результатов кластеризации и расчитаем суммарную ожидае-

мую информативность ЕНр(РаНк(Ь)) для каждого к. Таким образом будет получено постериорное оптимальное количество кластеров к* 0в^ Результат представлен на Рисунке 4. Как видно, априорное значение к* начинает совпадать с уже приблизительно при й = 1000. Таким образом, модель распределения корректна.

Рисунок 4 - для п = 75 and s = 1,

10000

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

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

Алгоритм k* kinf k* ksil

к* = true к K-means 0.96 0.94

Single linkage 0.96 0.92

MSE K-means 0.26 0.76

Single linkage 0.1 0.14

Таблица 1 - Устойчивость метода оценки информативности

— устойчивость метода;

— применимость метода для оптимизации гиперпараметров; различных алгоритмов обучения;

— применимость метода для выбора модели обучения.

Для проверки устойчивости метода и применимости к оптимизации гиперпараметров было сгенерировано s = 50 выборок размером п = 50, со случайной размерностью d G {2,..., 50} и истинным количеством кластеров к G {3,..., 10}. На сегенированных выборках производилась кластеризация двумя алгоритмами: K-means и single linkge, рассчитывались оптимальные количества кластеров k*nf на основе метода оценки информативности и k*sil на основе метрики Silhouette. Полученные значения сравнивались с истинным количеством кластеров по частоте совпадений и по среднему квадрату ошибки. Результаты представлены в Таблице 1. Как видно, метод оценки информативности оказался не только устойчивым, но и более точным при оптимизации гиперпараметров, чем оценка на основе внутреннего критерия.

Для проверки применимости метода в выборе модели обучения был составлен список алгоритмов кластеризации, использующих различные модели обучения: K-means, Single linkage и Optics. Сгенерирован набор данных размером п = 50, размерностью d = 4 и с истинным количеством кластеров к = 10. Для каждого алгоритма на основе меры точности V — measure находилось максимально точное количество кластеров к* и оптимальное количество кластеров k*nj на основе метода оценки информативности. Результаты представлены в Таблице 2. На их основе можно сделать следующие выводы: во-первых, для каждого алгоритма оптимальное количество кластеров на основе информативности совпадает с максимально точным количеством кластеров, во-вторых, ре-

А к,* к* inf

K-means 10 10 0,095377

Single linkage 9 9 0,088308

Optics 10 10 0,095377

Таблица 2 - Сравнение моделей обучения

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

Для метода автоматизации обучения без учителя исследовались следующие вопросы

— сравнение значения априорного критерия с внутренним постериорным при различном размере набора данных;

— сравнение точности результатов обучения на основе априорного критерия и на основе внутреннего постериорного;

— устойчивость метода автоматизации.

Для этого будем генерировать выборки с соответствующими параметрами. Для каждой выборки будем рассчитывать оптимальное количество кластеров по критерию Лапласа к"*1Ъош и по методу "локтя" к*1Ъош и выполнять алгоритм К-шеапэ с заданными количествами кластеров.

На Рисунке 5 представлена зависимость к*п^ и к*Ьош от размера набора данных п. Как видно, значение априорного критерия растет примерно с той же скоростью, что и значение внутреннего постериорного критерия.

На Рисунке 6 представлены графики точности значений к*п^ и к*е1Ьош при различном количестве истинных кластеров к. Как видно, априорный критерий незначительно уступает внутреннему постериорному критерию по точности, однако при этом достигается существенный снижение вычислительной сложности: сложность априорного критерия 0(1), постериорного — 0(2п^л//п)к2п3ё,).

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

10 15 20 25 30 35 40 45 50

п

0 10 20 30 40 50

1тие к

Рисунок 6

- Сравнение и к*1Ьот с ^ие к

Silhouette FM index Время

krand 0,21 0,08 0,00

к* 0,3 0,16 0,00

h* 0,32 0,18 0,03

Таблица 3 - Набор данных "Ирисы"

Silhouette FM index Время

krand 0,32 0,08 0,00

к* 0,50 0,15 0,00

h* ^elb 0,54 0,19 0,04

Таблица 4 - Набор данных "Вина"

выборки из реальных наборов данных. Были выбраны наборы данных "Ирисы" [99], "Вина" [100] и "Рак молочной железы" [98]. Для каждого набора данных сгенерировано s = 100 выборок размером п = 100.

Для каждой полученной таким путем выборки рассчитано оптимальное количество кластеров к* на основе разработанного априорного критерия Лапласа. Произведено Сравнение результатов кластеризации при полученных значениях к* с результатами, полученными при случайном количестве кластеров krand и при количестве, полученном методом "локтя". Сравнение результатов произведено на основе внутренней метрики Silhouette, на основе точности по метрике Fowlkes-Mallows index [43] и на основе времени, затраченного на нахождение значения гиперпараметра.

Список литературы диссертационного исследования кандидат наук Баймуратов Ильдар Раисович, 2019 год

Список литературы

1. Блягоз З.У., Попова А.Ю. Принятие решений в условиях риска и неопределенности // Вестник Адыгейского государственного университета. 2006. №4.

2. Колмогоров А.Н. Три подхода к определению понятия "количество информации" // Проблемы передачи информации, 1965, 1:1, 3—11.

3. Ширяев А.Н. Вероятность. — М.: МЦНМО, 2004.

4. Adriaans P. Information // Stanford Encyclopedia of Philosophy, 2012, https://plato.stanford.edu/entries/information/

5. Akaike H. A new look at the statistical model identification // IEEE Transactions on Automatic Control, 1974, Vol. 19, Pp. 716—723.

6. Ankerst M., Breunig M.M., Kriegel H.-P, Sander J. OPTICS: Ordering Points To Identify the Clustering Structure // ACM SIGMOD international conference on Management of data, 1999, 49-60.

7. Automated machine learning with azureml. https://github.com/Azure/MachineLearningNotebooks/tree/master/ how-to-use-azureml/automated-machine-learning, accessed: 2019-04-10.

8. Auto-ml: Automated machine learning for production and analytics. https://github.com/ClimbsRocks/automl, accessed: 2019-04-10.

9. Baimuratov I., Shichkina Y., Stankova E., Zhukova N., Than N. A Bayesian Information Criterion for Unsupervised Learning Based on an Objective Prior // Computational Science and Its Applications - ICCSA, 2019, 11619, 707-716.

10. Bar-Hillel Y., Carnap R. An Outline of a Theory of Semantic Information // Technical Report No. 247, October 27, 1952, Research Laboratory of Electronics. - 49.

11. Baimuratov I.R., Morozov S.D., Zhukova N.A. Verification of the Formal Approach to Data Fusion // CEUR Workshop Proceedings, 2018, Vol. 2268, pp. 179-189

12. Baimuratov I., Zhukova N. An Approach to Clustering Models Estimation // 22nd Conference of Open Innovations Association FRUCT, 2018, 19-24.

13. Baimuratov I., Zhukova N. Logical and Mathematical Models of Data Fusion // International Conference on Control, Artificial Intelligence, Robotics &

Optimization (ICCAIRO), 2017, pp. 121-126.

14. Bergstra J., Bardenet R., Bengio Y., Kegl B. Algorithms for hyper-parameter optimization // Proceedings of the 24th International Conference on Neural Information Processing Systems, 2011, 2546-2554.

15. Bergstra J., Bengio Y. Random search for hyper-parameter optimization // Journal of Machine Learning Research, 2012, 13, 281-305.

16. Blumer A., Ehrenfeucht A., Haussier D., Warmuth M.K. Occam's razor // Information processing letters, 1987, 24(6), 377-380.

17. Bonab H.R., Can F. A Theoretical Framework on the Ideal Number of Classifiers for Online Ensembles in Data Streams // 25th Conference on Information and Knowledge Management, 2016

18. Bonab H.R., Can F. Less Is More: A Comprehensive Framework for the Number of Components of Ensemble Classifiers // IEEE Transactions on Neural Networks and Learning Systems, 2017.

19. Bonev B., Escolado F., Giorgi D., Biasotti S. Information-theoretic selection of high-dimensional spectral features for structural recognition // Computer Vision and Image Understanding, 2013, No.113, pp. 214-228.

20. Calinski T., Harabasz J. A dendrite method for cluster analysis // Communications in Statistics-theory and Methods, 1974, 3: 1-27.

21. Cangelosi R., Goriely A. Component retention in principal component analysis with application to cDNA microarray data // Biology Direct, 2007

22. Cao J., Wu Zh., Wu J., Liu W. Towards information-theoretic K-means clustering for image indexing // Signal Processing, 2013, 93(7), Pp. 2026-2037.

23. Chaitin G.J. On the Length of Programs for Computing Finite Binary Sequences // Journal of Association for Computing Machinery, 1966, v. 13, No. 4, pp. 547-569

24. Chapelle O., Vapnik V., Bousquet O., Mukherjee S. Choosing multiple parameters for support vector machines // Machine Learning, 2002, 46: 131-159.

25. Chicco D. Ten quick tips for machine learning in computational biology // BioData Mining, 2017, 10 (35): 35.

26. Chuong B., Chuan-Sheng F., Andrew Y.Ng. Efficient multiple hyperparameter learning for log-linear models // Advances in Neural Information Processing

Systems, 2008, 20, 377-384.

27. Claesen M., De Moor B. Hyperparameter Search in Machine Learning // arXiv:1502.02127, 2015.

28. Cunningham P. Dimension Reduction // University College Dublin, Technical Report UCD-CSI-2007-7, 2007

29. D'Alfonso S. The Logic of Knowledge and the Flow of Information // Minds & Machines, 2014, 24(3), pp. 307-325.

30. Darwin-sparkcognition. https://github.com/sparkcognition/darwin-sdk, accessed: 2019-04-10.

31. Datarobot usage examples.

https://github.com/datarobot / datarobot-sagemaker-examples, accessed: 2019-04-10.

32. David A., Vassilvitskii S. How Slow is the k-means Method? // Proceedings of the 21nd Annual Symposium on Computational Geometry, 2006, 144-153.

33. David A., Vassilvitskii S. k-means++: The advantages of careful seeding // Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2007

34. Davies D.L., Bouldin D.W. A Cluster Separation Measure // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, PAMI-1 (2): 224-227.

35. de Sa A.G.C., Pinto W.J.G.S, Otavio L.V.B.O., Pappa G.L. RECIPE: A Grammar-Based Framework for Automatically Evolving Classification Pipelines // Lecture Notes in Computer Science, 2017, 10196, 246-261

36. de Sa, A.G.C., Freitas A.A., Pappa G.L. Automated Selection and Configuration of Multi-Label Classification Algorithms with Grammar-Based Genetic Programming // Parallel Problem Solving from Nature - PPSN XV. Lecture Notes in Computer Science. Springer International Publishing, 2018, 11102: 308-320.

37. Desgraupes B. Clustering indices, University of Paris Ouest-Lab Modal'X. vol.1, 2013, pp. 1-34.

38. Dunn J.C. Well-Separated Clusters and Optimal Fuzzy Partitions // Journal of Cybernetics, 1974, 4 (1): 95-104.

39. Escalante H., Montes M., Sucar E. Particle Swarm Model Selection // Journal

of Machine Learning Research, 2009, 10, 405-440

40. Feurer M, Klein A., Eggensperger K., Springenberg J., Blum M., Hutter F . Efficient and Robust Automated Machine Learning // Advances in Neural Information Processing Systems 28 (NIPS 2015). — 2015.

41. Fisher R.A. Theory of statistical estimation // Proceedings Cambridge Philosophical Society, 1925, 22(5), pp. 700-725.

42. Fortin S., Lombardi O., Vanni L. A pluralist view about information // Philosophy of Science, 2015, 82(5), pp. 1248-1259.

43. Fowlkes E.B., Mallows C.L. A Method for Comparing Two Hierarchical Clusterings // Journal of the American Statistical Association, 1983, 78(383): 553-569.

44. Franceschi L., Donini M, Frasconi P., Pontil M. Forward and Reverse Gradient-Based Hyperparameter Optimization // Proceedings of the 34th International Conference on Machine Learning, 2017, 70, 6-11.

45. Google cloud automl. https://cloud.google.com/automl/, accessed: 2019-04-10.

46. H2o.ai automl github. https://github.com/h2oai/h2o-3, accessed: 2019-04-10.

47. H2o-driverlessai. http://docs.h2o.ai/driverless-ai/latest-stable/docs/userguide/index.html, accessed: 2019-04-10.

48. Hamerly G., Elkan Ch. Learning the K in K-Means // Advances in Neural Information Processing Systems, 2004, 17.

49. Hazan E., Klivans A., Yuan Y. Hyperparameter Optimization: A Spectral Approach // arXiv:1706.00764, 2017.

50. Hazewinkel M., ed. Regression analysis // Encyclopedia of Mathematics, Springer Science+Business Media B.V., Kluwer Academic Publishers, 2001 [1994]

51. Hintikka J. Knowledge and Belief, 1962, Cornel University Press, Ithaca.

52. Hutter F., Caruana R., Bardenet R., Bilenko M., Guyonl., KeglB., Larochelle H. AutoML 2014 @ ICML // AutoML 2014 Workshop @ ICML. Retrieved 2018-03-28.

53. Hutter F., Hoos H., Leyton-Brown K. Sequential model-based optimization for general algorithm configuration // Learning and Intelligent Optimization, Lecture Notes in Computer Science, 2011, 6683: 507-523,

54. Hutter F., Kotthoff L, Vanschoren J. Automatic machine learning: methods, systems, challenges // Challenges in Machine Learning, New York: Springer, 2019.

55. Jin H., Song Q., Hu X. Auto-keras: An efficient neural architecture search system // arXiv:1806.10282, 2018.

56. Kearns M.J., Vazirani U.V. An introduction to computational learning theory, chapter 2. MIT press, 1994.

57. Komer B., Bergstra J., Eliasmith C. Hyperopt-sklearn: Automatic hyperparameter configuration for scikit-learn // ICML workshop on Automated Machine Learning, 2014

58. Kotthoff L., Thornton C, Hoos H.H., Hutter F., Leyton-Brown K. Auto-WEKA 2.0: Automatic model selection and hyperparameter optimization in WEKA // Journal of Machine Learning Research. — 2017.

59. Kullback S., Leibler R.A. On information and sufficiency // The Annals of Mathematical Statistics. 22(1), 1951. pp. 79-86.

60. Kuncheva L., Whitaker C. Measures of diversity in classifier ensembles and Their Relationship with the Ensemble Accuracy // Machine Learning, 2003, 51:2, 181-207.

61. Lee J., Kim D-W. Fast multi-label feature selection based on information-theoretic feature ranking // Pattern-recognition, 2015, 48(9), Pp. 2761-2771.

62. Ludwig. https://github.com/uber/ludwig, accessed: 2019-04-10

63. Mattingly H.H., Transtrum M.K., Abbott M.C., Machta B.B. Maximizing the information learned from finite data selects a simple model // Proceedings of the National Academy of Sciences, 2018, 115(8), 1760-1765.

64. Misiuna K. A Modal Logic of Information // Logic and Logical Philosophy, 2012, Vol. 21, pp. 33-51.

65. Mljar. https://github.com/mljar/mljar-api-python, accessed: 2019-04-10.

66. Mohr F., Wever M., Hüllermeier E. ML-Plan: Automated machine learning via hierarchical planning // Machine Learning, 2018, 107 (8-10): 1495-1515.

67. Mohri M., Rostamizadeh A., Talwalkar A. Foundations of Machine Learning. MIT Press, Second Edition, 2018.

68. Neumaier A. Solving ill-conditioned and singular linear systems: A tutorial on regularization // SIAM Review 40, 1998, pp. 636-666.

69. Olson R.S., Bartley N., Urbanowicz R.J., Moore J.H. Evaluation of a tree-based pipeline optimization tool for automating data science // Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), 2016, 485-492.

70. Opitz D., Maclin R. Popular ensemble methods: An empirical study // Journal of Artificial Intelligence Research, 1999, 11, 169-198.

71. Palmieri F.A.N., Ciuonzo D. Objective priors from maximum entropy in data classification // Information Fusion, 2013, 14(2), 186-198.

72. Park I-K., Choi G-S. Rough set approach for clustering categorical data using information-theoretic dependency measure // Information Systems, 2014, 48, Pp. 289-295.

73. Pearson K. On Lines and Planes of Closest Fit to Systems of Points in Space // Philosophical Magazine, 1901, 2 (11): 559-572.

74. Peter J.R. Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis // Computational and Applied Mathematics, 1987, 20: pp. 53-65.

75. Piironen J., Vehtari A. Comparison of Bayesian predictive methods for model selection // Statistics and Computing, 2017, 27: 711.

76. Polikar R. Ensemble based systems in decision making // IEEE Circuits and Systems Magazine, 2006, 6:3, 21-45

77. Rand W.M. Objective criteria for the evaluation of clustering methods // Journal of the American Statistical Association. American Statistical Association, 1971, 66 (336): 846-850.

78. Rokach L. Ensemble-based classifiers // Artificial Intelligence Review, 2010, 33:1-2, 1-39.

79. Rosenberg A., Hirschberg J. V-Measure: A conditional entropy-based external cluster evaluation measure // Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, 2007.

80. Schubert E, Sander J., Ester M, Kriegel H.P., Xu X. DBSCAN Revisited, Revisited // ACM Transactions on Database Systems, 2017, 42(3), 1-21.

81. Schwarz G.E. Estimating the dimension of a model // Annals of Statistics, 1978, 6(2): 461-464

82. Sewell W. Correlation and causation // Journal of Agricultural Research, 1921, 20: 557-585.

83. Shai Sh-Sh, Shai B-D. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, New York, USA, 2014.

84. Shannon C.E. A Mathematical Theory of Communication // Bell System Technical Journal, 1948. Vol. 27, pp. 379-423.

85. Sibson R. SLINK: an optimally efficient algorithm for the single-link cluster method // The Computer Journal. British Computer Society, 1973, 16 (1): 30-34.

86. Simpson D., Rue H., Riebler A., Martins Th.G, S0rbye S.H. Penalising Model Component Complexity: A Principled, Practical Approach to Constructing Priors // Statistical Science, 2017, 32(1), 1-28.

87. Snoek J., Larochelle H., Adams R. Practical Bayesian Optimization of Machine Learning Algorithms // Advances in Neural Information Processing Systems, 2012, 2, 2951-2959.

88. Solomonoff R.J. A Formal Theory of Inductive Inference // Information and Control, 1964, v. 7, No. 1, pp. 1-22; No.2, pp. 224-254

89. S0rbye S.H., Rue H. Penalised Complexity Priors for Stationary Autoregressive Processes // Journal of Time Series Analysis, 2017, 38(6), 923-935.

90. Spiegelhalter, D.J., Best N.G., Carlin B.P., van der Linde A. Bayesian measures of model complexity and fit (with discussion) // Journal of the Royal Statistical Society, Series B, 2002, 64 (4): 583-639.

91. Swearingen Th, Drevo W., Cyphers B., Cuesta-Infante A., Ross A., Veeramachaneni K. ATM: A distributed, collaborative, scalable system for automated machine learning // 2017 IEEE International Conference on Big Data (Big Data), 2017, IEEE: 151-162.

92. Thomas M.C., Joy A.T. Elements of Information Theory, 2nd Edition. Wiley-Interscience, 2006. pp. 792.

93. Thorndike R.L. Who Belongs in the Family? // Psychometrika, 1953, 18 (4): 267-276

94. Thornton C, Hutter F, Hoos H.H., Leyton-Brown K. Auto-WEKA: Combined selection and hyperparameter optimization of classifcation algorithms // 19th ACM SIGKDD Conference on Knowledge Discovery and

Data Mining (KDD'13), 2013.

95. Tianxing M, Baimuratov I.R., Zhukova N.A. A knowledge-oriented recommendation system for machine learning algorithm finding and data processing // International Journal of Embedded and Real-Time Communication Systems, 2019, Vol. 10, No. 4, pp. 20-38

96. Transmogrifai. https://github.com/salesforce/TransmogrifAI, accessed: 2019-04-10.

97. Truong A., Walters A., Goodsitt J., Hines K., Bruss B., Farivar R. Towards Automated Machine Learning: Evaluation and Comparison of AutoML Approaches and Tools // arXiv:1908.05557, 2019

98. UCI Machine Learning Repository: Breast Cancer Wisconsin (Diagnostic) Data Set. URL: https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+(Diagnostic) (дата обращения: 18.11.2019).

99. UCI Machine Learning Repository: Iris Data Set. URL: http://archive.ics.uci.edu/ml/datasets/Iris (дата обращения: 18.11.2019).

100. UCI Machine Learning Repository: Wine Data Set. URL: https://archive.ics.uci.edu/ml/datasets/wine (дата обращения: 18.11.2019).

101. Valiant L. A theory of the learnable // Communications of the ACM, 27, 1984.

102. Vinh N.X., Epps J., Bailey J. Information theoretic measures for clusterings comparison // Proceedings of the 26th Annual International Conference on Machine Learning - ICML, 2009, pp. 1073-1080.

103. Von Neumann J. Mathematische Grundlagen der Quantenmechanik, 1955, Berlin: Springer.

104. Warne R.T., Larsen R. Evaluating a proposed modification of the Guttman rule for determining the number of factors in an exploratory factor analysis // Psychological Test and Assessment Modeling, 2014, 56: 104-123.

105. Wolpert D.H., Macready, W.G. No Free Lunch Theorems for Optimization // IEEE Transactions on Evolutionary Computation, 1997, 1(67): 67-82.

106. Zaki M.J., Meira Jr.W., Meira W. Data mining and analysis: fundamental concepts and algorithms. Cambridge University Press, 2014.

107. Zhukova N., Baimuratov I, Nguyen T, Mustafin N. The Information Estimation System for Data Processing Results // Proceedings of the 24th

Conference of Open Innovations Association FRUCT, 2019, 810-814

Приложение А

Сгенерированный набор данных

Номер Хс2 Хз Х/4 Кластер

0 -10.30880864 3.91546613 -9.53260447 -12.75232708 9

1 -2.7642421 -9.0679942 6.5766268 -1.89075142 0

2 7.08350365 -2.3852434 0.66559699 2.60874541 6

3 -10.52389806 5.29043684 -9.6079636 -10.34930122 9

4 -0.41030163 -4.29764479 6.58664231 0.59650596 8

5 1.19632397 -3.26912204 5.8732178 -5.73782455 1

6 1.20197016 -2.65288103 3.97760808 -6.00287066 1

7 -2.3090164 -6.03269012 6.25288937 0.02255196 0

8 6.40867423 2.71648762 6.18433559 1.68192672 2

9 0.2901537 1.59210099 -1.27793409 4.46675549 5

10 8.10285751 -1.7006137 1.44910216 3.62014689 6

11 -3.87384628 -2.32406723 -10.17620645 3.14885185 4

12 0.75704216 -4.82053622 4.59039618 1.12872438 8

13 6.58384321 1.40151484 -3.29400977 -2.24838471 7

14 7.3220483 3.86464502 6.57369082 1.29590353 2

15 -0.14315465 -3.82695308 5.23151349 -6.31716669 1

16 8.11802537 -0.36116666 0.41303771 2.3092357 6

17 -0.74866666 -4.6804906 4.87353591 -8.93293087 1

18 1.06468848 -5.92112572 5.64851864 2.18356493 8

19 8.58168449 5.98062211 8.15481075 -0.23703952 2

20 -6.46761282 -1.29924464 -1.48226479 7.7661633 3

21 -4.89374025 -6.9047234 6.96761143 -1.93466545 0

22 -3.20815576 -7.70490229 5.83107035 -0.21966208 0

23 7.70628425 2.21910935 -4.56460881 -4.27333942 7

24 0.11168559 1.35471757 -1.12777305 3.46896147 5

25 -5.13630879 -2.21047483 -11.39694382 2.31117212 4

26 -6.40705426 -1.61067027 -2.47564072 6.95975378 3

27 -3.46876651 -6.78428994 6.01024494 0.15339327 0

28 -9.397352 3.04899742 -8.25057596 -11.33493254 9

29 6.18093304 0.42071789 -4.14205681 -3.48249239 7

30 6.33392723 1.69857636 -4.71215689 -3.60468884 7

31 -0.42840826 -5.17462324 6.68841577 3.43783642 8

32 6.5644279 -0.63191216 1.95783887 1.19565037 6

33 -0.61844317 -4.50860104 4.963016 1.76972678 8

34 -5.38121962 -2.5428276 -8.47147901 2.8147317 4

35 1.76137917 -4.33241103 5.31639456 -6.19976609 1

36 -5.44396482 -2.55287207 -0.4288912 6.29089701 3

37 -10.53187886 3.91670333 -8.6925055 -9.12272731 9

38 6.13337961 0.4617146 -3.42664091 -3.25555353 7

39 -5.7892938 -1.36183003 -9.416994 2.02181471 4

40 -6.96834568 -1.25599643 -0.1234829 6.65623728 3

41 -7.5086506 -1.75460389 -0.37354302 4.71098147 3

42 2.32341826 1.32831621 -0.61138122 3.24963165 5

43 6.45836873 4.13929202 7.1561515 0.1343287 2

44 7.27206712 4.84476656 9.2023718 -1.87569784 2

45 -0.9229551 0.26353521 -0.72232618 5.22442495 5

46 7.02339675 -0.93774221 1.35313977 2.64542653 6

47 -3.5930965 -2.19319136 -9.10040298 1.39851803 4

48 1.3894047 2.08084801 -2.0459338 4.5419212 5

49 -10.23859692 5.13445013 -10.27091609 -9.30307169 9

Таблица 4.7: Сгенерированный набор данных

Приложение B

Программная реализация разработанных методов

Модуль генерации разбиений

#Генерация разбиений заданного числа def parts(n): a = [1]*n y = -1 v = n

while v > 0: v -= 1

x = a[v] +1 while y >= 2 * x: a[v] = x

У -= x v += 1

w = v + 1

while x <= y:

a[v] = x

a[w] = y

yield a[:w + 1]

x += 1

y -= 1

a[v] = x + y y = a[v] - 1 yield a[:w]

#Генерация k-частных разбиений заданного числа def k_parts(n, k):

a = [1]*n

y = -1

v = n

while v > 0: v -= 1

x = a[v] +1 while y >= 2 * x: a[v] = x

y -= x

v += 1 w = v + 1 while x <= y: a[v] = x a[w] = y l = w + 1 if l == k:

yield a[:l] x += 1

y -= 1

a[v] = x + y y = a[v] - 1 if w == k:

yield a[:w]

Модуль оценки информативности

import numpy as np

from collections import Counter

from math import log

from part import parts, k_parts

from operator import itemgetter

#Получение разбиения def list_to_part(X):

return list(Counter(X).values())

def matrix_to_part(X): M = []

m = len(X[0]) for i in range(m):

M.append([x[i] for x in X])

arr = [] for line in M:

arr.append(len(set(line)))

return arr

#Оценка разбиения def entr(part):

n = sum(part)

inf = [log(x, n) for x in part]

return np.mean(inf)

def inf_part(y, cash):

n = len(y) k = len(set(y))

k_entr = cash.get(k) if k_entr == None:

print(k)

parts = k_parts(n, k) inf = []

for part in parts:

inf.append(entr(part))

k_entr = np.mean(inf) cash[k] = k_entr

return entr(list_to_part(y)) - k_entr

def inf_k(n, k, cash):

k_entr = cash.get(k) if k_entr == None:

print(k)

parts = k_parts(n, k) inf = []

for part in parts:

inf.append(entr(part))

k_entr = sum(inf) cash[k] = k_entr

return k_entr

#Получение оптимального количества подмножеств def get_k(n, cash):

k = cash.get(n) if k == None:

arr = []

for i in range(1, n+1) arr.append([i, 0])

_parts = parts(n) for part in _parts:

arr[len(part)-1][1] += entr(part)

arr.sort(key=itemgetter(1), reverse = True) k = arr[0][0] cash[n] =k

return k

Модуль визуализации

import matplotlib.pyplot as plt from sklearn.decomposition import PCA

def vizualize(data, labels, fig_name, d=2):

k_list = set(labels) n = len(labels) arr = []

for k in k_list: arr. append([]) for i in range(n):

if labels[i] == k:

arr[-1] .append(i)

if len(data[0]) != d:

pca = PCA(n_components=d).fit(data) data = pca.transform(data)

fig = plt.figure()

plt.scatter(data[:, 0], data[:, 1], c=labels) fig.savefig(fig_name + .png)

plt.close(fig) Пример оценки

from sklearn.datasets.samples_generator import make_blobs import inf

from viz import vizualize

if__name__==__main__:

n = 50 d = 4 k = 10 cash = {}

#Генерация данных

data, target = make_blobs(n_samples=n, centers=k, n_features=d) #Оценка разбиения

metric = inf.inf_part(target, cash)

#Запись результатов file_name = test f = open(file_name + .txt,"w") f.write(str(k) + \n) f.write(str(metric) + \n) for i in range(n):

f.write({}, {}, {}\n.format(i, data[i], target[i])) f.close()

vizualize(data, target, file_name)

Пример автоматизации

from sklearn.datasets.samples_generator import make_blobs from sklearn.cluster import KMeans import inf

from viz import vizualize

if__name__==__main__:

n = 50 d = 4 cash = {}

#Расчет оптимального количества кластеров k_inf = inf.get_k(n, cash)

#Генерация данных

data, target = make_blobs(n_samples=n, centers=k_inf, n_features=d) #Обучение модели

model = KMeans(n_clusters=k_inf).fit(data) labels = model.labels_

#Запись результатов file_name = test f = open(file_name + .txt, w) f.write(str(k_inf) + \n) for i in range(len(labels)):

f.write({}, {}\n.format(i, labels[i])) f. close()

vizualize(data, target, file_name, 2)

Публикации

2017 International Conference on Control, Artificial Intelligence, Robotics & Optimization

Logical and Mathematical Models of Data Fusion

Ildar Baymuratov Nataly Zhukova

ITMO University ITMO University

Saint-Petersburg, Russia Saint-Petersburg, Russia

Email: [e-mail] Email: [e-mail]

Abstract—In order to represent data fusion process in more systematic way, a logical model of the process is suggested. The logical model being insufficiently general to represent different data fusion algorithms is reformulated on category theory language. After that a number of information theoretic measures defined on morphisms are suggested as universal criteria for evaluation of data fusion algorithms.

Index Terms—Data fusion, fuzzy logic, category theory, information theory.

I. Introduction

There is a research area named 'Data fusion'. Data fusion is integration of different types of information, usually uncertain, received from different sources, directed to decision-making. Aims of a typical data fusion system are processing of continuously incoming raw data, evaluation of current situation, prediction of forthcoming events and recommendation considering corresponding actions. Data fusion process is analogous to the process during which humans and animals combine data from different senses, experience and reasoning ability to improve their survive chances.

Consider biometric data as an example. A system that uses the only biometric factor has high error probability. For instance, if that factor is fingerprints, then for people with extremely fat or dry or injured fingers it is problematic to get fingerprints of acceptable quality. But if we use iris recognition also, error probability will significantly decrease. Another example of data fusion is a moving object, such as an aircraft, observed by both a pulsed radar and an infrared sensor. The radar accurately determines the aircraft's range, but it hardly determines the angular direction of the aircraft. By contrast, the infrared sensor accurately determines the aircraft's angular direction, but is unable to measure range. The combination of these two observations provides an improved determination of the aircraft's location.

To extract particular and possibly more analysable stages in data fusion process, different models of the process are developed. In 1986 so called JDL data fusion model was developed . It consists of the following levels:

1) preprocessing: processing of incoming data;

2) object refinement: data integration for getting improved representation of individual objects;

3) situation refinement: description of relations between objects and environment;

4) threat refinement: projecting of current situation in future and predicting of consequences.

5) process refinement: meta-level for process control. Other models representing data fusion as set of levels were also developed. The extensive research of data fusion field can be found in, for example, Mitchell's 'Data Fusion: Concepts and Ideas' [1] or Hall's and McMullen's 'Mathematical Techniques in Multisensor Data Fusion' [2].

By now numerous methods of data integration were developed for each level. For example, artificial neural networks, wavelet transformations, Markov random fields, etc. are used at object refinement level, Bayesian networks, fuzzy logic, Dempster-Shafer theory and other methods are used for classification and so on. As result, data fusion field dissolves to set of poorly correlated subproblems. Some of them are more elaborated, such as image recognition or classification, and some are hardly articulated and have no common approach. Data fusion methods were developed apart from each other and it is difficult to put them in any common context. Finally, it is problematic even to meaningfully compare different algorithms of data fusion.

The purpose of this work is to develop universal mathematical model of data fusion process in context of uncertainty. That allows:

• represent the process of data fusion in more systematic way;

• develop universal criteria for estimating and comparing data fusion algorithms.

Examples of such systematizations already exist. In 'Mathematics of Data Fusion' by I. R. Goodman, Ronald P. S. Mahler and Hung T. Nguen [3] fuzzy logic, random set theory and conditional event algebra are used as such mathematical foundation. In this work data fusion process is reduced, first, to logic, fuzzy in general case, then to category theory and, finally, a criteria set for estimating and comparing data fusion algorithms is formulated.

II. Data fusion models A. Logical data fusion model

In this section a logical model of data fusion process is presented. First of all, define what logic is meant. This logical model is based on first order predicate logic language, extensive elaboration of which and its semantics can be found, for example, in Chang's and Keisler's 'Model Theory' [4]. The model consists of:

• individual constants: ai,a2,...;

978-1-5090-6536-3/17 $31.00 © 2017 IEEE DOI 10.1109/ICCAIRQ.2017.33

• individual variables: x1,x2,...;

• individual functions: f1 ,... ;

• predicate functions: P1,P2,...;

• quantifiers: V, 3.

Consider first order predicate logic formula in general:

Q1x1 ...QnxnP(x1j ...; xnj ...; /m),

where Qi — some quantifier. The interpretation of such formula is represented by the following structure:

^ [0,1]

• v — some valuation of xi, ...,xn;

• a,..., e — a set of values of x1,..., xn for some valuation v;

• s,..., t — a set of values of f1,..., fm for some valuation v.

If each valuation v satisfies P(x1,...,xn) e {0,1}, the logic is pure, but in general case P(x1,..., xn) e [0,1] and the logic is fuzzy.

Finally, associate each syntactical category of predicate logic with elements of JDL-model:

X1 . . xn /1 . . fm P

V1 01 . . e1 ^ S1 . . ^ t1 ^ [00, 1]

Vq aq . . eq ^ sr . . ^ ts ^ ¡0,1]

where

Predicate logic Data fusion

individual constants data

individual variables object features

individual functions processes

predicate function particular situation assessment

quantifiers general situation assessment

To sum up, it is shown that data fusion process can be described in logical terms. Since, first, there is no general accepted data fusion model, second, data fusion models usually have no articulated list of categories, it would be groundless to state that data fusion process can be completely reduced to logic, but due to grounding of data fusion on logical base it becomes possible to formulate that list of categories.

However, at current stage it is still problematic to define universal criteria applicable to individual functions, predicate functions and quantifiers, thus in the next section present logical model is reformulated on the language of more abstract mathematical theory.

B. Category theoretic data fusion model

As such more abstract mathematical theory category theory is used. There are examples of data fusion representation in category theory terms. Kokar, Tomasik and Weyman in 'Formalizing Classes of Information Fusion Systems' [5] consider two classes of data fusion systems: data fusion and decision fusion, formalize them in terms of category theory and show that decision fusion is a subclass of data fusion.

Category theoretic model presented here is derived from logical one. It is shown, for instance, in R. Goldblatt's 'Topoi, the Categorial Analysis of Logic' [6] that logic can be described in terms of category theory.

Analyzing the structure of predicate logic formula interpretation, two categories are extracted:

• data: a family of sets A = {X1, ...,Xn};

• truth-values: the interval TV = [0,1] and three morphism classes:

• data processing: DP : A ^ A;

• particular assessments: PA : A ^ TV;

• general assessments: GA : TV1 x ... x TV™ ^ TV. According to category theory, an identity morphism exists

for each category, thus, two identity morphisms are defined:

• for data category identity morphism ¿d : A ^ A e DA forms a set of pure data;

• for truth-values category identity morphism ¿d : TV ^ TV e GS forms a set of individual assessments.

Resulting structure is represented by the following diagram:

DP

TV

TV

Therefore, each data fusion process can be represented as a morphisms and it becomes possible to formulate universal criteria for data fusion algorithms.

C. Morphisms quantitative characteristics

Given a morphism f : X ^ Y, there is a set F : X ^ Y of alternative morphisms for the domain X and codomain Y. The cardinality of the set F is meant as quantitative characteristic of the morphism f. In this section characteristics for each morphism class of the present model will be given.

1) Data processing: Given a morphism f : X ^ Y, how many other possible morphisms from X to Y there are? First, there are |Y| different valuations of f(x) for some x. Then, there are |Y| different values for each x e X, thus, for a set of morphisms F : X ^ Y:

|F : X ^ Y| = |Y||X|.

This result can be generalized in two ways: first, morphism f can have n arguments, i.e. f is f : X1 x ... x Xn ^ Y. Then

|f : X1 x ... x Xn ^ Y| = |Y|lXil-lX"l.

Second, some f'(X) can have a different codomain, thus, F(X) = {F(X) = Y1} U ... U {F(X) = Yn} and

|F (X )| = | Y111 X !+ ...|Y„| 1 X L

pa

pa

ga

Therefore,

|F : A ^ Aj = £

for each Fi C F, such that Fi : X1 x ... x Xj ^ Y^

2) Particular assessments: According to the definition, particular assessment is a morphism PA : A ^ TV and A = X1;..., Xn,TV = [0,1], therefore,

PA : X1 x ... x Xn ^ [0,1].

Given m different values of PA(A) from [0,1], it follows that in general case

|PA : A ^ TV| = mili|Xi|.

If the logic being used is pure, each value of PA(A) is in {0,1} and m = 2, therefore, for pure logic

|PA : A ^ TV| = 2lli

Xi|

3) General assessments: As general assessment is a morphism GA : TV1 x ... x TVm ^ TV and TV = [0,1],

GA : [0,1] x ... x [0,1] ^ [0,1],

therefore, given TV1 x ... x TV« and l possible values of GA(TV1 x ... x TVm),

|GA : TV1 x ... x TVm ^ TV| = l.

If the logic being used is pure, there are only two possible values of GA(TV1 x ... x TV«), thus, for pure logic

|GA : TV x ... x TVm ^ TV| = 2.

To sum up, with each level of data fusion degrees of freedom decrease, that correlates with data integrity being increased during the data fusion process.

III. Morphism criteria

In this section the set of universal morphism criteria considering its effectiveness as data fusion algorithms is defined. For each morphism f : X ^ Y it is possible to characterize:

• some value y e Y of morphism f;

• morphism f itself;

• morphism f in relation with the whole set of morphisms F : X ^ Y.

Therefore, a measure will be defined for each of this items. Considered measures origins from information theoretical ones. An extensive elaboration of information theoretic measures can be found in 'Elements of Information Theory' [7] by Cover and Thomas .

A. Information

Given a morphism f : X ^ Y, a measure for some value y e Y of that morphism is defined.

As such measure Shannon's [8] information measure is used. For each xj e X and yi e Y it is possible to count frequency mi of f (xj ) = yi being satisfied. Then for each yi e Y it is possible to count information 1(y^):

I (yi

, mi

- logi*i|X| '

in other words,

1 (yi) = 1 - log|X| ;

This formula differs from Shannon's one in that cardinality | X| of the set X is used as logarithm base. Due to this fact,

0 < 1 (yi) < 1,

1 means that after the transformation from yi all information is reserved. Vice versa, if

and 1 (yi) = f-1(yi) to

1 (yi) = 0, it means that after the transformation f : X ^ Y all information presented in X is lost.

B. Knowledge

I suppose that considering data fusion process, information loss has positive aspects. Relieving from extra details reveals common tendencies. In respect to human thinking this process is named abstraction. Abstraction results in knowledge, thus, the measure K(yi) of knowledge amount contained in some value yi e Y of morphism f : X ^ Y, as opposite to information measure, is introduced:

K(yi) = log|x| mi.

The measure K(yi) also satisfies

0 < K(yi) < 1,

but if K(yi) = 1, it means that after the transformation f : X ^ Y all information, contained in X, is generalized. Vice versa, if K(yi) = 0, it means that transformation f : X ^ Y yields no knowledge.

Given some value y, it can be shown that

K(y) = 1 - I(y).

As I(y) = 1 - log|x| m,

1 - I(y) = 1 - (1 - log|x| m),

that is

1 - I(y) = log|x| m,