40. SBAI-Simpésio Brasileiro da Automação Inteligente, São Paulo, SP, 08-10 de Setembro de 1999

ILROS: ·UM SISTEMA DE APRENDIZADO DE MÁQUINA. PARA DOMíNIOS INCOMPLETOS

Joaquim Quinteiro UchôaUFLA - Univers idade Federal de LavrasDEX- Departamento de Ciências Exatas

Caixa Postal 3737200-000 Lavras - MO

e-mai! : joukim@comp.ufla.br

Resumo: A Teoria de Conjuntos Aproximados (TCA) tem sidoutiliZada em muitas áreas de pesquisa, principalmente naquelasrelacionadas à representação de conhecimento incompleto eaprendizado de máquina. Este artigo apresenta o sistemaILROS que disponibiliza, além de várias funções, aimplementação de uma versão otimizada do algoritmo deaprendizado de máquina conhecido como RSI. O algoritmoRSl é baseado em conceitos da TCA e viabiliza o aprendizadoem domínios incompletos. Apresenta também uma avaliaçãoempírica do desempenho do ILROS em alguns domínios deconhecimento. .

Palavras-chaves: conjuntos aproximados, aprendizado emdomínios incompletos, aquisição automática de conhecimento.

Abstract: Rough Set Theory (RST) has been used in manydifferent research areas, mainly in those related to therepresentation of incomplete knowledge and machine learning.This papel' presents ILROS, a system that implements , besidesother functions, an ·optimized version of a machine learningalgorithm known as RS1. The RS1 algorithm is based on someRST concepts and deals with learning in incomplete domains.It also presents an empirical evaluation of ILROS' performancein a few knowledge domains.

Keywords: rough sets, learning in incomplete domains ,automatic knowledge acquisition.

1 INTRODUÇÃOA Teoria de Conjuntos 'Aproximados (TCA) foi proposta em[Pawlak (1982)] como uma nova ferramenta matemática paratratamento de incerteza e imprecisão, tendo sido usada ,posteriormente, para subsidiar o desenvolvimento de técnicaspara classificação aproximada em aprendizado indutivo demáquina. De uma maneira simplista, conjuntos aproximadospodem ser considerados conjuntos com fronteiras nebulosas, ouseja, conjuntos que não podem ser caracterizados precisamentecomo função do conjunto de atributos disponível. A TCA temsido utilizada em Inteligência Artificial principalmente nasáreas de representação de conhecimento incerto , aprendizadoindutivo, data mining, sistemas de suporte à decisão e sistemas

314

Maria do Carmo NicolettiUFSCar - Universidade Federal de São Carlos

DC - Departamento de ComputaçãoCaixa Postal 676

13565-905 São Carlos - SPe-mai!: marian@cse.unsw.edu.au

de controle em manufatura. A abordagem da TCA pararepresentação de conceitos vagos e de incerteza tem relações ealguns paralelos com a Teoria de Conjuntos Fuzzy [Zadeh(1978)]. .

Esse trabalho descreve o ILROS, um sistema indutivo deaprendizado de máquina, baseado na TCA que, além dedisponibilizar a determinação de uma série de medidas .propostas pela TCA para a avaliação de um determinadodomínio de conhecimento, disponibiliza também umsubsistema de aprendizado de máquina, que permitegeneralizar o conhecimento disponível. Tal subsistema é .baseado em uma versão otimizada , parte da proposta ILROS,do algoritmo RSI [Wong (1986)] . O artigo está organizado daseguinte forma: na Seção 2 são apresentados os principaisconceitos da TCA e descritas as medidas mais relevantespropostas na teoria, que são necessários para subsidiar aapresentação do sistema. Na Seção 3 é apresentado o algoritmode aprendizado indutivo conhecido como RSl , no qual sefundamenta a versão otimizada por nós proposta, chamada deRS1+. A Seção 4 descreve o sistema ILROS, caracterizando edetalhando suas principais funções, bem como descreve algunsexperimentos realizados com o sistema e os resultados obtidos.A Seção 5 apresenta as conclusões do trabalho realizado eidentifica as próximas etapas para a sua continuidade.

2 NOÇÕES BÁSICAS DA TEORIA DECONJUNTOS APROXIMADOS

Seja U um conjunto universo. Um espaço aproximado é um parordenado A=(U,R), onde R é uma relação de equivalênciasobre U, denominada relação de indiscernibilidade. Dados x,ye R, se xRy então x e y são indiscemiveis em A, ou seja, aclasse de equivalência definida por x é a mesma que a definidapor y, i.e., [X]R = [y]R'

As classes de equivalência por R em U sãodenominadas conjuntos elementares. Se X é um conjuntoelementar, des(X) denota a descrição dessa classe deequivalência. Essa descrição é função do conjunto de atributosque define R. Note que, dados x,y eE, onde E é um conjuntoelementar .em A, x e y são indiscemíveis, i.e., no espaço

Exemplo 1. Seja o SRC apresentado em [Pawlak (1991)] erepresentado pela Tabela 1. Nesse caso, U={XhX2, ... ,X7},Q={a,b,c,d,e}, V. = Vb = Vd = Ve= {O,I,2} e Vc =.{O,2}. NesteSRC tem-se: p(xha)=l, p(x2,b)=O, p(xs,d) = 2, p(x7,e) = 2.

Dado um SRC identificado por S=(U,Q,V,p), é importanteobservar que cada subconjunto de atributos P ç;;; Q define umúnico espaço aproximado A=(U;P), onde P é a relação deindiscemibilidade (equivalência) induzida por P.

Exemplo 2. Considere o SRC do Exemplo I e P = {e}. Nestecaso tem-se que os elementos Xl e X2 são indiscerníveis comrelação a P pois possuem o mesmo valor. Ainda, A=(U, P) éum espaço aproximado e seus conjuntos elementares são E1 =

{X3.X4} {XS,Xó,X7}'

40. SBAI- Simpósio Brasileiro de Automação Inteligente . São Paulo, SP, 08-10 de Setembro de 1999

A=(U,R) não se consegue distinguir x de y, pois des(x) = é uma função de descrição tal que p(x,q) E Vq,

des(y) = desfE). Um conjunto definível em A é qualquer união para x E U e q E Q. Um SRC pode ser visto como umafinita de conjuntos elementares. Seja A=(U,R) um espaço caracterização formal de um espaço aproximado.aproximado e seja X ç;;; U um subconjunto arbitrário de objetosde U. Com o objetivo de verificar quão bem o conjunto dedescrições {des([x]R), x E U}, reflete as funções de pertinênciade objetos a X, são definidas:

(2) a aproximação superior de X em A, AA'sup(X), como aunião de todos QSconjuntos que possuem intersecção não vaziacom X, ou seja. é o menor conjunto definível em A contendoX,i.e.,

(I) a aproximação inferior de X ,em A, AA.in!<X), como a uniãode todos os conjuntos elementares que estão contidos em X,i.e., .

AA.sup(X) = {x E UI [X]R (] X 0}

AA.in!<X) = {x E UI [X]R c X}

Dado um espaço aproximado A=(U,R) e Xç;;;U, podem seridentificadas as seguintes regiões:

• região positiva de X em A, POSA(X)= Ainr (X)

• região negativa de X em A, negA(X) = U - A,up(X)

• região duvidosa de X em A, duvA(X) = Asup(X) - Ainr(X)

Além disso são definidas as seguintes medidas:• medida interna de X em A, CilA.inr(X) = IAA.in!<X)I. onde /YI

representa a cardinalidade do conjunto Y

• medida externa de X em A.CilA'sup(X) = IAA.sup(x)1• qualidade do. aproximação inferior de X em A,

YA.inf = CilA.in!<X)/IUI

• qualidade da aproximação superior de X em A,YA.sup = CilA.sup(X)!IUI

• acuracidade de X em A, CilA = ICilA.inr(X)IIICilA.sup(X)1

Seja A=(U,R) um espaço aproximado e seja Xç;;; U. O conjuntoX pode ou não ter suas fronteiras claramente definidas emfunção das descrições dos conjuntos elementares de A. Issoleva ao conceito de conjuntos aproximados: um conjuntoaproximado em A é a família de todos os subconjuntos de Uque possuem a mesma aproximação inferior e a mesmaaproximação superior em A. Ou seja , possuem a mesma região, positiva, negativa e duvidosa.

Nas notações utilizadas, quando o espaço aproximado forconhecido e não houver risco de dubiedade, a referência aoespaço será abolida. Por exemplo, ao invés de AA.sup(X) seráusado Asup(X).

Os conceitos da TCA são utilizados principalmente no contextode Sistemas de Representação 'de Conhecimento. Um Sistemade Representação de Conhecimento (SRC) é uma 4-uplaS=(U,Q,V,p), onde U é o universo finito de S. Os elementos deU são chamados objetos, que são caracterizados por umconjunto de atributos - Q - e seus respectivos valores. Oconjunto de valores de atributos é dado por V = UVq , onde

qeQ

Vq é o conjunto de valores do atributo q. Por sua vez,

Tabela 1 - SRC onde U={Xl,x2,...X7} e Q={a,b,c,d,e}U a b c d eXl 1 O O 1 1X2 1 O O O 1XJ O O O O OX4 I I O I O

1 ' I O 2 2Xi; 2 2 O 2 2X7 2 2 2 2 2

Dado um espaço aproximado A=(U, P), definido por umsubconjunto de atributos P ç;;; Q em um sistema derepresentação de conhecimento S=(U,Q,V,p) e X ç;;; U, define-se o índice discriminante de X em relação ao subconjunto deatributos P s;;Q, notado por ap(X), como uma medida do graude certeza na determinação da pertinência de um elemento deU ao conjunto X, de acordo com os atributos de P, dada por :

Note que a definição do índice discriminante é uma medidaobtida a partir do número de elementos que pertencem à regiãoduvidosa de X. Se essa região for vazia, o índice discriminantede X é 1, Le., o melhor possível. Por outro lado, se ela for opróprio U, tal índice resulta em zero, i.e.• não existe cornodiscriminar os elementos do conjunto X, no sistema, usando oconjunto de atributos P.

No contexto da TCA o interesse recai, principalmente, sobretabelas de decisão, um tipo particular de SRC. Uma tabela dedecisão é um SRC onde 'os atributos de Q são divididos emcondições e decisões. Tem-se então 'Q = C u D, onde C é oconjunto das condições e D, o conjunto das decisões. Cornogeralmente o conjunto D é unitário, uma tabela de decisão édescrita por S=(U,Cu{õ},V,p} , onde U e V são tais como numSRC, C é o conjunto de condições e Õé o atributo de decisão.De urna forma geral urna tabela de decisão é utilizada para arepresentação da classificação feita por um especialista nodomínio de conhecimento; nela C é o conjunto decaracterísticas que descrevem uma situação e Ôé o resultado daanálise do especialista. Por Classs(Ô) entende-se a classificaçãode S, i.e., a farrn1ia de conjuntos elementares do conjuntoaproximado induzido por {S}.

315

40. SBAI- Simpósio Brasileiro de Automação Inteligente, São Paulo, SP, 08·10 de Setembro de 1999

Exemplo 3. Seja S o SRC do Exemplo 1. Seja e o.atributo dedecisão em S, i.e., {ô] = {e}. S é uma tabela de decisão, ondeC={a,b,c,d}. Os conjuntos elementares do espaço aproximadoinduzido por C são {x.}, {X2}, {X3}, {X4}, [xj], {X6}, {X7}' Porsua vez, Classs(e) = {{XJ,X2},{X3,X4} ,{XS,X6,X7}}'

Dada uma tabela de decisão S=(U,Cu{ô} ,V,p}, é importanteverificar o quão bem a família de conjuntos elementaresinduzidos pelas condições P ç;;C espelha a farrulia de conjuntoselementares induzidos por {ô}. Para isso, considerando oespaço aproximado induzido por P, são definidas :

(1) região positiva de o induzida por P, pos(P,ô)UAp -i,r(X)

Xe C1asss(õ)

(2) grau de dependência de o com relação a P,K(P,Ô) = Ipos(P, ôWIUI

(3) fator de significãncia de um atributo a E P, com relação àdependência existente entre O . e P,FS(a,P,ô) = (K(P,Ô)-K(P-{ a},ô))!K(P,ô), se K(P,Ô) > O.Diz-se, ainda com respeito a uma tabela de decisãoS=(U,Cu{ô},V,p) e P ç;; C, que P é independente com relaçãoà dependência existente entre Ôe P se, para todo subconjuntopróprio R c P, for verdade que pos(P,ô) * pos(R,õ), i.e., K(P,Õ)* K(R,ô). Caso haja algum R c P tal que pos(P,õ) = pos(R,ô) ,i.e., K(P,Õ) = K(R,Õ), então P é dito ser dependente com relaçãoà dependência existente entre Õe P. Um conjunto R c P é diteser um reduto de P com relação à dependência existente entre õe P se for independente com relação à dependência existenteentre õ e R, e pos(P,õ) = pos(R,õ), i.e., K(P,Õ) = K(R,õ).

Exemplo 4. Seja S o SRC do Exemplo I, onde e é o atributo dedecisão em S. A família Classs(e) foi determinada no Exemplo3. A Tabela 2 mostra o valor do grau de dependência comrelação a alguns subconjuntos de C.

Tabela 2 - Grau de dependência de alguns subconjuntosK(C.e)=717 =1 K({a,b,c} ,e)=5/7 K({a.b.d},e)=717

= 0.714 =1K({b,c,d},e)=5/7= K({a,b },e)=517= K({a,c},e)=517=0.714 0.714 0.714K({b,c},e)=4I7=0.571

Note que C é dependente e que [a.b.d] é o único subconjuntode C a possuir um reduto de C, uma vez que {a.b.d] é o únicosubconjunto com o mesmo grau de dependência de C.Examinando os valores da Tabela 2 pode se dizer que oconjunto R={a.b.d} é o único reduto do conjunto de condiçõescom relação à dependência entre õ e C. Mais ainda,K(R,ô)=I=K(C,Õ).

3 O ALGORITMO RS1 E SUA VARIANTE,RS1+

Nesta seção será apresentado o algoritmo de aprendizadoindutivo de conceitos subsidiado pela TCA conhecido comoRSI [Wong (1986)], que se baseia na determinação do índicediscriminante de atributos. A apresentação do algoritmo éessenci al para que a sua otimização por nós proposta, chamadade RS1+, possa ser entendida. Como será visto na Seção 4, osistema ILROS implementa o RS I+ como um subsistema.

316

Conforme comentado na Seção 2, 6 índice discriminante deatributos fornece o grau de certeza na determinação dapertinência de um elemento de U a um. determinado conjuntoX, utilizando o conjunto de atributos P. Com isso, caso X sejaum elemento de Classtô), o índice discriminante fornece umamedida de quão bem o espaço aproximado induzido por Pclassifica os elementos de X. Tal índice é uma medida bastantesignificativa, que promove um melhor desempenho doalgoritmo que o utiliza, quando comparado a outros índices, talcomo análise de dependência (ver, por exemplo, [Ohm(1993)]).

A partir de uma tabela de decisão o RS 1 aprende regras dedecisão que obedecem à seguinte sintaxe: (ai = v.) & ... &

I

(ak= vaJ =} (b = Vb), onde o símbolo & representa o conectivode conjunção da lógica, um seletor do tipo (ar = v.) representa

rum teste de valor de atributo e b representa o atributo dedecisão. A Figura 1 apresenta e mantém a descrição doalgoritmo RSl encontrada em [Wong (1986)]. Optamos apenaspor dividir alguns de seus passos com o intuito único defacilitar o seu entendimento. As principais melhorias emodificações acrescidas ao RSl, que deram origem à versãoRSl+foram:

1. O RSl prossegue adicionando atributos ao conjunto B',mesmo quando não há um aumento nos índices discriminantes.Isto é problemático' quando da geração de regras inconsistentes,pois o RSI irá adicionar atributos a B' (passos 4 e 5), enquantohouver atributos em C. Ou seja, o RS I não "percebe" quando aadição de atributos a B' não melhora o índice discriminante do .B' anterior. Este problema foi solucionado armazenando ovalor do maior índice discriminante para futuras comparações.Isto evita a presença de termos desnecessários em regrasinconsistentes,

2. Eventualmente, o passo 4 do RS I pode trazer oinconveniente de gerar regras com um grau de especificidademaior do que o necessário. Isso acontece quando nesse passosão encontrados dois conjuntos de atributos B' com o mesmoíndice discriminante, Com o melhoramento descrito no ítemanterior implementado, esse problema só ocorrerá com regrasconsistentes, pois o algoritmo irá adicionar atributos a B'apenas quando esse aumento significar uma maiordiscriminação da classe em questão. O problema foisolucionado . eliminando os atributos desnecessários eescolhendo um reduto de B'.

3. Quando da geração de regras, é . extremamente vantajosopossuir um mecanismo que possa avaliar a representatividadede uma regra . Isso permite, por exemplo, que quando daexistência de regras inconsistentes, se possa fazer uma seleçãodas regras mais representativas, excluindo-se as menosrepresentativas. O método discutido a seguir viabiliza isso.

Com o objetivo de permitir a análise de conjuntos aproximadosnos moldes da Teoria de Conjuntos Fuzzy, podem serencontradas na literatura da TCA, propostas de algumasfunções de pertinência aproximada. A mais promissora é aencontrada em [Pawlak (1994)] . Dados um espaço aproximadoA=(U,R), X ç;;U e x EU, o valor da pertinência aproximada dex a X, no espaço aproximado A é dado por:

40. SBAI - Simpósio Brasileiro de Automação Inteligente, São Paulo, SP, 08-10 de Setembrode 1999Em [Pawlak (1995)] é proposta a associação de um fator decredibilidade a cada regra gerada utilizando-se os conceitos daTCA. Este fator de credibilidade indicaria um grau de suporte(e de confiança) associado à regra. Nessa referência ainda, oautor sugere que a função por ele definida seja usada com essafinalidade. O processo consiste em, dada uma regra de decisão(ai = va) & ...& (am = v« ) (b = Vb)' onde a., 'H' aIO E B e B é

I rnsubconjunto da classe de condições, calcular a pertinência doelemento que gerou essa regra ao conjunto de elementos quepossuem valor Vb no atributo de decisão. Essa pertinência écalculada no espaço aproximado induzido por B. Este métodofornece o percentual dos elementos do SRC que sustentam aregra. e foi implementado no sistema ILROS . Embora a adoçãodo fator de cred ibilidade tenha apresentando bom resultados,pretendemos ainda continuar com a investigação deste aspectocom o intuito de viabilizar técnicas que promovam uma maiorhierarquização das regras geradas.

1. Calcular Classs(ô) = (XI>'.. ,Xn}, a fanúlia de conjuntoselementares do espaço aproximado induzido por (ô}

2.j=1

3. U'=U; C'=C; B=0 ; X = x, S'=(U' ,Cu( o}.V,p)4. Calcular o conjunto de índices discriminantes (ao'(X) I B'=Bu (c ), 'Vc E C'} emS'

5. Selecionar o conjunto de atributos B'=B u (c) com o maiorvalorao-(X)

6.B=B'

7. Se AO.in({X) = 0 , executarpasso 10

8 . Identificar os conjuntos elementares E = (EIo... ,E,1do espaçoaproximado induzido por B, que estão contidosemAO.in({X)

9. Para cada elemento E, E E. gerar uma regra de decisãodeterminística (consistente). Considerando que B possui matributos, então cada regra tem a forma (ai= Vai) & .. .& (a; = VaIO)

(b = Vb), onde ajo .. .,am E B. Cada seletor (a, = vak) doantecedenteé construídoda seguinte forma: ak recebeo nomedok- ésirno atributo de B e v\ recebeo valor atribuídoa Eko por esseatributo. O consequente (b = Vb) é construído de formasemelhante: b recebeo nomedo atributode decisãoe Vbrecebeovalor atribuídoa Ek por esse atributo

10. U' = U' - «U' - Ao.sup(X» u An-in({X» . X = X - An.in({X) eS' = (U',C u (o},V ,p)

11. Se U' = 0 executar passo 16

12. C' =C' -B

13. Se C' i' 0 , voltar ao passo 4

14. Identificar todos os conjuntos elementares E = (EIo.. ..E,} doespaço aproximadoinduzidopor B

15. Para cada elemento Ek E E, gerar uma regra de decisão nãodeterminística (inconsistente) de forma semelhante à descrita nopasso 9

16. j = j + 117. Se j :5; n voltar ao passo3

1a. Devolvertodas as regrasencontradas nos passos9 e 15

Figura 1 • Descrição do RSl

317

4 O SISTEMA ILROSO ILROS (lnductive Learning with ROugh Sets ) é um sistemaautomático que disponibiliza a dete rminação de dóze funçõesrelativas à caracterização da informação disponível sobre umdomínio de conhecimento bem como à sua classificação,utilizando os conceitos da TCA. São elas :

I. representação de um SRC2. aproximação inferior de um dado conjunto3. aproximação superior de um dado conjunto4. precisão de uma aproximação (acuracidade)5.dependência (ou independência) de um conjunto de atributos6. redutos de um conjunto de atributos7. grau de pertinência de um elemento a um dado conjunto8. índice discriminante de um conjunto de elementos emrelação a um conjunto de atributos9. grau de dependência de um atributo em relação a umconjunto de atributos10. fator de significância de um atributoI I . redutos de um dado conjunto de atributos com relação àdependência existente entre um dado atributo e este conjunto12. subsistema de aprendizado indutivo de máquina, queimplementa o RS I+, para a geração de regras de conhecimento

O sistema ILROS foi implementado em Borland C++ Builder eé invocado via a execução de um arquivo .exe, em ambienteWindows de 32 bits (95/98 ou NT). Durante odesenvolvimento do sistema buscou-se ao máximo isolar oambiente gráfico dos algoritmos da TCA. objetivando maiorportabilidade para outros ambientes de programação. bemcomo para outros sistemas operacionais com compiladoresC++ .

No ILROS a iteração usuário/sistema acontece via telas eacionamento de botões disponibilizados nas barras deferramentas das várias telas do sistema. A informação básicaque o sistema espera é descriç ão do domínio de dadosdisponível , que deve especificar o nome do SRC , número deelementos, número de atributos, nome dos atributos e exemplosque caracterizam o domínio, cada um 'deles descrito como umvetor de valores, separados por vírgulas.

Figura 2 - Tela inicial do sistema ILROSA tela inicial do sistema, mostrada na Figura 2. apresenta umabarra horizontal de ferramentas, com as seguintes opções: New,Open, Save, Redefine e Close. As três primeiras são relativas aoperações com o arquivo que descreve o SRC e a última,utilizada para sair do sistema. O acionamento de cada umadessas opões leva o usuário a novas telas , com novas opçõesdisponibilizadas. As doze funções elencadas anteriormenteestão disponibilizadas por meio de botões dispostos em uma

40. SBAI - Simpósio Brasileiro de Automação Inteligente, São Paulo, SP, 08-10 de Setembro de 1999

barra vertical de ferramentas, que são identificados como:Elementary Sets, Approximations, Membership, Dependence,Reducts e Rules. As funções de tais botões estão implícitas emseus próprios nomes. Seguem 'algumas considerações sobreelas.

Elementary Sets - a determinação dos conjuntos elementaresrelativos a um SRC considera o espaço aproximado induzidopor todos os atributos.

Approximations - fornece ao usuário informações sobre umdeterminado conjunto, relativas a: sua aproximação inferior,aproximação superior, acuracidade, bem .como as medidas deavaliação das aproximações, i.e., medida interna, medidaexterna e qualidade de ambas as aproximações.

Dependence - permite verificar se um conjunto de atributos édependente ou não. O uso dessa opção implica a seleção, porparte do usuário, dos atributos que farão parte do conjunto.

Reducts - permite calcular todos os redutos de um dadoconjunto de atributos selecionado pelo usuário. .

Rules - aciona o subsistema de aprendizado de máquina. Autilização dessa opção implica' o uso do RS1+, na indução deregras de decisão a partir da descrição do SRC fornecida pelousuário.

O ILROS foi avaliado em dados de domínio público, todosdisponibilizados para download em [Merz (1998)]. Os trêsdomínios inicialmente escolhidos foram Mushroom, Cal' e, Monks (optamos aqui por manter os nomes originais dosdomínios, para facilidade de identificação). As descrições maisdetalhadas dos três domínios podem encontradas naquelareferência.

Mushroom (Mu): consiste de um conjunto de dados comdescrições de 23 espécies de cogumelos das famílias Agaricuse Lepiota. Cada instância deste domínio é descrita por 22atributos, todos com valores nominais (não numéricos). Oconjunto original de dados possui 8124 instâncias, muitas delascom valores ausentes, Como o ILROS ainda não trata esse tipode dado, os testes foram realizados com um subconjunto de5936 instâncias do conjunto original.

Cal' (Car): consiste de um conjunto de dados descrevendo aaceitação de vários modelos de carros. A descrição de cadainstância é feita através de 6 atributos discretos, 4 com valoresnominais e 2 com valores nuinéricos. As' quatro possíveisclasses são: inaceitável, aceitável, bom e muito bOIIL àconjunto original, com 1728 instâncias, foi usadointegralmente.

Monks (Mo): os dados do domínio Monks são relativos àsinstâncias que descrevem um robô, usando seis atributosnominais e duas possíveis classes. Três diferentes conjuntos dedados, identificados como Monksl(Mol), Monks2 (Mo2) eMonks3 (Mo3) foram utilizados, cada um deles com 432instâncias. O que deu origem a três diferentes versões de ummesmo problema foi o processo de geração dos dados. Paracada um deles, uma determinada expressão lógica envolvendoatributos é satisfeita pelas suas instâncias.

Para cada um dos domínios de 'dados, foram realizados cincotestes e, em cada um deles. o seguinte procedimento foiadotado: o conjunto original de dados foi randomicamentedividido em dois, contendo respectivamente 75% e 25% do

318

total das instâncias. O primeiro conjunto (conjunto detreinamento) foi usado para a indução do conceito e o segundo(conjunto de teste), para a avaliação do conceito gerado. ATabela 3 apresenta as 10 características que foramcontabilizadas nos experimentos e a Tabela 4, a média dosvalores obtidos de cada uma das características, nos cincoexperimentos, para cada um dos domínios.

Devido ao pouco espaço disponível, nos limitaremos apenas aalguns comentários sobre os valores obtidos no experimentorelativo a dois domínio de dados Mushroom (Mu) e Monks3(Mo3). Mais detalhes podem ser encontrados em [Uchôa &Nicoletti (1998)] e [Uchôa (1998)].

No domínio Mu, o fato do número de elementos ter variadoentre 1 e 1.4 indica que as regras obtidas são de fácil leitura,podendo ser facilmente avaliadas por um especialista da área.O valor médio do grau de suporte, em torno de 83% indica queo sistema induziu regras relativamente "boas" (regras comrazoável poder classificatõrio), Note, entretanto, que o fato doconjunto de teste ter sido gerado randomicamente, produziuuma avaliação de apenas um pequeno percentual das regrasgeradas (uma média de 73% das regras não foram deflagradaspor qualquer instância de teste). Note também que em média18% das instâncias de teste não satisfizeram o antecedente dequalquer das regras. Sistemas .de aprendizado disponíveistratam esta situação disponibilizando uma regra default, queatribui a classe mais frequente às instâncias que não sãoclassificadas por qualquer das regras. O ILROS ainda nãoimplementa qualquer tratamento deste tipo. Os resultadosobtidos usando dados de Mo3, por sua vez, permitem dizer queou este conjunto de dados ,é bastante homogêneo ou então quea caracterização de suas classes está muito bem definida (o quepode ser deduzido a partir do fator de credibilidade e do graude suporte). Cabe aqui observar que, quando da geração dasregras, o ILROS produziu regras idênticas em todos os cincotestes realizados no domínio, alterando apenas a ordem dasmesmas.

Tabela 3 Características contabilizadasA- # regras geradas ,B- # mínimo de elementos no antecedente da regraC- # máximo de elementos no antecedente da regraD- # médio de elementos no antecedente da regraE- valor médio de credibilidade de cada regraF- desvio-padrão da credibilidade de cada regraG- valor médio do grau de suporte de cada regraH desvio-padrão do grau de suporte de cada regra1- # 'regras não deflazradas na avaliacãoJ- # elementos do conjunto de teste que nãosatisfazem o antecedente de uualcuer regra

Tabela 4. Valores médios das várias características,nos vários domínios

Mu Car MoI Mo2 Mo3A 8.8 166.4 14.6 6 12B 1 1 1 1 1C 1.4 6 2.2 1 2D 1.23 4.27 ,1.77 1 1.92E 1 0.99 0.83 0.5 1F O 0.04 0.09 0.19 OG 83.35 66.08 51.42 50 100H 27.92 36.59 41.07 22.26 OI 6.4 101.8 7.2 2.4 O ,J 270.4 O 14.8 O O

Este artigo descreve inicialmente os principais conceitos daTCA, com o objetivo de subsidiar a apresentação do sistemaILROS, um sistema automático que disponibiliza adeterminação de vários dos conceitos e medidas da TCA. OILROS disponibiliza, também; um subsistema de aprendizadoindutivo de máquina, que implementa o RS1+, uma varianteotimizada de um dos algoritmos de aprendizado de máquinadisponível na literatura.

540. SBAI- Simpósio Brasileiro de Automação Inteligente, São Paulo, SP. 08-10 de Setembro de 1999

CONCLUSÕES Uchôa, J. Q. (1998). Representação e Indução deConhecimento usando Conjuntos Aproximados.Dissertação de Mestrado. São Carlos, PPG-CC UFSCar,256p.

Uchôa, J. Q. e Nicoletti, M. C. (1998). ILROS: um Sistema deAprendizado Indutivo de Máquina Baseado emConjuntos Aproximados. Relatório Técnico doDepartamento de Computação. São Carlos, DC-UFSCar, 38p.

O uso do ILROS permite que o usuário avalie precisamente ainformação relativa ao domínio de conhecimento disponível,bem como viabiliza que tal informação possa ser generalizada,na forma de regras de decisão e utilizadas posteriormente emsistemas classificat órios.

Como continuidade do trabalho descrito neste artigo, pretende-se implementar as seguintes melhorias no algoritmo RS1+(bem como no protótipo ILROS): tratamento de dados comvalores desconhecidos e tratamento a valores contínuos. Alémdisso, como pode ser percebido na descrição do algoritmoRS1+, o processo de geração de regras é facilmenteparalelizável , pois é possível fazer chamadas independentespara cada elemento de Classtô), onde Õé o atributo de decisão.Dada essa facilidade , pretende-se disponibilizar paralelismo emfuturas implementações do protótipo, visando aumento dedesempenho do sistema. Atualmente, encontra-se emdesenvolvimento uma versão UNIX do sistema.

6 AGRADECIMENTOSApoio a este trabalho foi fornecido pela FAPESP a ambos osautores.

7 REFERÊNCIASMerz, C. J. and Murphy, P. (1998). UCI Repository of ML

Database . Irvine , CA: University of California, DICS,[http://www.ics.uci.edu/-mlearnlMLRepository.html]

Ohm, A. (1993). Rough Logic Control: a New Approach toAutomatic Control? Trondheim, University ofTrondheim, Norway, 44 p.

Pawlak, Z. (1982). Rough Sets. Intemational Journal ofComputer and Information Sciences, 11(5), pp. 341-

. 356.

Pawlak, Z. (1991) . Rough Sets: Theoretical Aspects of. Reasoning About Data. London, Kluwer.

Pawlak, Z. (1994). Hard and Soft Sets. In: W. P. Ziarko (ed.)Rough Sets , FuZzY Sets and Knowledge Discovery.London , Springer-Verlag, pp. 130-135

Pawlak, Z. (1995) . Rough Set Approach to Knowledge BasedDecision Support. .Research Report of ICS - WarsawUT, n.IO/95, Warsaw, 12 p.

Wong, S. K. M.; Ziarko, W. and Ye, R. L. (1986). Comparisonof Rough Set and Statistical Methods in InductiveLearning . International Journal ofMan-Machine Studies24, pp. 53-72 .

Zadeh, L. A. (1978). Fuzzy Sets as a Basis for a Theory ofPossibility. In: Fuzzy Sets and Systems 1, pp. 3-28.

319