Диссертация (1137259), страница 11
Текст из файла (страница 11)
Тогда:1 − | | · 2−Δmin () ≤ 1 −∑︁2−Δ(,) ≤ Stab()(3.4)∈DD()Таким образом, эта оценка и верхняя оценка формулы (3.3) подсказывают, что устойчивость может иметь полезное на практике поведение61в логарифмической шкале. Так, например, авторы работы [53] замечают, что на достаточно больших контекстах, большая часть понятийимеет устойчивость близкую к единице, что не позволяет выбиратьнаиболее релевантные понятия. Позже будет показано на различныхбольших контектсах, что такое поведение свойственно всем выборкам данных. Таким образом, необходимо рассмотреть устойчивостьтакже и в логарифмической шкале:LStab() = − log2 (1 − Stab())(3.5)Принимая во внимание (3.3) и (3.4), получаем следующее:Δmin () − log2 (| |) ≤ − log2 (∑︁2−Δ(,) ) ≤ LStab() ≤ Δmin ().∈DD()(3.6)Данная оценка позволяет эффективно оценивать устойчивость втом числе в удобной логарифмической шкале.
Однако точность данной оценки (разность между верхней и нижней оценками) не можетбыть задана заранее. Здесь метод оценивания устойчивости методомМонте-Карло, предложенный в работе [11], оказывается полезным.Идея данного метода состоит в том, чтобы для понятия случайнымвыбором оценить количество подмножеств его объёма ⊆ Ext()таких, что описание этих подмножеств совпадает с содержанием понятия , то есть, что ′ = Int(). Затем, зная количество случайно выбранных подмножеств и количество искомых подмножеств.среди них можно оценить устойчивость как Stab() = Далее, авторы этой работы приводят следующую оценку количестватребуемых итераций:12 > 2 ln ,(3.7)2в которой – это желаемая точность оценки устойчивости, а – этовероятность ошибки. Это значит, что вычисленное значение устой-62чивости по методу Монте-Карло попадает в интервал [ − ; + ]с вероятностью 1 − .Пример 6.
Для того, чтобы оценить устойчивость по методуМонте-Карло с точностью = 0, 01 и вероятностью ошибки = 0, 01 необходимо выполнить по крайней мере = 2, 65 · 104итераций.Вышеприведённый пример показывает, что количество необходимых итераций для метода Монте-Карло может быть существенными, как следствие, вычислительная эффективность данного метода существенно ниже, чем оценка устойчивости по формуле (3.3). Болеетого, устойчивость стремится в среднем к единице при увеличенииразмера контекста, а значит для больших контекстов невозможно различить два устойчивых понятия, чья устойчивость отстоит от 1 навеличину точности метода Монте-Карло. Тем не менее метод МонтеКарло может гарантировать наперёд заданный уровень точности вотличии от метода оценивания, а значит метод Монте-Карло и методоценивания могут дополнять друг друга. Для этого, для текущегопонятия метод оценивания должен найти оценки снизу и сверху, ≤ Stab() ≤ .
Затем, если точность данной оценки хуже заданной − ≥ , то методом Монте-Карло можно улучшить даннуюоценку до . Здесь стоит отметить, что согласно (3.3) и (3.4), использование метода Монте-Карло может дать выигрыш только в случае(| | − 1)2−Δmin () ≥ , то есть когдаΔmin () ≤ log| | − 1.(3.8)Псевдо-код данного подхода показан в алгоритме 2. В дальнейшемданный подход будет называться комбинированным методом оценкиустойчивости.В работах [74; 75; 103] приводятся три других оценки устойчивости формального понятия. Первые две дает оценку сверху и снизупри условии, что мы добавляем несколько объектов в формальный63Function FindStabilityByBoundsMCInput: Формальный контекст K = (, , ); понятие ;желаемая точность и вероятность ошибки методаМонте-Карло .Output: < , ℎ > – пара оценок снизу и сверху дляустойчивости понятия .< , ℎ >← FindStabilityBounds(K, );if ℎ − > 2 · then ← FindStabByMonteCarlo(K, , , ); ← max( , − );ℎ ← min(ℎ, + );return < , ℎ >;Algorithm 2: Алгоритм оценки устойчивости понятия , основанный на комбинации методов Монте-Карло и оценивания.контекст и знаем точную меру устойчивости для начального контекста.
Последняя оценивает меру устойчивости путем рассмотренияподмножеств, имеющих определенную мощность. Первые оценки неприменимы в случае когда контекст строится полностью; последняяже имеет большую вычислительную сложность, так как требует перебора всех подмножеств объёма понятия определенной мощности.3.3Особенности расчёта устойчивости и её оценокДля инициализации алгоритма по вычислению меры устойчивости и его оценок согласно алгоритму [103] необходимо для понятия с объектами, инициализировать параметры данного понятиячислом 2 , что соответствует числителю, из которого ещё не вычлинеподходящие подмножества. При объёме понятия больше 32, данное число выходит за пределы точности стандартных типов данных,и следует либо использовать большие числа, что существенно замедлит вычисления и увеличит объём потребляемой памяти, либоиспользовать числа с плавающей точкой и хранить сразу отношение, соответствующее устойчивости.
Последний путь используетсяв нашем подходе. В частности, если текущая рассчитанная устой64чивость равна Stab(1 ) для понятия с объёмом = Ext(1 ), иэто значение нужно изменить на значение устойчивости понятияStab(2 ), то итоговое значение на следующей итерации должно бытьStab(1 )+1 = Stab(1 ) − Stab(2 ) · 2−(Ext(1 )−Ext(2 )) . Данный подходпозволяет получать приемлемую точность при расчёте устойчивости, без дополнительных нагрузок на память и время вычислений.Для расчёта устойчивости в логарифмическом масштабе, на данныймомент вычисляется сначала мера устойчивости, от которой затемберётся логарифм.При расчёте оценки устойчивости в логарифмическом масштабе, оценка сверху вычисляется напрямую как разница в объектах между объёмами.
Для расчёта оценки снизу левую часть формулы 3.6 можно преобразовать следующим образом LStab() ≥∑︀ −Δ(,)∑︀ −(Δ(,)−Δmin ())− log2 (2) = Δmin () − log2 (2). Та∈DD()∈DD()кое преобразование позволяет рассчитывать значение оценки устойчивости снизу без существенных потерь точности с использованиемстандартных типов данных.3.4Исследование поведения меры устойчивостиформального понятия и её оценокУстойчивость – одна из многих мер качества закономерностей.Важным её достоинством является возможность применения к различным типам элементарных моделей или закономерностей. Длямногих мер качества формально показано, что они выделяют схожие закономерности из разных выборок данных порождённых однойгенеральной совокупностью.
Это является необходимым условиемлюбой меры качества, так как гарантирует предсказуемость результата. Для многих мер качества закономерностей это было показаноформально либо проверено экспериментально. Не смотря на большое количество работ, использующих меру качества по устойчивостидля выделения важных закономерностей, на данный момент не суще65ствует работ исследующих независимость результатов ранжированияпо устойчивости закономерностей. Таким образом, в данном разделеисследуются вопросы поведения устойчивости на разных выборках,порождённых по одной генеральной совокупности.
Это исследование позволяет убедиться, что устойчивость обладает необходимымисвойствами и может быть использована для выделения важных закономерностей.Экспериментальное исследование устойчивости проводилось напублично доступных выборках данных, размещённых на портале Калифорнийского Университета [37]. Рассматриваемые выборки данных и их параметры приведены в таблице 3.2. Данные выборки существенно отличаются по размеру и сложности и, таким образом,представляют богатый тестовый материал для исследования поведения устойчивости. Сложность выборки в данном случае ссылаетсяна тот факт, что при одинаковом размере формального контекста,размер соответствующей решётки формальных понятий может бытьсущественно разным.
Чем больше этот размер, тем сложнее выборкакак для обработки так и для поиска важных узоров. Например, выборка Chess является наиболее сложной из исследуемых выборокпотому, что для небольшого контекста из 100 объектов в соответствующей решётке будет порядка 2 · 106 формальных понятий.3.4.1Схема экспериментаДля того чтобы исследовать поведение устойчивости на разныхвыборках порождённых одной генеральной совокупностью, доступная выборка данных должна быть разделена на две независимые выборки, на которых будет исследоваться поведение устойчивости.
Вэтом случае можно с уверенностью утверждать, что эти две выборкипорождены одной и той же генеральной совокупностью. Для удоб1http://archive.ics.uci.edu/ml/datasets/Mushroom2http://archive.ics.uci.edu/ml/machine-learning-databases/plants/3http://archive.ics.uci.edu/ml/datasets/Chess+(King-Rook+vs.+King-Pawn)4http://archive.ics.uci.edu/ml/datasets/Solar+Flare5http://archive.ics.uci.edu/ml/datasets/Nursery66ВыборкаСсылка |K| Макс. |K| Макс.
|ℒ| ℒstab15MushroomsMush812481242.3 · 103245726PlantsPlants 3478110002 · 1045104Chess3Chess31981002 · 10630 7.4 · 10310661066298800Solar Flare (II)4 Flare55NurseryNurs 12960129601.2 · 102455Таблица 3.2: Выборки использованные для исследования поведенияустойчивости. Колонка Ссылка соответствует краткому имени выборки для дальнейшего использования; |K| – количество объектовв выборке; Maкс.
|K| – максимальное количество объектов в выборке, которая может быть посчитана; Макс. |ℒ| – максимальноеколичество понятий в соответсвующей решётке; ℒ – время построения этой решётки; stab – время получения устойчивости для каждогопонятия из этой решётки.
Время вычислений указано в секундах.ства, в дальнейшем, эти две выборки будут называться как базовая итестовая. Более подробно эксперимент может быть описан следующим образом:1. Пусть имеется выборка данных K, содержащая объектов.Пусть также размер базовой и тестовой выборок равен . Длятого чтобы обеспечить, что базовая и тестовая выборка былинезависимы, необходимо, чтобы было по крайней мере вдвоеменьше чем . Например, при = 10, может быть равно 4.2.
По выборке K нужно случайным образом сконструировать базовую и тестовую выборки K и K , содержащие объектов.Например, если в выборку K входят объекты 1 , · · · , 10 тогда базовая может включать K = {2 , 5 , 6 , 9 }, а тестоваяK = {3 , 7 , 8 , 10 }.3. Для каждой выборки K и K должны быть найдены соответствующие решётки формальных понятий ℒ и ℒ .4.
Находятся пары формальных понятий ( , ) в решётках ℒ иℒ , где ∈ ℒ , а ∈ ℒ , такие что содержания этих поня67тий совпадают, Int( ) = Int( ). В дальнейшем формальныепонятий из одной пары называются похожими.5. Основываясь на парах похожих понятий, составляется множества численных пар = {· · · , ⟨ , ⟩ , · · · }, в котором каждаяпара соответствует паре похожих понятий, а каждое число впаре, устойчивости одного из этих понятий, = Stab( ), = Stab( ). Для всех понятий, для которых не нашлосьустойчивого понятия, создаётся пара чисел, в котором устойчивость похожего понятия принимается равной 0. Это соответствует значению устойчивости для “понятия”, в котором содержание незамкнуто. Также рассчитывается множество пар чисел, в котором для каждой пары из устойчивости пересчитываются в логарифмической шкале согласно формуле (3.5).6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
