Диссертация (1137259), страница 13
Текст из файла (страница 13)
Данный график вычислялся до тех пор, покабыло более 100 устойчивых понятий, то есть до тех пор, пока случайная перестановка двух элементов не приводит к существенномуизменению индекса упорядоченности. На этом графике видно, чтодля всех выборок данный график медленно растёт при увеличениипорога устойчивости в базовой выборке. При этом большие выборкиданных с относительно небольшим размером решётки формальныхпонятий (Mush4000, Nurs6480) имеют лучшую упорядоченность,чем маленькие.На графике 3.7 показан локальный индекс упорядоченности(ЛИУ) устойчивости в тестовой выборке.
ЛИУ – это индекс, которыйпоказывает насколько хорошо упорядочена устойчивость тех понятий в тестовой выборке, которые похожи на первые 1000 устойчивыхпонятий в базовой выборке при заданном пороге . На этом графике видно, что локально понятия одинаково упорядочены на базовойи тестовой выборках только тогда, когда принимаются во вниманиетолько сильно устойчивые понятия.
При этом порог сильной устойчивости существенно отличается от выборки данных к выборке. Этообъясняется тем, что наиболее устойчивые понятия сильнее отличаются друг от друга, чем менее устойчивые, и, соответственно, вероятность изменения порядка элементов ниже при небольших изменениях устойчивости. Если сравнивать ЛИУ и ГИУ, то ГИУ как правило даёт лучшее упорядочивание. Таким образом, наиболее устойчивые понятия в базовой выборке, буду оставаться наиболее устойчивыми в тестовой, в то время как, чем менее устойчивое понятие мы761.00.70.40.50.6ЛИУ0.80.9Mush120Mush1000Mush4000Plnt250Plnt1000Sflr120Sflr500Nurs250Nurs2000Nurs6480010203040Порог в базовой выборкеРисунок 3.7: Локальный индекс упорядоченности устойчивости втестовой выборке согласно порядку полученному по первым 1000устойчивым понятиям в базовой выборке.зафиксировали, тем меньше определено его место в общем порядкепонятий.
В частности, если эксперт будет анализировать устойчивыепонятия в порядке их устойчивости в разных выборках порожденныходной генеральной совокупностью, то первые понятия будут упорядочены практически в одном и том же порядке.3.4.5Ограничения данной схемы экспериментовДанная схема экспериментов была разработана для анализа поведения устойчивости. Здесь стоит отметить, что хорошее поведениелюбой меры качества элементарных моделей в такой схеме являетсянеобходимым условием, чтобы эта мера могла применяться на практике. Эта схема является необходимым условие, потому что любаямера качества должна в качестве наиболее важных понятий выбирать77Рисунок 3.8: Поддержка в тестовой выборке по отношению к поддержке в базовой.одни и те же понятия вне зависимости от конкретный выборки данных, если эти выборки порождены одной генеральной совокупность.Тем не менее, это не означает, что такая мера качества будут всегдаили часто предпочитать действительно важные закономерности.
Такнапример на рисунке 3.8 показан график, аналогичный графикам нарисунке 3.2, но для поддержки каждого содержания (мощности соответствующего объёма). На нём видно, что поддержка позволяетполучить намного менее размытую линию = . Тем не менее напрактике эта мера редко используется, так как среди закономерностей, отобранных по поддержке встречается много шума.3.5Сравнение меры устойчивости и её оценок с другими мерами качества моделейВ данном разделе приводится второй эксперимент, подтверждающий возможность использования устойчивости как меры качествазакономерностей.
Несмотря на то, большинство других мер качестваможет быть применено только к признаковым закономерностям, мы78можем сравнить устойчивость с ними именно на таких закономерностях. Более того, сравнение мер качества на признаковых данныхсущественно упрощает задачу сравнения, так как данных такого типасущественно больше в открытых источниках. Такое сравнение поможет показать, что мера качества по устойчивости является хорошимвыбором в том числе для выделения элементарных моделей процессов с состояниями сложной структуры.Основной сложностью такого исследования является вопрос: чтосчитать за истину? Дело в том, что разные меры качества будут выделять разные закономерности как важные, но как проверить, какаяиз них выдаёт правильный результат? В работе [23] авторы проверяют работу мер качества экспертным анализом, то есть сначалакачество закономерностей исследуется автоматически и затем оносоотносится с качеством, присвоенным этим закономерностям экспертами предметной области.
Это интересный и важный подход к такому анализу, имеющий некоторые недостатки. Во-первых, в данномподходе присутствует элемент субъективности – эксперт может ошибиться или неправильно понять свою задачу. Во-вторых, этот подходочень дорог. Так чтобы проверить различные меры качества на большой тестовой базе, необходимо найти большое количество экспертовв каждой из предметных областей тестовой базы.Другим подходом к оценке работы мер качества закономерностейявляются генераторы тестовых выборок [140]. В этом подходе порождаются тестовые выборки, в которых закономерности заранее известны, а сами выборки порождаются именно по этим закономерностям.
В этом случае остаётся нерешённым вопрос: на сколько хорошоалгоритмы порождения выборок по закономерностям соответствуетреальности.Наиболее близким подходом к нашему является работа [10], в которой авторы проверяют работу мер качества на задаче обучения сучителем. В этом случае классы объектов в выборке моделируют экспертные знания, но являются более объективными. Более того, этопозволяет не искать экспертов предметной области и использовать79все доступные выборки данных снабжённых информацией о классахобъектов. Основным недостатком данной работы является вид тестируемых закономерностей. Каждая закономерность также снабжаетсяинформацией о её классе и, таким образом, меры качества могут использовать эту информацию для улучшения своей работы.
Это приводит к смещению эффективности мер качества в сторону классификации и не позволяет делать выводы о их практической важности.В нашем подходе мы сравниваем только меры качества, которыене полагаются на метку класса закономерности. Более того, в нашемэксперименте такая информация не передаётся на вход мерам качества, что позволяет избежать смещения в сторону классификации длямер качества и более эффективно оценить их работу.
В данной работемы сравниваем меры устойчивости и рычага [117]. Мы также добавили к сравнению меру разницы, получаемой из верхней оценки устойчивости. Напомним, что для формального понятия , его устойчивость оценивается следующим образом Stab() ≤ 1 − min 2−Δ(,) .∈DD()Тогда разница задаётся как min Δ(, ). Эту меру качества законо∈DD()мерностей можно вычислить эффективно и, как мы позже увидим,она имеют практически тоже качество работы, что и мера устойчивости. Последней в нашем сравнении будет участвовать поддержказакономерности (мощность объёма формального понятия), котораяявляется самой простой, но которая часто используется для выделения закономерностей.3.5.1Рабочий примерКак было отмечено, сравнение проводится на признаковых данных.
Пример таких данных показан в таблице 3.3. В данной таблице8 объектов, 5 из которых находятся в обучающей выборке и 3 в тестовой, то есть метки класса объектов 6 , 7 и 8 не известны, но вскобках приведено правильное значение. Выборку таких данных является формальным контекстом (, , ). Закономерностями на таких данных являются множества признаков, например, {, } – это8012345678a b c d e f Метка классаxx x+xx xxx x+x x xx xx+x xx x?(+)xxx?(+)xx xx?(-)Таблица 3.3: Пример выборки для сравнения мер качества.закономерность и она встречается в большинстве объектов обучающей выборки. Для закономерности можно определить поддержку,как мощность множества объектов, в которых она встречается и частоту , как относительную поддержку или поддержку отнесённуюк мощности множества .Методы анализа формальных понятий могут выделить все замкнутые закономерности, то есть те множества признаков, к которымнельзя добавить других признаков без изменения множества объектов, в которых они встречаются.
Множество {, } замкнуто, так каконо входит 4 объекта (пока рассматривается только обучающая выборка {1 , 2 , 3 , 4 , 5 }), и при добавлении любого атрибута, расширенной множество признаков входит в меньшее число объектов. Вдальнейшем мы будем сравнивать меры качества именно при выделении замкнутых закономерностей. Рассмотрим, например, меруразницы для множества {, }. Любое расширение этого множествавходит не более, чем в один объект и, значит, мера разницы для этогомножества признаков вернёт 4 − 1 = 3.3.5.2Мера рычагаДля того чтобы определить меру рычага [117], необходимо напомнить, что двухкомпонентным разбиением или 2-разбиением множества называется любое разбиение этого множества на два непересекающихся множества и , такие что ∪ = .
Мы будем81обозначать такое разбиение как ( | ), а множество всех разбиениемножества , как Part2 ( ). Например, одним из разбиений множества {, , , , } является 2-разбиение ({, , } | {, }).Определение 24. Рычагом множества признаков , называется разница между частотой ( ) и максимальной ожидаемой частотойпри предположении, что любые подмножества независимы:Lev( ) = ( ) −max( | )∈Part2 ( )( ) · ( )Данная мера позволяет оценить насколько рассматриваемая закономерность неожиданна.
Авторы в своей работе также проверяютважность введённой ими меры и показывают, что задача её вычисления является сложной [117]. Авторы используют вероятностныеметоды расчёт меры рычага. В рамках их подхода, процесс расчётамеры рычага и процесс поиска закономерностей объединены в одинпроцесс. В нашей работе мы рассчитываем меру рычага только длязамкнутых закономерностей.
Покажем, что именно на них достигается максимум меры рычага.Утверждение 12. Мера рычага для некоторого множества признаков не меньше, чем меры рычага для его замыкания ′′ , т.е.Lev( ) ≤ Lev( ′′ ).Доказательство. Частота множества ( ) может только уменьшаться при увеличении размера множества, то есть (∀ ⊃ )() ≤( ). Частоты множества и его замыкания ′′ одинаковы, ( ) =( ′′ ). Пусть есть некоторое множество , тогда его 2-разбиение( | ) ∈ Part2 () порождает разбиение множества , то есть( ∩ | ∩ ) ∈ Part2 ().
Тогда,Lev( ′′ ) = ( ′′ ) −= ( ) −≥ ( ) −max( | )∈Part2 ( ′′ )max( | ) ∈ Part2 ( )(| ) ∈ Part2 ( ′′ ∖ )max( ∪ ) · ( ∪ ) ≥( ) · ( ) = Lev( ).( | )∈Part2 ( )82( ) · ( ) =Таким образом, рычаг принимает свои максимальные значение назамкнутых закономерностях, и достаточно рассматривать только ихдля поиска важных закономерностей согласно мере рычага.Пример 7. Для того, чтобы посчитать меру рычага для множества{, } нужно найти все 2-разбиения. В данном случае есть толькоодно такое разбиение: ({} | { }).
Частоты этих множеств следующие: ({, }) = 0.8, ({}) = 0.8, ({ }) = 0.8 (см. таблицу 3.3).Тогда Lev({, }) = 0.8 − 0.82 = 0.16. Для множества {, , } существует три 2-разбиения: ({}|{, }), ({}|{, }) и ({ }|{, }).Их частоты: ({, , }) = 0.2, ({}) · ({, }) = 0.8 · 0.2 = 0.16,({})·({, }) = 0.2·0.8 = 0.16, ({ })·({, }) = 0.8·0.2 = 0.16.Следовательно, Lev({, , }) = 0.2 − 0.16 = 0.04.3.5.3Схема экспериментаВ наших экспериментах меры качества проверяются с помощьюзадачи классификации, класс объектов в которых моделирует знанияэксперта.
Тогда способность различных мер качества к выделениюважных закономерностей может быть соотнесена с точностью и полнотой классификаторов.В основе такого эксперимента лежат следующие интуитивные соображения: если закономерность является интересной для эксперта,то она должна отражать базовые зависимости предметной области.Это должно давать преимущество в задачах классификации таким закономерностям перед случайными. Соответственно, систематическивысокое качество классификаторов основанных на некоторой мерекачества означает, что данная мера лучше подходит для выделенияважных закономерностей. Таким образом, методология сравнения работы различных мер качества состоит из следующих этапов:1. Выбирается выборка данных .832.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
