Диссертация (1137259), страница 14
Текст из файла (страница 14)
Стократно выборка разделяется на обучающую и тестовую подвыборки случайным образом. При этом обучающая выборкасодержит 90% , но не больше чем 1000 объектов, что является ограничением демо-версии программного обеспеченияMagnum Opus [118]. Это программное обеспечение используется для расчёта меры рычага, участвующей в сравнении.3. Выбирается целевой класс .4. Выбирается целевая мера качества ℳ.5. В каждой обучающей выборке, полученной на шаге 2, ищутсязамкнутые закономерности и они упорядочиваются мерой ℳ.При этом метки классов объектов не учитываются.6.
Среди всего множества закономерностей выделяются гипотезыкласса [73], известные также как контрастные закономерности (emerging patterns) [31]. Гипотезы – это такие закономерности, которые являются характеристическими для одного класса, то есть в поддержке такой закономерности присутствуют восновном (согласно порогу ) объекты класса .
Такие закономерности предполагаются хорошими для задач классификации.Пусть найдено гипотез.7. На этих гипотезах строятся классификаторов, основанныхна первых < гипотезах согласно мере ℳ. Каждый такойклассификатор работает следующим образом: для множествагипотез {1 , · · · , } классификатор относит любой объект кклассу , чьё описание содержит хотя бы одну из множества гипотез.8. Вычисляются точность и полнота для каждого такого классификатора в тестовом множестве. Эти результаты интерполируются в 21 точку следующего вида: (, ), где – это точность,а – полнота, при этом ∈ {0, 0.05, · · · , 0.95, 1}.
Эти точкизадают некоторую кривую.849. Шаги 6–8 повторяются для каждой пары обучающей и тестовой подвыборки выборки . Вычисляется усреднённая криваяточности-полноты.10. Площадь под усреднённой кривой даёт интегральное качествамеры ℳ на выборке по отношению к классу .11. Шаги 3–10 повторяются для всех классов в и для всех тестируемых мер качества.12. Шаги 1-11 повторяются для всех имеющихся выборок данных.На шаге 8 точность и полнота вычисляется по стандартным формулам. Возможны 2 исхода предсказания классификатора: положительный и отрицательный.
Для каждого из них возможны два варианта соотношения этого предсказания с действительностью: правильно и неправильно. Таким образом возможны 4 варианта: правильноположительный (TP), правильно отрицательный (TN), неправильноположительный (FP) и отрицательный (FN). Тогда точность задаётсякак = + , а полнота как = + .Шаг 6 схемы экспериментов содержит порог , но как именно следует установить этот порог? С одной стороны следует взять высокий порог, чтобы в рассмотрение входили только закономерностиинтересные для задачи классификации. Это нужно для того, чтобырезультат классификации не был смещён важными, но не имеющими отношения к задаче классификации закономерностями. С другойстороны, требуется достаточное количество закономерностей, чтобыувидеть разницу работы различных мер качества.
Здесь мы используем = 90%, но вопрос какой из порогов лучше остаётся открытым.Пример 8. Рассмотрим данную схему эксперимента на примеревыборки в таблице 3.3. В этой выборке 8 объектов, она поделена на обучающую выборку = {1 , 2 , 3 , 4 , 5 } и тестовую = {6 , 7 , 8 } подвыборки. Целевым классом выберем “+”, = +(шаг 3). Целевой мерой выберем разницу (шаг 4). В данном примере мы считаем закономерность гипотезой, если хотя бы половина85объектов в её поддержке относится к целевому классу. Таким образом, можно выделить 5 замкнутых гипотез: {, }, {, }, {, , },{, , } и {, , } (шаг 6). Соответствующие значения меры разницы: 3, 1, 1, 1, 1. Как мы видим они хорошо упорядочены и мы можемсоставлять классификаторы (шаг 7) и измерять их качество (шаги8 и 9).Первый классификатор содержит только одну гипотезу {, }.В тестовой выборке данная гипотеза включается только в 6 и таким образом точность и полнота равны 1 и 0.5.
Следующий классификатор основывается на {, } и {, }. Объект 6 включает{, } и поэтому классифицируется положительно, объекты 7 и 8включают {, } и, таким образом, они тоже классифицируютсяположительно. Значит, точность и полнота равны 23 и 1. Далее потаким значения точности и полноты вычисляется кривая точностии считается площадь под ней.3.5.4Результаты экспериментаВ таблице 3.4 показаны интегральные характеристики для различных мер качества закономерностей.
В рассмотрение попали: поддержка, устойчивость, разница, получаемая из верхней оценки устойчивости, и рычаг. Здесь стоит отметить, что устойчивость и разницаведут себя одинаково, подтверждая эффективность и практическуюзначимость введённой оценки. Между устойчивостью и рычагом неточевидного победителя, но тем не менее устойчивость является более удобной мерой качества, так как может быть применена к закономерностям любого типа, в том числе к элементарным моделямпроцессов с состояниями сложной структуры, тогда как рычаг, можетиспользоваться только для ранжирования множества признаков.86ВыборкаMushroomMushroomVoteVoteNurseryNurseryNurseryКлассPoisonousEatableDemocratRepublicanNot RecommendedPrioritySpecial PriorityПоддержка0.8906580.9272390.8652790.8834060.9750.785030.875556Разница0.9458810.9537930.8625070.9210930.9750.7430390.850174Устойчивость0.9456650.9539410.86450.9210040.9750.7252210.851127Рычаг0.9568950.9466830.9044330.8848180.9750.6054050.699788Таблица 3.4: Площадь под ROC-диаграммой для разных выборокданных, разных целевых классов и разных индексов полезности.Лучший индекс в строке выделен полужирным шрифтом.3.6Эффективность оценок устойчивостиВ данном разделе изучается эффективность предложенной оценки устойчивости, согласно формулам (3.3) и (3.6).
Экспериментальная база состоит из данных, описанных в таблице 3.5. Для вычисления устойчивости алгоритмом [103] требуется найти решётку формальных понятий с её отношением порядка. В нашем случае этарешётка получается алгоритмом AddIntent [87]. Для вычисленияоценки устойчивости, полная решётка не требуется, и нужно рассчитать только множество понятий (возможно не всё).
Для этих целейприменяется алгоритм FCbO [64]6 .Данные участвующие в экспериментах получены из UCI хранилища [37]. Среди выборок данных присутствуют также Chess иPlants, для которых невозможно найти полную решётку формальных понятий в силу её большого размера. Типичным подходом канализу больших данных является установление пороговой частотыискомых закономерностей. В нашем случае это соответствует минимальному количеству объектов в объёме понятия Supp . При установлении данного порога становится возможным найти множество частых понятий, для которых затем возможно оценить устойчивость. В6Реализация алгоритма взята с http://icfca2012.markuskirchberg.net.7http://archive.ics.uci.edu/ml/datasets/Mushroom8http://archive.ics.uci.edu/ml/machine-learning-databases/plants/9http://archive.ics.uci.edu/ml/datasets/Chess+(King-Rook+vs.+King-Pawn)10http://archive.ics.uci.edu/ml/datasets/Solar+Flare11http://archive.ics.uci.edu/ml/datasets/Nursery87Выборка|ℒ|ℒ FCbO Supp75Mush8124 2.3 · 10 324 570.70Plnt100082 · 106 45 104780Chss10092 · 106 46 104 3.5010SFlr106629880000115Nurs129601.2 · 10 245 50.20Оценка2 · 103181900.7425Chss31964.4 · 106––4210002 · 104Plnt347815.8 · 106––7951750 4.1 · 105Кобм.#МК36 · 106 · 1044463 · 1031922.3 · 1031128431.2 · 104 · 1043.5 ·104?(2%)4.6 ·105?(4.7%)Таблица 3.5: Время выполнения различных этапов обработки для данных изразличных источников.
|ℒ| – размер решётки формальных понятий; ℒ – время построения решётки формальных понятий алгоритмом AddIntent; stab – время расчёта устойчивости для каждого понятия в решётке; FCbO – время нахождения всехформальных понятия алгоритмом FCbO; Supp – минимальная кардинальность объёма понятий; Оценка – время вычисления оценки устойчивостей для всех понятия;Комб.
– время оценки устойчивости для всех понятия комбинированным методом;в скобках указывается процент от всех понятия, обработаных за указанное время.#MK – количество вызовов Монте-Карло в комбинированном подходе.этом случае нахождение точного значения устойчивости для неполного набора понятий не представляется возможным, поэтому толькооценка устойчивости будет использоваться для больших выборок. Втаблице 3.5 и в дальнейшем в целях эффективности любой методоценки устойчивости останавливает вычисления для данного понятия, как только становиться понятным, что понятие не может бытьустойчивым с порогом = 3.
Здесь и далее используется только логарифмическая устойчивость, отшкалированная по формуле (3.5)В таблице 3.5 можно отметить, что даже комбинированный метод(см. алгоритм 2), в котором участвует лишь небольшое количествовызовов процедуры оценки по Монте-Карло, является существенноболее медленным, чем оценочный метод, то есть методы оценки поформуле (3.6). Следовательно, мы не будем рассматривать отдельнометод Монте-Карло, так как он не может дать никаких преимуществпо сравнению с комбинированным методом, но с необходимостьюявляется более медленным, так как должен оценивать устойчивостькаждого понятия (а не только избранных) по методу Монте-Карло.88Более того, для больших решёток, комбинированный метод можетбыть слишком медленным, и тогда только оценочный метод можетбыть применён.Таблица 3.5 также показывает, что для больших решёток формальных понятий, оценки работают намного эффективнее, чем прямой расчёт устойчивости.
Для маленьких решёток, оценка устойчивости может занимать больше времени, чем прямой расчёт устойчивости. Однако, здесь стоит отметить, что для расчёта оценок, структура решётки формальных понятий не использовалась, в то времякак прямой расчёт полагается на неё.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
