Гранулярные вычисления

Парадигма вычислений, основанная на информационных сущностях («гранулах»)

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

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

Виды грануляции

Вид циклона со спутника.
Вид Манхэттена со спутника.

Как упоминалось выше, гранулярные вычисления — это не алгоритм или процесс; не существует конкретного метода, который называется «гранулярными вычислениями». Это скорее подход к рассмотрению данных, который распознает, как различные и интересные закономерности в данных могут проявляться на разных уровнях детализации, подобно тому, как различные особенности становятся заметными на спутниковых снимках большего или меньшего разрешения. Например, на спутниковом снимке с низким разрешением можно заметить интересные облачные узоры, представляющие циклоны или другие крупномасштабные погодные явления, в то время как на снимке с более высоким разрешением можно пропустить эти крупномасштабные атмосферные явления, но вместо этого заметить явления меньшего масштаба, такие как интересный узор, который представляют собой улицы Манхэттена . То же самое в целом верно для всех данных: при разных разрешениях или детализации появляются различные особенности и взаимосвязи. Цель гранулярных вычислений — попытаться воспользоваться этим фактом при разработке более эффективных систем машинного обучения и рассуждений.

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

Гранулирование значений (дискретизация/квантование)

Одним из типов грануляции является квантование переменных. Очень часто в приложениях добычи данных или машинного обучения требуется уменьшить разрешение переменных для извлечения значимых закономерностей. Примером этого может служить переменная, такая как «внешняя температура» ( temp ), которая в данном приложении может быть записана с точностью до нескольких десятичных знаков (в зависимости от измерительного прибора). Однако для целей извлечения соотношений между «внешней температурой» и, скажем, «количеством заявок в оздоровительный клуб» ( club ), как правило, будет выгодно квантовать «внешнюю температуру» на меньшее количество интервалов.

Мотивации

Существует несколько взаимосвязанных причин для грануляции переменных таким образом:

  • Исходя из предшествующих знаний в области , нет никаких ожиданий, что незначительные изменения температуры (например, разница между 80–80,7 °F (26,7–27,1 °C)) могут повлиять на поведение, определяющее количество заявок в оздоровительный клуб. По этой причине любая «регулярность», которую наши алгоритмы обучения могут обнаружить на этом уровне разрешения, должна быть ложной , как артефакт переобучения. Огрубляя переменную температуры до интервалов, разница между которыми, как мы ожидаем (основываясь на предшествующих знаниях в области), может повлиять на количество заявок в оздоровительный клуб, мы исключаем возможность обнаружения этих ложных закономерностей. Таким образом, в этом случае уменьшение разрешения является методом контроля переобучения .
  • Уменьшая количество интервалов в переменной температуры (т.е. увеличивая ее размер зерна ), мы увеличиваем количество выборочных данных, индексированных каждым обозначением интервала. Таким образом, огрубляя переменную, мы увеличиваем размеры выборки и достигаем лучшей статистической оценки. В этом смысле увеличение гранулярности является противоядием от так называемого проклятия размерности , которое связано с экспоненциальным уменьшением статистической мощности с увеличением количества измерений или мощности переменной.
  • Независимо от предшествующих знаний в предметной области часто бывает так, что значимые закономерности (т. е. те, которые можно обнаружить с помощью данной методологии обучения, языка представления и т. д.) могут существовать на одном уровне разрешения и отсутствовать на другом.
Преимущества грануляции значений: здесь существуют последствия при разрешении, которые не существуют при более высоком разрешении, в частности, и в то же время, { Х я , И дж } {\displaystyle \{X_{i},Y_{j}\}} { х я , у дж } ; {\displaystyle \{x_{i},y_{j}\};} х я , у дж : х я у дж , {\displaystyle \forall x_{i},y_{j}:x_{i}\not \to y_{j},} Х я И дж : Х я И дж . {\displaystyle \forall X_{i}\exists Y_{j}:X_{i}\leftrightarrow Y_{j}.}

Например, простая обучаемая система или система распознавания образов может стремиться извлекать закономерности, удовлетворяющие условному порогу вероятности, такому как В особом случае, когда эта система распознавания по существу обнаруживает логическое импликирование формы или, говоря словами, «если то ». Способность системы распознавать такие импликации (или, в общем случае, условные вероятности, превышающие порог) частично зависит от разрешения, с которым система анализирует переменные. п ( И = у дж | Х = х я ) α . {\displaystyle p(Y=y_{j}|X=x_{i})\geq \alpha.} α = 1 , {\displaystyle \альфа =1,} Х = х я И = у дж {\displaystyle X=x_{i}\rightarrow Y=y_{j}} Х = х я , {\displaystyle X=x_{i},} И = у дж {\displaystyle Y=y_{j}}

В качестве примера этого последнего пункта рассмотрим пространство признаков, показанное справа. Каждая из переменных может рассматриваться в двух различных разрешениях. Переменная может рассматриваться в высоком (четвертичном) разрешении, при котором она принимает четыре значения , или в более низком (двоичном) разрешении, при котором она принимает два значения. Аналогично, переменная может рассматриваться в высоком (четвертичном) разрешении или в более низком (двоичном) разрешении, при котором она принимает значения или соответственно. При высоком разрешении не обнаруживается никаких импликаций формы , поскольку каждая связана более чем с одной и, таким образом, для всех Однако при низком (двоичном) разрешении переменной становятся обнаруживаемыми две двусторонние импликации: и , поскольку каждая происходит тогда и только тогда, когда и происходит тогда и только тогда, когда Таким образом, система распознавания образов, сканирующая импликации такого рода, обнаружила бы их при разрешении двоичной переменной, но не смогла бы найти их при более высоком разрешении четверичной переменной. Х {\displaystyle X} { х 1 , х 2 , х 3 , х 4 } {\displaystyle \{x_{1},x_{2},x_{3},x_{4}\}} { Х 1 , Х 2 } . {\displaystyle \{X_{1},X_{2}\}.} И {\displaystyle Y} { у 1 , у 2 , у 3 , у 4 } {\displaystyle \{y_{1},y_{2},y_{3},y_{4}\}} { И 1 , И 2 } , {\displaystyle \{Y_{1},Y_{2}\},} Х = х я И = у дж , {\displaystyle X=x_{i}\rightarrow Y=y_{j},} х я {\displaystyle x_{i}} у дж , {\displaystyle y_{j},} х я , {\displaystyle x_{i},} п ( И = у дж | Х = х я ) < 1. {\displaystyle p(Y=y_{j}|X=x_{i})<1.} Х = Х 1 И = И 1 {\displaystyle X=X_{1}\leftrightarrow Y=Y_{1}} Х = Х 2 И = И 2 {\displaystyle X=X_{2}\leftrightarrow Y=Y_{2}} Х 1 {\displaystyle X_{1}} И 1 {\displaystyle Y_{1}} Х 2 {\displaystyle X_{2}} И 2 . {\displaystyle Y_{2}.}

Вопросы и методы

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

Ниже приведен пример статей, в которых рассматривается проблема дискретизации переменных в целом и дискретизации нескольких переменных в частности: Chiu, Wong & Cheung (1991), Bay (2001), Liu et al. (2002), Ван и Лю (1998), Зигед, Рабаседа и Ракотомалала (1998), Кэтлетт (1991), Догерти, Кохави и Сахами (1995), Монти и Купер (1999), Файяд и Ирани (1993), Чиу, Ченг и Вонг (1990), Нгуен и Нгуен (1998), Гржимала-Буссе и Стефановски (2001), Тинг (1994), Людл и Видмер (2000), Пфарингер (1995), Ан и Черконе (1999), Чиу и Чунг (1989), Хмелевский и Гржимала-Бюссе (1996), Ли и Шин (1994), Лю и Веллман (2002), Лю и Веллман (2004).

Переменная грануляция (кластеризация/агрегация/трансформация)

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

Трансформация переменных

Ряд классических методов, таких как анализ главных компонентов , многомерное шкалирование , факторный анализ и моделирование структурных уравнений , а также их родственники, попадают в род «преобразования переменных». Также в этой категории находятся более современные области исследования, такие как снижение размерности , поиск проекций и анализ независимых компонентов . Общей целью этих методов в целом является нахождение представления данных в терминах новых переменных, которые являются линейным или нелинейным преобразованием исходных переменных и в которых возникают важные статистические связи. Результирующие наборы переменных почти всегда меньше исходного набора переменных, и, следовательно, можно сказать, что эти методы накладывают грануляцию на пространство признаков. Все эти методы снижения размерности рассматриваются в стандартных текстах, таких как Duda, Hart & Stork (2001), Witten & Frank (2005) и Hastie, Tibshirani & Friedman (2001).

Агрегация переменных

Другой класс методов грануляции переменных вытекает больше из методологий кластеризации данных , чем из теории линейных систем, информирующей вышеприведенные методы. Довольно рано было отмечено, что можно рассматривать «кластеризацию» связанных переменных точно так же, как и кластеризацию связанных данных. При кластеризации данных идентифицируется группа схожих сущностей (используя « меру сходства », подходящую для области — Martino, Giuliani & Rizzi (2018)), а затем в некотором смысле заменяется эти сущности прототипом какого-либо вида. Прототипом может быть простое среднее значение данных в идентифицированном кластере или какая-то другая репрезентативная мера. Но ключевая идея заключается в том, что в последующих операциях мы можем использовать единственный прототип для кластера данных (возможно, вместе со статистической моделью, описывающей, как образцы выводятся из прототипа), чтобы заменить гораздо больший набор образцов. Эти прототипы, как правило, таковы, что захватывают большую часть интересующей информации относительно сущностей.

Дерево агломерации переменных Ватанабэ-Краскова. Переменные агломерируются (или «унифицированы») снизу вверх, причем каждый узел слияния представляет собой (сконструированную) переменную, энтропия которой равна совместной энтропии агломерирующих переменных. Таким образом, агломерация двух m -арных переменных, имеющих индивидуальные энтропии, дает одну m 2 -арную переменную с энтропией Когда сильно зависят (т. е. избыточны) и имеют большую взаимную информацию , то потому что и это будет считаться экономной унифицированностью или агрегацией. Х 1 , Х 2 {\displaystyle X_{1},X_{2}} ЧАС ( Х 1 ) , ЧАС ( Х 2 ) {\displaystyle H(X_{1}),H(X_{2})} Х 1 , 2 {\displaystyle X_{1,2}} ЧАС ( Х 1 , 2 ) = ЧАС ( Х 1 , Х 2 ) . {\displaystyle H(X_{1,2})=H(X_{1},X_{2}).} Х 1 , Х 2 {\displaystyle X_{1},X_{2}} я ( Х 1 ; Х 2 ) , {\displaystyle I(X_{1};X_{2}),} ЧАС ( Х 1 , 2 ) ЧАС ( Х 1 ) + ЧАС ( Х 2 ) {\displaystyle H(X_{1,2})\ll H(X_{1})+H(X_{2})} ЧАС ( Х 1 , Х 2 ) = ЧАС ( Х 1 ) + ЧАС ( Х 2 ) я ( Х 1 ; Х 2 ) , {\displaystyle H(X_{1},X_{2})=H(X_{1})+H(X_{2})-I(X_{1};X_{2}),}

Аналогично, разумно спросить, можно ли объединить большой набор переменных в меньший набор прототипных переменных, которые охватывают наиболее существенные связи между переменными. Хотя были предложены методы кластеризации переменных, основанные на линейной корреляции (Duda, Hart & Stork 2001; Rencher 2002), более мощные методы кластеризации переменных основаны на взаимной информации между переменными. Ватанабе показал (Watanabe 1960; Watanabe 1969), что для любого набора переменных можно построить политомическое (т. е. n-арное) дерево, представляющее ряд агломераций переменных, в котором конечная «общая» корреляция среди полного набора переменных является суммой «частичных» корреляций, демонстрируемых каждым агломерирующим подмножеством (см. рисунок). Ватанабе предполагает, что наблюдатель может попытаться таким образом разделить систему таким образом, чтобы минимизировать взаимозависимость между частями «... как если бы они искали естественное разделение или скрытую трещину».

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

Системная грануляция (агрегация)

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

Существуют также другие подходы, в которых группы определяются на основе, например, физической смежности строк. Например, Infobright реализовал механизм базы данных, в котором данные были разделены на грубые строки , каждая из которых состояла из 64K физически последовательных (или почти последовательных) строк. Грубые строки автоматически маркировались компактной информацией об их значениях в столбцах данных, часто включающих многостолбцовые и многотабличные связи. Это приводило к более высокому слою гранулированной информации, где объекты соответствовали грубым строкам, а атрибуты - различным аспектам грубой информации. Операции с базой данных могли эффективно поддерживаться в такой новой структуре, при этом доступ к исходным фрагментам данных оставался доступным (Slezak et al. 2013).

Концептуальная грануляция (компонентный анализ)

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

Гранулирование класса эквивалентности

Проиллюстрируем на примере. Рассмотрим систему атрибут-значение ниже:

Образец информационной системы
Объект П 1 {\displaystyle P_{1}} П 2 {\displaystyle P_{2}} П 3 {\displaystyle P_{3}} П 4 {\displaystyle P_{4}} П 5 {\displaystyle P_{5}}
О 1 {\displaystyle O_{1}} 12011
О 2 {\displaystyle O_{2}} 12011
О 3 {\displaystyle O_{3}} 20010
О 4 {\displaystyle O_{4}} 00121
О 5 {\displaystyle O_{5}} 21021
О 6 {\displaystyle O_{6}} 00122
О 7 {\displaystyle O_{7}} 20010
О 8 {\displaystyle O_{8}} 01221
О 9 {\displaystyle O_{9}} 21022
О 10 {\displaystyle O_{10}} 20010

При рассмотрении полного набора атрибутов мы видим, что у нас есть следующие семь классов эквивалентности или примитивных (простых) понятий: П = { П 1 , П 2 , П 3 , П 4 , П 5 } {\displaystyle P=\{P_{1},P_{2},P_{3},P_{4},P_{5}\}}

{ { O 1 , O 2 } { O 3 , O 7 , O 10 } { O 4 } { O 5 } { O 6 } { O 8 } { O 9 } {\displaystyle {\begin{cases}\{O_{1},O_{2}\}\\\{O_{3},O_{7},O_{10}\}\\\{O_{4}\}\\\{O_{5}\}\\\{O_{6}\}\\\{O_{8}\}\\\{O_{9}\}\end{cases}}}

Таким образом, два объекта в первом классе эквивалентности не могут быть различимы друг от друга на основе доступных атрибутов, а три объекта во втором классе эквивалентности не могут быть различимы друг от друга на основе доступных атрибутов. Остальные пять объектов каждый различимы от всех других объектов. Теперь представим себе проекцию системы значений атрибутов на один атрибут, которая будет представлять, например, взгляд наблюдателя, который способен обнаружить только этот один атрибут. Тогда мы получим следующую гораздо более грубую структуру класса эквивалентности. { O 1 , O 2 } , {\displaystyle \{O_{1},O_{2}\},} { O 3 , O 7 , O 10 } , {\displaystyle \{O_{3},O_{7},O_{10}\},} P 1 {\displaystyle P_{1}}

{ { O 1 , O 2 } { O 3 , O 5 , O 7 , O 9 , O 10 } { O 4 , O 6 , O 8 } {\displaystyle {\begin{cases}\{O_{1},O_{2}\}\\\{O_{3},O_{5},O_{7},O_{9},O_{10}\}\\\{O_{4},O_{6},O_{8}\}\end{cases}}}

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

Чтобы установить это понятие зависимости (см. также грубые множества ), представим конкретную грануляцию понятия, где каждое является классом эквивалентности из структуры понятия, индуцированной набором атрибутов Q. Например, если набор атрибутов Q состоит только из атрибутов, как указано выше, то структура понятия будет состоять из [ x ] Q = { Q 1 , Q 2 , Q 3 , , Q N } {\displaystyle [x]_{Q}=\{Q_{1},Q_{2},Q_{3},\dots ,Q_{N}\}} Q i {\displaystyle Q_{i}} P 1 {\displaystyle P_{1}} [ x ] Q {\displaystyle [x]_{Q}}

Q 1 = { O 1 , O 2 } , Q 2 = { O 3 , O 5 , O 7 , O 9 , O 10 } , Q 3 = { O 4 , O 6 , O 8 } . {\displaystyle {\begin{aligned}Q_{1}&=\{O_{1},O_{2}\},\\Q_{2}&=\{O_{3},O_{5},O_{7},O_{9},O_{10}\},\\Q_{3}&=\{O_{4},O_{6},O_{8}\}.\end{aligned}}}

Зависимость набора атрибутов Q от другого набора атрибутов P определяется выражением γ P ( Q ) , {\displaystyle \gamma _{P}(Q),}

γ P ( Q ) = | i = 1 N P _ Q i | | U | 1 {\displaystyle \gamma _{P}(Q)={\frac {\left|\sum _{i=1}^{N}{\underline {P}}Q_{i}\right|}{\left|\mathbb {U} \right|}}\leq 1}

То есть, для каждого класса эквивалентности в мы складываем размер его «нижнего приближения» (см. грубые наборы ) по атрибутам в P , т. е. Проще говоря, это приближение представляет собой количество объектов, которые по набору атрибутов P могут быть положительно идентифицированы как принадлежащие целевому набору Добавленное ко всем классам эквивалентности в числителе выше представляет собой общее количество объектов, которые — на основе набора атрибутов P — могут быть положительно категоризированы в соответствии с классификацией, вызванной атрибутами Q . Таким образом, коэффициент зависимости выражает долю (во всей вселенной) таких классифицируемых объектов, в некотором смысле фиксируя «синхронизацию» двух структур понятий и Зависимость «можно интерпретировать как долю таких объектов в информационной системе, для которых достаточно знать значения атрибутов в P, чтобы определить значения атрибутов в Q » (Ziarko & Shan 1995). Q i {\displaystyle Q_{i}} [ x ] Q , {\displaystyle [x]_{Q},} P _ Q i . {\displaystyle {\underline {P}}Q_{i}.} Q i . {\displaystyle Q_{i}.} [ x ] Q , {\displaystyle [x]_{Q},} [ x ] Q {\displaystyle [x]_{Q}} [ x ] P . {\displaystyle [x]_{P}.} γ P ( Q ) {\displaystyle \gamma _{P}(Q)}

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

Образец информационной системы
Объект P 1 {\displaystyle P_{1}} P 2 {\displaystyle P_{2}} P 3 {\displaystyle P_{3}} P 4 {\displaystyle P_{4}} P 5 {\displaystyle P_{5}}
O 1 {\displaystyle O_{1}} 12011
O 2 {\displaystyle O_{2}} 12011
O 3 {\displaystyle O_{3}} 20010
O 4 {\displaystyle O_{4}} 00121
O 5 {\displaystyle O_{5}} 21021
O 6 {\displaystyle O_{6}} 00122
O 7 {\displaystyle O_{7}} 20010
O 8 {\displaystyle O_{8}} 01221
O 9 {\displaystyle O_{9}} 21022
O 10 {\displaystyle O_{10}} 20010

Рассмотрим зависимость набора атрибутов от набора атрибутов. То есть мы хотим узнать, какую долю объектов можно правильно отнести к классам на основе знания о . Классы эквивалентности и показаны ниже. Q = { P 4 , P 5 } {\displaystyle Q=\{P_{4},P_{5}\}} P = { P 2 , P 3 } . {\displaystyle P=\{P_{2},P_{3}\}.} [ x ] Q {\displaystyle [x]_{Q}} [ x ] P . {\displaystyle [x]_{P}.} [ x ] Q {\displaystyle [x]_{Q}} [ x ] P {\displaystyle [x]_{P}}

[ x ] Q {\displaystyle [x]_{Q}} [ x ] P {\displaystyle [x]_{P}}
{ { O 1 , O 2 } { O 3 , O 7 , O 10 } { O 4 , O 5 , O 8 } { O 6 , O 9 } {\displaystyle {\begin{cases}\{O_{1},O_{2}\}\\\{O_{3},O_{7},O_{10}\}\\\{O_{4},O_{5},O_{8}\}\\\{O_{6},O_{9}\}\end{cases}}} { { O 1 , O 2 } { O 3 , O 7 , O 10 } { O 4 , O 6 } { O 5 , O 9 } { O 8 } {\displaystyle {\begin{cases}\{O_{1},O_{2}\}\\\{O_{3},O_{7},O_{10}\}\\\{O_{4},O_{6}\}\\\{O_{5},O_{9}\}\\\{O_{8}\}\end{cases}}}

Объекты, которые можно окончательно классифицировать в соответствии со структурой понятий , находятся в наборе , и поскольку их шесть, зависимость Q от P сама по себе может считаться интересной зависимостью, но, возможно, в конкретном приложении по добыче данных желательны только более сильные зависимости . [ x ] Q {\displaystyle [x]_{Q}} [ x ] P {\displaystyle [x]_{P}} { O 1 , O 2 , O 3 , O 7 , O 8 , O 10 } , {\displaystyle \{O_{1},O_{2},O_{3},O_{7},O_{8},O_{10}\},} γ P ( Q ) = 6 / 10. {\displaystyle \gamma _{P}(Q)=6/10.}

Затем мы могли бы рассмотреть зависимость меньшего набора атрибутов от набора атрибутов. Переход от к вызывает огрубление структуры класса , как мы вскоре увидим. Мы снова хотим узнать, какая доля объектов может быть правильно классифицирована в (теперь более крупные) классы на основе знания о Классы эквивалентности новых и показаны ниже. Q = { P 4 } {\displaystyle Q=\{P_{4}\}} P = { P 2 , P 3 } . {\displaystyle P=\{P_{2},P_{3}\}.} Q = { P 4 , P 5 } {\displaystyle Q=\{P_{4},P_{5}\}} Q = { P 4 } {\displaystyle Q=\{P_{4}\}} [ x ] Q , {\displaystyle [x]_{Q},} [ x ] Q {\displaystyle [x]_{Q}} [ x ] P . {\displaystyle [x]_{P}.} [ x ] Q {\displaystyle [x]_{Q}} [ x ] P {\displaystyle [x]_{P}}

[ x ] Q {\displaystyle [x]_{Q}} [ x ] P {\displaystyle [x]_{P}}
{ { O 1 , O 2 , O 3 , O 7 , O 10 } { O 4 , O 5 , O 6 , O 8 , O 9 } {\displaystyle {\begin{cases}\{O_{1},O_{2},O_{3},O_{7},O_{10}\}\\\{O_{4},O_{5},O_{6},O_{8},O_{9}\}\end{cases}}} { { O 1 , O 2 } { O 3 , O 7 , O 10 } { O 4 , O 6 } { O 5 , O 9 } { O 8 } {\displaystyle {\begin{cases}\{O_{1},O_{2}\}\\\{O_{3},O_{7},O_{10}\}\\\{O_{4},O_{6}\}\\\{O_{5},O_{9}\}\\\{O_{8}\}\end{cases}}}

Очевидно, имеет более грубую гранулярность, чем раньше. Объекты, которые теперь могут быть окончательно классифицированы в соответствии со структурой понятий, основанной на, составляют полную вселенную , и, таким образом, зависимость Q от P , То есть, знание членства в соответствии с набором категорий достаточно для определения членства в категории с полной уверенностью; В этом случае мы могли бы сказать, что Таким образом, огрубляя структуру понятий, мы смогли найти более сильную (детерминированную) зависимость. Однако мы также отмечаем, что классы, индуцированные в из-за снижения разрешения, необходимого для получения этой детерминированной зависимости, теперь сами по себе велики и немногочисленны; в результате зависимость, которую мы обнаружили, хотя и сильна, может быть для нас менее ценной, чем более слабая зависимость, найденная ранее в представлении с более высоким разрешением [ x ] Q {\displaystyle [x]_{Q}} [ x ] Q {\displaystyle [x]_{Q}} [ x ] P {\displaystyle [x]_{P}} { O 1 , O 2 , , O 10 } {\displaystyle \{O_{1},O_{2},\ldots ,O_{10}\}} γ P ( Q ) = 1. {\displaystyle \gamma _{P}(Q)=1.} [ x ] P {\displaystyle [x]_{P}} [ x ] Q {\displaystyle [x]_{Q}} P Q . {\displaystyle P\rightarrow Q.} [ x ] Q {\displaystyle [x]_{Q}} [ x ] Q . {\displaystyle [x]_{Q}.}

В общем, невозможно протестировать все наборы атрибутов, чтобы увидеть, какие индуцированные структуры концептов дают самые сильные зависимости, и поэтому этот поиск должен быть направлен с некоторой долей интеллекта. Статьи, в которых обсуждается этот вопрос, и другие, касающиеся разумного использования грануляции, принадлежат YY Yao и Lotfi Zadeh, перечисленным в #References ниже.

Гранулирование компонентов

Другая точка зрения на грануляцию понятий может быть получена из работы над параметрическими моделями категорий. Например, в обучении смешанной модели набор данных объясняется как смесь различных гауссовых (или других) распределений. Таким образом, большой объем данных «заменяется» небольшим числом распределений. Выбор числа этих распределений и их размера снова можно рассматривать как проблему грануляции понятий . В общем, лучшее соответствие данным достигается большим числом распределений или параметров, но для того, чтобы извлечь значимые закономерности, необходимо ограничить число распределений, тем самым намеренно огрубляя разрешение понятий. Нахождение «правильного» разрешения понятий является сложной задачей, для которой было предложено много методов (например, AIC , BIC , MDL и т. д.), и они часто рассматриваются под рубрикой « регуляризация модели ».

Различные интерпретации гранулярных вычислений

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

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

Смотрите также

Ссылки

  • An, Aijun; Cercone, Nick (1999), «Дискретизация непрерывных атрибутов для обучения правилам классификации», в Ning Zhong; Lizhu Zhou (ред.), Методологии обнаружения знаний и интеллектуального анализа данных: Труды Третьей Тихоокеанско-Азиатской конференции, PAKDD-99 , Конспект лекций по информатике, т. 1574, Пекин, Китай , стр.  509–514 , doi :10.1007/3-540-48912-6_69, ISBN 978-3-540-65866-5{{citation}}: CS1 maint: location missing publisher (link).
  • Bargiela, A. и Pedrycz, W. (2003) Гранулярные вычисления. Введение , Kluwer Academic Publishers
  • Бэй, Стивен Д. (2001), «Многомерная дискретизация для извлечения наборов данных», Knowledge and Information Systems , 3 (4): 491– 512, CiteSeerX  10.1.1.217.921 , doi : 10.1007/PL00011680, S2CID  10945544.
  • Кэтлетт, Дж. (1991), «О преобразовании непрерывных атрибутов в упорядоченные дискретные атрибуты», в Y. Kodratoff (ред.), Machine Learning—EWSL-91: Европейская рабочая сессия по обучению , Порту, Португалия , стр.  164–178 , ISBN 9780387538167{{citation}}: CS1 maint: location missing publisher (link).
  • Chiu, David KY; Cheung, Benny (1989), «Иерархическая дискретизация максимальной энтропии», в Ryszard Janicki; Waldemar W. Koczkodaj (ред.), Computing and Information: Proceedings of the International Conference on Computing and Information (ICCI '89) , Торонто, Онтарио , Канада: North-Holland, стр.  237–242.
  • Чиу, Дэвид К.Й.; Чунг, Бенни; Вонг, Эндрю К.С. (1990), «Информационный синтез на основе иерархической дискретизации с максимальной энтропией», Журнал экспериментального и теоретического искусственного интеллекта , 2 (2): 117– 129, doi :10.1080/09528139008953718.
  • Чиу, Дэвид К.Й.; Вонг, Эндрю К.С.; Чунг, Бенни (1991), «Обнаружение информации посредством иерархической дискретизации и синтеза с максимальной энтропией», в Грегори Пятецкий-Шапиро; Уильям Дж. Фроули (ред.), Обнаружение знаний в базах данных , Кембридж , Массачусетс : MIT Press, стр.  126–140.
  • Chmielewski, Michal R.; Grzymala-Busse, Jerzy W. (1996), «Глобальная дискретизация непрерывных атрибутов как предварительная обработка для машинного обучения» (PDF) , International Journal of Approximate Reasoning , 15 (4): 319– 331, doi :10.1016/s0888-613x(96)00074-6.
  • Догерти, Джеймс; Кохави, Рон; Сахами, Мехран (1995), «Управляемая и неуправляемая дискретизация непрерывных признаков», в Арманд Приедитис; Стюарт Рассел (ред.), Машинное обучение: Труды Двенадцатой международной конференции (ICML 1995) , Тахо -Сити, Калифорния : Morgan Kaufmann, стр.  194–202.
  • Дуда, Ричард О.; Харт, Питер Э.; Сторк, Дэвид Г. (2001), Классификация образов (2-е изд.), Нью-Йорк : John Wiley & Sons, ISBN 978-0-471-05669-0
  • Файяд, Усама М.; Ирани, Кеки Б. (1993), «Многоинтервальная дискретизация непрерывных атрибутов для обучения классификации», Труды Тринадцатой Международной совместной конференции по искусственному интеллекту (IJCAI-93) , Шамбери, Франция , стр  . 1022–1027{{citation}}: CS1 maint: location missing publisher (link).
  • Гржимала-Буссе, Ежи В.; Стефановский, Ежи (2001), «Три метода дискретизации для индукции правил», Международный журнал интеллектуальных систем , 16 (1): 29– 38, CiteSeerX  10.1.1.330.2975 , doi :10.1002/1098-111X(200101)16:1<29::AID-INT4>3.0.CO;2-0.
  • Хасти, Тревор ; Тибширани, Роберт ; Фридман, Джером (2001), Элементы статистического обучения: добыча данных, вывод и прогнозирование , Нью-Йорк : Springer, ISBN 978-0-387-84857-0
  • Красков, Александр; Штегбауэр, Харальд; Анджейак, Ральф Г.; Грассбергер, Питер (2003), Иерархическая кластеризация на основе взаимной информации , arXiv : q-bio/0311039 , Bibcode : 2003q.bio....11039K.
  • Ли, Чанхван; Шин, Дон-Гук (1994), «Контекстно-зависимая дискретизация числовых атрибутов для обучения классификации», в AG Cohn (ред.), Труды 11-й Европейской конференции по искусственному интеллекту (ECAI 94) , Нидерланды , стр.  428–432{{citation}}: CS1 maint: location missing publisher (link).
  • Лю, Чао-Линь; Уэллман, Майкл (2002), «Оценка байесовских сетей с помощью гибких методов абстракции пространства состояний», Международный журнал приближенного рассуждения , 30 (1): 1– 39, CiteSeerX  10.1.1.127.7040 , doi :10.1016/S0888-613X(01)00067-6, S2CID  17529419.
  • Лю, Чао-Линь; Уэллман, Майкл (2004), «Ограничение вероятностных отношений в байесовских сетях с использованием качественных влияний: методы и приложения», Международный журнал приближенного рассуждения , 36 (1): 31–73 , doi :10.1016/j.ijar.2003.06.002.
  • Лю, Хуан; Хуссейн, Фархад; Тан, Чу Лим; Дасии, Маноранджан (2002), «Дискретизация: эффективный метод», Data Mining and Knowledge Discovery , 6 (4): 393– 423, doi :10.1023/A:1016304305535, S2CID  207609303.
  • Ludl, Marcus-Christopher; Widmer, Gerhard (2000), "Относительная неконтролируемая дискретизация для извлечения ассоциативных правил", в Djamel A. Zighed; Jan Komorowski; Jan Zytkow (ред.), Труды 4-й Европейской конференции по принципам извлечения данных и обнаружения знаний (PKDD 2000) , Lecture Notes in Computer Science, т. 1910, Лион, Франция , стр.  148–158 , doi : 10.1007/3-540-45372-5_15 , ISBN 978-3-540-41066-9{{citation}}: CS1 maint: location missing publisher (link).
  • Монти, Стефано; Купер, Грегори Ф. (1999), «Модель скрытых переменных для многомерной дискретизации», Неопределенность 99: 7-й международный семинар по искусственному интеллекту и статистике , Форт-Лодердейл, Флорида{{citation}}: CS1 maint: location missing publisher (link).
  • Мартино, Алессио; Джулиани, Алессандро; Рицци, Антонелло (2018), «Методы гранулярных вычислений для задач распознавания образов биоинформатики в неметрических пространствах», в Pedrycz W.; Chen SM. (ред.), Computational Intelligence for Pattern Recognition , Studies in Computational Intelligence, т. 777, Springer International Publishing, стр.  53–81 , doi :10.1007/978-3-319-89629-8_3, ISBN 978-3-319-89628-1.
  • Нгуен, Хунг Сон; Нгуен, Син Хоа (1998), «Методы дискретизации в добыче данных», в Лехе Полковски; Анджей Сковрон (ред.), Грубые множества в обнаружении знаний 1: Методология и приложения , Гейдельберг : Physica-Verlag, стр.  451–482.
  • Пфарингер, Бернхард (1995), «Дискретизация непрерывных атрибутов на основе сжатия», в Armand Prieditis; Stuart Russell (ред.), Machine Learning: Proceedings of the Twelfth International Conference (ICML 1995) , Tahoe City, CA : Morgan Kaufmann , стр.  456–463.
  • Ренчер, Элвин С. (2002), Методы многомерного анализа , Нью-Йорк : Wiley.
  • Саймон, Герберт А.; Андо, Альберт (1963), «Агрегация переменных в динамических системах», в книге Альберта Андо; Франклина М. Фишера; Герберта А. Саймона (ред.), Очерки о структуре моделей социальных наук , Кембридж, Массачусетс: MIT Press, стр.  64–91
  • Саймон, Герберт А. (1996), «Архитектура сложности: иерархические системы», в книге Герберта А. Саймона (ред.), Науки об искусственном (2-е изд.), Кембридж, Массачусетс: MIT Press, стр.  183–216
  • Слезак, Доминик; Синак, Петр; Война, Аркадиуш; Вроблевски, Якуб (2013), «Две интерпретации грубых приближений, связанные с базой данных: организация данных и выполнение запросов», Fundamenta Informaticae , 127 ( 1–4 ): 445–459 , doi : 10.3233/FI-2013-920.
  • Тинг, Кай Мин (1994), Дискретизация непрерывных атрибутов и обучение на основе экземпляров (Технический отчет № 491), Сидней : Basser Department of Computer Science.
  • Ван, Кэ; Лю, Бин (1998), «Параллельная дискретизация множественных атрибутов», в Springer (ред.), Труды 5-й Тихоокеанской международной конференции по искусственному интеллекту , Лондон : Springer-Verlag, стр.  250–259.
  • Ватанабэ, Сатоси (1960), «Информационно-теоретический анализ многомерной корреляции», IBM Journal of Research and Development , 4 (1): 66–82 , doi :10.1147/rd.41.0066.
  • Ватанабэ, Сатоси (1969), Знание и догадка: количественное исследование вывода и информации , Нью-Йорк : Wiley.
  • Witten, Ian H.; Frank, Eibe (2005), Data Mining: Practical Machine Learning Tools and Techniques (2-е изд.), Amsterdam : Morgan Kaufmann, архивировано из оригинала 27.11.2020 , извлечено 11.02.2007
  • Яо, YY (2004) «Модель разбиения гранулярных вычислений», Lecture Notes in Computer Science (готовится к публикации)
  • Яо, YY (2001). «О моделировании добычи данных с помощью гранулярных вычислений». Труды 25-й ежегодной международной конференции по программному обеспечению и приложениям для компьютеров (COMPSAC 2001) . стр.  638–643 .
  • Яо, Ию (2006). "Гранулированные вычисления для добычи данных" (PDF) . В Dasarathy, Belur V. (ред.). Труды конференции SPIE по добыче данных, обнаружению вторжений, обеспечению безопасности информации и безопасности сетей передачи данных . Архивировано из оригинала (PDF) 2007-04-18.
  • Яо, Дж. Т.; Яо, Й. Я. (2002). «Индукция правил классификации с помощью гранулярных вычислений» (PDF) . Труды Третьей международной конференции по грубым множествам и текущим тенденциям в вычислениях (TSCTC'02) . Лондон, Великобритания: Springer-Verlag. С.  331–338 .
  • Заде, Л.А. (1997) «К теории нечеткой информационной грануляции и ее центральному значению в человеческом мышлении и нечеткой логике» , Нечеткие множества и системы , 90:111-127
  • Zighed, DA; Rabaséda, S.; Rakotomalala, R. (1998), "FUSINTER: метод дискретизации непрерывных атрибутов", Международный журнал неопределенности, нечеткости и систем, основанных на знаниях , 6 (3): 307–326 , doi :10.1142/s0218488598000264.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Granular_computing&oldid=1229680760"