Computação granular

Origem: Wikipédia, a enciclopédia livre.

Computação granular (GrC) é um paradigma de computação emergente de processamento de informações. Trata-se de processamento de entidade complexas de informação chamadas de grânulos, que surgem no processo de abstração e derivação de conhecimento de informações ou dados. De modo Geral, grânulos de informações são coleções de entidade que usualmente originam no nível numérico e são organizadas em conjunto, deviso a sua semelhança, adjacência física ou funcional, indistinguibilidade, coerência, ou semelhantes.

Atualmente, computação granular é mais uma perspectiva teórica do que um conjunto coerente de métodos e princípios. Como uma perspectiva teórica, incentiva uma abordagem dos dados que reconhece e explora o conhecimento presente em dados em vários nível de resolução ou escala. Neste sentido, ela aborda todos os métodos que fornecem flexibilidade e adaptabilidade na resolução em que conhecimento ou informação é extraída ou apresentada

Tipos de granulação[editar | editar código-fonte]

Visão de satélite de um ciclone.
Visão de satélite de Manhattan.

Como mencionado acima, computação granular não é um algoritmo ou processo; não existe um método particular que é chamado de "computação granular". Isto é, uma abordagem para observar os dados que reconhece como regularidades são diferentes e interessantes, nos dados podem aparecer aparecer em diferentes nível de granularidade, tanto quanto diferentes características se salientam em Imagem de satélite de maior ou menor resolução. Em imagens de satélite de baixa resolução, por exemplo, pode-se notar padrões interessantes de nuvens que podem representar um Ciclone ou outro fenômeno de larga escala, enquanto uma imagem de alta resolução, falha em perceber esses fenômenos em grande escala, mas em vez percebe fenômenos atmosféricos em menor escala, como um padrão interessante nas ruas de Manhattan. O mesmo é geralmente verdade em todos os dados: em diferentes resoluções ou granularidades, diferentes características ou relações emergem. O objetivo da computação granular, em última analise, é simplesmente tentar tirar proveito deste fato na concepção de sistemas mais eficazes de aprendizagem de maquina e raciocínio.

Existem vários tipos de granularidade que são frequentemente encontrados em mineração de dados e aprendizado de maquina, e iremos rever isto abaixo:

Valor de granulação (discretização/quantização)[editar | editar código-fonte]

Um tipo de granulação é a quantização de variáveis. Isto é muito comum em aplicações de mineração de dados aprendizagem de máquina em que a resolução das varáveis precisa ser reduzida para obter regularidades significativas. Um exemplo disto seria uma variável como "temperatura do lado de fora" (), que em uma dada aplicação pode ser gravada com várias casas de precisão (dependendo do aparelho de medição). No entanto, para fins de extrair relações entre "temperatura do lado de fora" e dizer, "números de aplicações de saúde do clube" (), será vantajoso para quantificar "temperatura do lado de fora" entre um pequeno número de intervalos.

Motivações[editar | editar código-fonte]

Existem várias razões inter-relacionadas para variáveis de granulação desta forma

  • Com base no conhecimento prévio, não há expectativa de que pequenas variações de temperatura (por exemplo, a diferença entre Predefinição:Convert/Dual/LoffAoffDbSoffT) poderia influenciar no comportamento de condução do número de aplicações sem saúde do clube. Por esta razão, alguma "regularidade" que nossos algoritmos de aprendizagem que poderiam detectar este nível de resolução deveriam ser espúrios, como um artefato de reajuste. Por engrossar a variável temperatura em intervalos e diferenças que podemos antecipar (baseado no conhecimento adquirido a priori) possam influenciar nas aplicações em saúde do clube, eliminamos a possibilidade de detecção destes padrões espúrios. Assim, nesse caso, reduzir resolução é um método de controle de sobreajuste.
  • Por reduzir o número de intervalos na variável temperatura (por exemplo., aumentando o tamanho do granulo), aumentamos a quantidade de dados de exemplo indexados por cada intervalo designado. Assim, por engrossar a variável, aumentamos o tamanho das amostras e conseguimos uma melhor estimativa estatística. Neste sentido, aumentar a granularidade provem um antidoto para a então chamada maldição da dimensionalidade, que um decremento exponencial no poder estatístico com incremento no número de dimensões ou cardinalidade variável.
  • Independente do conhecimento prévio, é muitas vezes o caso em que regularidades significativas (i.e., que podem ser detectadas por um dado método de aprendizagem, linguagem representativa, etc.) podem existir em um nível de resolução e não em outro.

Por exemplo, um sistema de reconhecimento de aprendiz ou um padrão simples pode tentar extrair regularidades satisfazendo o limite de probabilidade condicional como . No caso especial onde , este sistema de reconhecimento esta essencialmente detectando implicação lógica da forma  ou, em palavras, "se , então ". O sistema de habilidade para reconhecer tais implicações (ou, em geral, as probabilidades condicionais de limiar superior ) é parcialmente contingente na resolução com que o sistema analisa as variáveis.

Como um exemplo deste último ponto, considere o espaço característico mostrado a direita. As variáveis podem ser consideradas com duas resoluções diferentes.  Variável  pode ser considerada como alta (quaternária) resolução onde isto leva a quatro valores  ou como menor (binaria) resolução onde isto leva a dois valores . Similarmente, variável  pode ser considerada alta (quaternária) resolução ou como baixa (binaria) resolução, onde terá os valores  ou , respectivamente. Poderá ser notado que na alta resolução, não há implicações detectáveis na forma , uma vez que cada  é associado a mais de um , e assim, para todo , . No entanto, na baixa (binaria) resolução variável, duas implicações bilaterais poderão ser detectadas: e, para cada  ocorre se e somente se  e ocorre se e somente se . Assim, um sistema de reconhecimento de padrões buscando por implicações deste tipo iria encontrá-los na resolução variável binária, mas não seria suficiente para encontrá-las na resolução variável superior quartenária.

Problemas e métodos[editar | editar código-fonte]

Não é viável testar exaustivamente todas possíveis soluções de discretização em todas as variáveis, a fim de ver qual a combinação de soluções possui resultados mais interessantes ou significativos . Em vez disso, o espaço de características devera ser pré-processado(muitas vezes por uma analise de uma espécie de entropia), de modo que alguma orientação pode ser dada a forma como o processo de discretização deve prosseguir. Além disso, não se pode obter bons resultados, ingenuamente, analisando e discretizando cada variável de forma independente, uma vez que isso pode destruir as próprias interações que esperávamos descobrir.

Umas amostras de documentos que abordam o problema de discretização de variáveis em geral, e em particular discretização de múltiplas-variáveis, estão a seguir: Chiu, Wong & Cheung (1991), Bay (2001), Liu et al. (2002), Wang & Liu (1998), Zighed, Rabaséda & Rakotomalala (1998), Catlett (1991), Dougherty, Kohavi & Sahami (1995), Monti & Cooper (1999), Fayyad & Irani (1993), Chiu, Cheung & Wong (1990), Nguyen & Nguyen (1998), Grzymala-Busse & Stefanowski (2001), Ting (1994), Ludl & Widmer (2000), Pfahringer (1995), An & Cercone (1999), Chiu & Cheung (1989), Chmielewski & Grzymala-Busse (1996), Lee & Shin (1994), Liu & Wellman (2002), Liu & Wellman (2004).

Granulação variável (agrupamento/agregação/transformação)[editar | editar código-fonte]

Granulação variável é um termo que poderia descrever uma variedade de técnicas, a maioria das quais são destinadas a redução de requerimentos de dimensionalidade, redundância e armazenamento. Nós descrevemos brevemente algumas das ideias aqui, e apresentamos ponteiros para literatura.

Transformação variável[editar | editar código-fonte]

Uma série de métodos clássicos, como analise de componentes principais, escalonamento multidimensional, analise fatorial, e modelagem de equações estruturais, e seus relativos, caem sob o gênero de "transformação variável." Também nesta categoria tem áreas mais modernas de estudo tais quais: redução de dimensionalidade, busca de projeção, e analise de componente independente. O objetivo comum destes métodos em geral é encontrar uma representação dos dados em termos de novas variáveis, que são transformações lineares ou não lineares das variáveis originais, e em que as relações estatísticas importantes emergem. O conjunto de variáveis resultante são quase sempre menor que o conjunto de variáveis original, e portanto,  estes métodos podem ser vagamente para impor uma granulação em um espaço de características. Estes são métodos de redução de dimensionalidade, são revistos nos textos convencionais, como Duda, Hart & Stork (2001), Witten & Frank (2005), e Hastie, Tibshirani & Friedman (2001).

Variável de agregação[editar | editar código-fonte]

Uma classe diferente de métodos de granulação variável deriva mais de metodologias de data clustering  que a partir da teoria de sistemas lineares informando os métodos acima. Notou-se bastante cedo que se pode considerar "cluster" em variáveis relacionadas exatamente do mesmo jeito que se considera dados de agrupamento relacionados. Em data clustering, uma identifica um grupo de entidades similares (usando uma medida de "similaridade" adequada ao domínio), e em seguida, em algum sentido, substitui as entidades com um protótipo de algum tipo. O protótipo pode ser a média simples dos dados identificados no cluster, ou alguma outra medida representativa. Mas a ideia chave, é que em operações subsequentes, que pode ser capaz de utilizar um único protótipo para o cluster de dados (ao longo, talvez um modelo estático que descreve como exemplares são derivadas do protótipo) para substituir um conjunto de exemplares maior. Estes protótipos são geralmente, como capturar a maior parte de informação de interesse referentes as entidades .

Similarmente, é razoável perguntar se um grande conjunto de variáveis podem ser agregadas em um conjunto menor de variáveis de protótipo que capturam as relações mais relevantes entre as variáveis. Embora métodos de agrupamento de variáveis baseados em correlação linear tenham sido propostos (Duda, Hart & Stork 2001;Rencher 2002), métodos mais poderosos de agrupamento de variáveis são baseados em informação mutua entre variáveis. Watanabe mostrou (Watanabe 1960;Watanabe 1969) que, para qualquer conjunto de variáveis pode-se construir uma politônica (i.e., n-aria) árvore que representa uma série de aglomerações variáveis em que o máximo de correlação "total" entre o conjunto variável completa é a soma das correlações "parciais" exibidas por cada aglomeração de subconjunto(veja a figura). Watanabe sugere que um observador poderia participar do sistema de tal forma a minimizar a interdependência entre as partes "... Como se eles estivessem procurando uma divisão natural ou um crack escondido."

Uma abordagem prática para a construção de uma tal árvore é escolher sucessivamente para a aglomeração das duas variáveis (ou variáveis atômicas ou variáveis anteriormente aglomeradas) que têm o mais alto de informação mútua em pares (Kraskov et al. 2003). O produto de cada aglomeração é uma nova (construída) variável que reflete a  distribuição local conjunta de duas variáveis aglomeradas, e portanto, possui uma entropia igual a sua entropia conjunta . (De um ponto de vista procedural, este passo de aglomeração envolve a substituição de duas colunas na tabela de atributo-valor, representando as duas variáveis com aglomeração, com uma coluna que tem um valor único para cada combinação única de valores nas colunas substituídas (Kraskov et al. 2003). Nenhuma informação é perdida por uma dessas operações; no entanto, deve notar-se que, se está a explorar os dados de relações inter-variáveis, que geralmente, não seria desejável para fundir variáveis redundantes, desta forma, uma vez que em tal contexto é provável que seja precisamente a redundância ou dependência entre variáveis que são de interesse, e uma vez que as variáveis redundantes são fundidas, a sua relação uma à outra já não pode ser estudada.

Sistema de granulação (agregação)[editar | editar código-fonte]

Em banco de dados, aggregações (ver, por exemplo, OLAP e sistemas inteligência empresarial) resultam na transformação de tabelas de dados originais (muitas vezes chamados de sistemas de informação) nas mesas com diferentes semânticas de linhas e colunas, onde as linhas correspondem aos grupos (grânulos) da tupla original e as colunas expressam informações agregadas sobre os valores originais dento de cada um dos grupos. Essas agregações são usualmente baseadas em SQL e suas extensões. Os grânulos resultantes usualmente correspondem aos grupos de tuplas originais com os mesmos valores (ou intervalos) ao longo de algumas colunas originais pré-selecionadas.

Existem também outras abordagens em que os grupos são definidos baseando-se, por exemplo, em linhas de adjacência física. Por exemplo, Infobright implementa um mecanismo de banco em que os dados são dividido em linhas ásperas, cada uma consistindo de 64K de linhas fisicamente consecutivas (ou quase consecutivas). Linhas ásperas são automaticamente rotuladas com informações compactadas sobre seus valores em colunas de dados, muitas vezes envolvendo várias colunas e as relações multi-tabelas. Isso resulta em uma camada superior de sistemas de informação granuladas onde os objetos correspondem a linhas ásperas e atributos - para vários sabores de informação áspera. Operações de banco de dados podem ser eficientemente suportadas no âmbito de um novo framework, com um acesso às peças de dados originais ainda disponíveis.

Conceito de granulação (analise de componentes)[editar | editar código-fonte]

As origens da ideologia da computação granular podem ser encontrados na literatura dos conjuntos ásperos e conjuntos difusos. Uma das principais ideias de pesquisa de conjuntos áspero, embora de jeito nenhum única dele, é que, geralmente, a seleção de diferentes conjuntos de características ou variáveis produzirá diferentes conceitos de granulação. Aqui, como na teoria dos conjuntos rústicos elementares, por "conceito" queremos dizer um conjunto de entidades que são indistinguíveis ou indiscerníveis ao observador (i.e., um conceito simples), ou um conjunto de entidades que compõem um simples conceito (i.e., um conceito complexo). Em outras palavras, projetando um conjunto de dados (sistema de valor-atributo) em diferentes conjuntos de variáveis, reconhecemos conjuntos alternativos de classe de equivalência, "conceitos" no dado,  e estes diferentes conjuntos de conceitos será em geral favorável para a extração de diferentes relacionamentos e regularidades.

Equivalência de classes de granulação [editar | editar código-fonte]

Ilustramos com um exemplo. Considere o valor-atributo do sistema abaixo:

Exemplo de sistema de informação
Objeto
1 2 0 1 1
1 2 0 1 1
2 0 0 1 0
0 0 1 2 1
2 1 0 2 1
0 0 1 2 2
2 0 0 1 0
0 1 2 2 1
2 1 0 2 2
2 0 0 1 0

Quando o conjunto completo de atributos  é considerado, vemos que temos as seguintes sete classes de equivalência ou conceitos primitivos(simples):

Assim, os dois objetos dentro da primeira classe de equivalência, , não podem ser distinguidos uns dos outros com base nos atributos disponíveis, e os três objetos dentro da segunda classe de equivalência, , não podem ser distinguidos uns dos outros com base nos atributos disponíveis. Os cinco objetos restantes são todos discerníveis dos demais objetos. Agora, vamos imaginar a projeção do sistema de valor de atributo para o atributo  sozinho, que irá representar, por exemplo, o ponto de vista de um observador que só é capaz de detectar este único atributo. Então obtemos a seguinte estrutura de classe de equivalência mais grosseira.

Isto é, em certo ponto, a mesma estrutura de antes, mas com um menor de resolução (grãos maiores). Justamente como no caso de valor de granulação (discretização/quantização), é possível que os relacionamentos (dependências) talvez surjam em um nível de granularidade e não estarem presentes em outro. Como um exemplo disto, nós podemos considerar o efeito do conceito de granulação na medida conhecida como dependência de atributo (um parente mais simples da informação mutua).

Para estabelecer a noção de dependencia (veja também conjuntos ásperos), deixe  representam um conceito particular de granulação, onde cada  é uma classe de equivalência do conceito de estrutura induzido pelo conjunto de atributos . Por exemplo, se o conjunto de atributos  consiste do atributo  somente, como anteriormente, então o conceito de estrutura  irá ser composto de    , , e . A dependência do conjunto de atributos  em outro conjunto de atributos , , é dada por

Ou seja, para cada classe de equivalência  em , soma-se o tamanho de sua "aproximação inferior" (veja conjuntos ásperos) pelos atributos em , i.e., . Mais simplesmente, esta aproximação é o número de objetos que estão no conjunto de atributos , pode ser positivamente identificado como pertencem a meta estabelecida no conjunto . Adicionados em todas as classes de equivalência em , o numerador acima representa o número total de objetos que, com base no conjunto de atributos , podem ser positivamente categorizados de acordo com a classificação induzida por atributos . Por conseguinte, a razão de dependência expressa a proporção  (dentro de todo universo) de tais objetos classificáveis, no sentido de capturar a "sincronização" das duas estruturas conceito  e . A dependencia  "Pode ser interpretada como a proporção de tais objetos no sistema de informação para os quais é suficiente para conhecer os valores de atributos em  para determinar os valores de atributos em " (Ziarko & Shan 1995).

Tendo chegado definições agora fora do caminho, nós podemos fazer uma simples observação de que a escolha do conceito de granularidade (por exemplo, escolha de atributos) irá influenciar as dependências detectadas entre os atributos. Considere novamente a tabela de valores de atributos abaixo:

Exemplos de sistema de informação 
Objeto
1 2 0 1 1
1 2 0 1 1
2 0 0 1 0
0 0 1 2 1
2 1 0 2 1
0 0 1 2 2
2 0 0 1 0
0 1 2 2 1
2 1 0 2 2
2 0 0 1 0

Vamos considerar a dependência d conjunto de atributos  no conjunto de atributos . Ou seja, queremos saber qual proporção de objetos podem ser corretamente classificados entre as classes de   baseado no conhecimento de  . A equivalência de classes de   e de  são demonstradas abaixo.

Os objetos que podem ser definitivamente categorizados de acordo com a estrutura conceito  baseada em  são aqueles no conjunto , e uma vez que existem seis deles, a dependência de  em , . Isto pode ser considerado uma dependência interessante em seu próprio direito, mas provavelmente em um aplicação em particular de mineração de dados são desejadas dependências só que mais fortes.

Podemos então considerar a dependência do menor atributo do conjunto   no conjunto de atributos . A passagem de  para  induz o engrossamento da estrutura de classe , como será vista em breve. Desejamos novamente saber qual proporção de objetos pode ser corretamente classificado nas (agora maior) classes de  baseado no conhecimento de . A equivalência de classes do novo  e de  são demonstradas abaixo.

Claramente, tem uma granularidade mais grossa do que antes. Os objetos podem agora ser definitivamente categorizados de acordo com o conceito da estrutura  baseado em  constituindo o universo completo , e assim,  a dependencia de  em , . Ou seja, o conhecimento de adesão de acordo com a categoria do conjunto   é adequada para determinar a  associoação de categoria em  com total certeza; Neste caso poderemos dizer que . Assim, por engrossamento da estrutura conceito, fomos capazes de encontrar uma (determinística) dependência mais forte. No entanto, notamos também que as classes induzidas em  da redução da resolução necessária para obter esta dependência determinística agora são eles próprios grandes e poucos em número; como resultado, a dependência que encontramos, enquanto forte, pode ter menos valor para nós do que a dependência fraca encontrada anteriormente sob o ponto de vista da alta resolução de .

Geralmente não é possível testar todos os conjuntos de atributos par ver quais as estruturas conceito induzidas possui as dependências mais fortes, e esta busca deve ser guiada com alguma inteligência. Papéis que discutem este problema, e outros relacionando o uso inteligente da granulação, são aqueles por Y.Y. Yao and Lotfi Zadeh listado nas #References abaixo.

Granulação de componentes[editar | editar código-fonte]

Outra perspectiva no conceito de granulação pode ser obtida do trabalho em modelos paramétricos de categorias. No modelo de mistura de aprendizado, por exemplo, um conjunto de dados é explorado como uma mistura de distribuições Gaussianas (ou outras). Assim, uma grande quantidade de dados "substituída" por uma pequena quantidade de distribuições. A escolha do número de distribuições, e seu tamanho, pode novamente ser vista como um problema do conceito de granulação. Em geral, o melhor ajuste de dados é obtido pelo maior número de distribuições ou parâmetros, mas a fim de extrair padrões significativos, é necessário limitar o número de distribuições, assim deliberadamente engrossando o conceito de resolução. Encontrar o conceito de resolução "correto" é um problema complicado para os quais vários métodos foram propostos (por exemplo, AIC, BIC, MDL, etc.), e estes são frequentemente considerados sob a rubrica do "modelo de regularização".

Diferentes interpretações de computação granular[editar | editar código-fonte]

Computação granular pode ser concebido como um framework de teorias, metodologias, técnicas, e ferramentas que fazem uso de informações granulares no processo de resolução do problema. Neste sentido, computação granular é usado como um termo genérico para cobrir tópicos que tem sido estudados em vários campos isoladamente. Por examinar todos esses estudos existentes a luz do framework unificado da computação granular e extrair semelhanças deles, isto talvez seja possível por desenvolver uma teoria geral para resolução de problemas.

Em um sentido mais filosófico, computação granular pode descrever um jeito de pensar que depende da capacidade humana de perceber o mundo real sob vários níveis de granularidade (i.e., abstração) a fim de abstrair e considerar somente aquelas coisas que servem a um interesse especifico e alternar entre diferentes granularidades. Por focar em diferentes nível de granularidade, pode obter diferentes níveis de conhecimento, tal como, um grande entendimento de uma estrutura de conhecimento inerente. Computação granular é assim essencial para resolver problemas humanos, e portanto, tem um impacto muito significante na concepção e implementação de sistemas inteligentes.

Ver também[editar | editar código-fonte]

  • Rough Sets, Discretização
  • Type-2 Fuzzy Sets and Systems

Referencias[editar | editar código-fonte]