gildot

Topo
Sobre
FAQ
Tópicos
Autores
Preferências
Artigos
Sondagens
Propor artigo


8/3
gildicas
9/30
jobs
10/9
perguntas
10/25
press

 
Autocategorize de documentos
Contribuído por AsHeS em 12-02-03 22:43
do departamento dos organizados
perguntas mvalente escreve "Depois de muitos anos a tentar manter uma estrutura de folders/pastas/directorias/directorios com nexo para organizar os mui e variados documentos que residem no disco, acabei por entregar os pontos e desistir. Recentemente, interessado em resolver o problema automaticamente com software de autocategorização, descobri que existem exemplos desse tipo de produtos, mas nenhum deles open source ou, pelo menos, disponivel para download/teste."

" As notorias excepções são o Gnowledge (open source initiative, mas sem nada de palpavel para uso) e o Ultraseek (comercial, ex-motor de indexacao do Infoseek, curiosamente feito em Python, que diz que faz autocategorização mas que na realidade não o faz).
O que estranho mais é o facto de estar disponivel um paper com o algoritmo de autocategorização usado pela NSA (Echelon?) para "ler" os jornais mundiais, pelo que uma implementação não deveria estar muito distante...

A pergunta impõem-se: há por ai algum leitor que possa dar info/links adicionais e/ou recomendar software que faça o desejado (ie abstrair de uma colecção de documentos uma organização por categorias/tópicos)?

TIA e Cumprimentos

Mario Valente

Seminários "Banda Larga & Segurança" | Writing more efficient PHP  >

 

gildot Login
Login:

Password:

Referências
  • Gnowledge
  • Ultraseek
  • algoritmo de autocategorização
  • usado pela NSA (Echelon?)
  • mvalente
  • automaticamente com software de autocategorização
  • existem exemplos desse tipo de produtos
  • Mais acerca perguntas
  • Também por AsHeS
  • Esta discussão foi arquivada. Não se pode acrescentar nenhum comentário.
    Interessante... (Pontos:4, Informativo)
    por lml em 13-02-03 0:50 GMT (#1)
    (Utilizador Info)
    isto é um problema que, pelo menos na minha experiência, persegue quase toda a gente e que não é muito falado.

    Como disseste há algum software comercial por aí, Open Source ou software gratuíto não parece haver muito.
    Até agora o que encontrei que me despertou interesse foi o TheBrain, que tem o grande inconveniente de so funcionar em Windows.
    Mais interessante (pelo menos em termos de ser mais multi-plataforma) é o newdocms para KDE, que ainda tem o bónus de ter sido criado por um Português. Infelizmente ainda está na versão 0.1...

    Numa questão relacionada, não para todo o tipo de documentos, apenas para mail, descobri há uns tempos o Zoë.
    É uma ideia brilhante que és capaz de achar interessante, directamente da página:

    "The goal here is to do for email (starting with your personal mailbox) what Google did for the web... The Google principle: It doesn't matter where information is because I can get to it with a keystroke. So what is Zoë? Think about it as a sort of librarian, tirelessly, continuously, processing, slicing, indexing, organizing, your messages. The end result is this intertwingled web of information. Messages put in context. Your very own knowledge base accessible at your fingertip. No more "attending to" your messages. The messages organization is done automatically for you so as to not have the need to "manage" your email."

    Re:Interessante... (Pontos:4, Informativo)
    por mvalente em 13-02-03 1:39 GMT (#2)
    (Utilizador Info) http://www.ruido-visual.pt/
    Agradecido pelos links, mas nao sao o q estou à procura. Já conhecia o TheBrain: nao faz automatic abstraction, és tu q tens de criar os topicos e associar-lhes os documentos; o newdocms baseia-se numa tecnica simples: quando se grava um documento tem de se lhe associar keywords, atraves das quais depois se pode fazer a abstraccao; obviamente nao é isto que pretendo, porque os documentos ja' existem nao quero voltar a abrir e grava-los com keywords nem muito menos pretendo dar keywords para todos os documentos que crio; o Zoe é giro, mas é mais um motor de pesquisa tipo Google (como eles dizem), não tendo mais uma vez a capacidade de abstracção automatica de topicos.

    Cumprimentos

    Mario Valente

    Re:Interessante... (Pontos:1)
    por lml em 13-02-03 16:08 GMT (#20)
    (Utilizador Info)
    Depois de ler o artigo original
    Re:Interessante... (Pontos:1)
    por lml em 13-02-03 16:29 GMT (#21)
    (Utilizador Info)
    Depois de ler o artigo original sobre autocategorização, li algumas partes na diagonal, parece-me que é uma técnica que foi pensada para ser usada apenas em documentos de texto e em grande quantidades. O autor, aliás, refere que a técnica seria muito difícil de usar numa intranet...
    Estás a procurar uma solução semelhante mas que funcione num computador pessoal ou num pequeno conjunto/rede de computadores? Não será isso difícil, tendo em conta aquilo que o autor refere sobre intranets? A um nível pessoal as complicações seriam ainda maiores se quisesses incluir imagens, filmes, código, programas e não ter que obedecer a regras sobre que tipo de formatos ou conteúdo os ficheiros têm...

    Presumi que quando falaste em documentos e organizar directorios estavas a abranger todo o tipo de ficheiros, será que me enganei? Mas organizar apenas texto não livra a maior parte das pessoas do confusão que acaba por resultar de uma organização hierarquica.
    Pensei logo em implementeções de filesystems, ou abstracções sobre o filesystem, baseadas em base de dados utilizando metadata.

    De facto o Zoe não tem uma capacidade de abstracção automática por tópicos, mas a mim não me parece que essa fosse a melhor maneira de o fazer... Como é que ele saberia por exemplo que mails vindos de certo sítio deveriam ser incluídos no tópico "trabalho" ou no tópico "desinteressante"? Não bastaria olhar para a frequência de palavras, nem procurar conjuntos de palavras... Depois, caso ele gerasse os tópicos automaticamente, terias uma enorme quantidade de tópicos que provavelmente não corresponderiam aos tópicos que tu atribuírias aos mails.
    O trabalho que poupavas a não atribuir tópicos seria perdido a tentar compreender os tópicos criados pelo sistema.
    Parece-me que puder fazer uma pesquisa por data ou palavras e depois organizar por subject, sender, data e por aí fora torna as coisas bem mais simples.

    Autonomy. (Pontos:3, Informativo)
    por leitao em 13-02-03 10:52 GMT (#6)
    (Utilizador Info) http://scaletrix.com/nuno/
    Ja' sei que queres software open-source, mas o melhor motor de categorizacao (embora comercial) e' o da Autonomy.


    "Arguing on the Internet is like running in the Special Olympics -- Even if you win you're still retarded."

    Re:Autonomy. (Pontos:2)
    por mvalente em 13-02-03 11:33 GMT (#8)
    (Utilizador Info) http://www.ruido-visual.pt/
    Pois, eu sei do Autonomy e sei que é dos melhores (duvidando que seja o melhor; vide por exemplo o Northern Light...). De qq forma é como dizes: nem sequer tem um online demo :-) ou uma versao para funcionar com um numero reduzido de documentos ou por um numero de dias.

    Cumprimentos

    Mario Valente

    Re:Autonomy. (Pontos:2)
    por leitao em 13-02-03 11:39 GMT (#10)
    (Utilizador Info) http://scaletrix.com/nuno/
    O Northern Light usa inferencia bayesiana ? E' isso o que faz a tecnologia da Autonomy unica -- usa DSP e "bayesian analysis" para categorizar qualquer tipo de informacao -- desde documentos, a voicemails. Ver aquilo a funcionar e' simplesmente inacreditavel -- mas concordo que nao e' exactamente um produto acessivel.


    "Arguing on the Internet is like running in the Special Olympics -- Even if you win you're still retarded."

    usa as técnicas anti-spam (Pontos:3, Interessante)
    por cgd em 13-02-03 11:09 GMT (#7)
    (Utilizador Info)

    Bom, se bem percebo o que queres, parece-me uma tarefa mais ou menos impossível :-) não tanto pela classificação, mas mais pela sua correcção. Como é que tens a certeza que o doc x que o sistema classificou no tópico y está certa? ...

    Dito isto, talvez o seguinte te interesse. Há uns tempos começou-se a popularizar uma nova técnica de combate ao mail spam, baseada em redes Bayesianas(?). A ideia é simples: usa-se uma grande quantidade de dados spam para "ensinar" o sistema. Quando chega uma mensagem nova, confrontamo-la com os dados entretanto aprendidos e o programa dá-nos uma probabilidade dessa mensagem ser spam. A ideia pode ser generalizada para N tópicos. O catch é o seguinte: tens que programar numa fase inicial cada um dos tópicos, i.e. pegar em grandes quantidades de dados de cada tópico e "ensiná-los" ao sistema. E quando os novos docs forem submetidos, tens apenas a probabilidade de se inserirem em cada um dos tópicos. Cada documento pode até ter uma probabilidade alta para dois ou mais tópicos diferentes (isso até pode ser bom, porque um texto de desenvolvimento de grandes projectos SW encaixa tanto em gestão como em engenharia de software, por exemplo).

    links:
    artigo de paul graham que deu origem a esta senda.
    bogofilter uma implementação por eric raymond (orientada ao spam)
    automated topic classification :-)
    Bayesian Network Classifier Toolbox mais genérico e complexo
    dbacl nesta página há mais soft, saca o dbacl. este é apropriado para categorizar conteudos.

    Dos urls de cima, o único com que brinquei foi o DBACL, há uns tempos, e não tive (alem de paciência) muita sorte. O tipo dava-me probabilidades algo estranhas, mas talvez agora já tenha melhorado (ou o programa ou eu).


    -- carlos

    Re:usa as técnicas anti-spam (Pontos:2)
    por leitao em 13-02-03 11:43 GMT (#11)
    (Utilizador Info) http://scaletrix.com/nuno/
    Um metodo que talvez te interesse, e que e' de facto interessante e' treinar um motor usando algoritmos simples de compressao. Este artigo explora isto, e da' exemplos utilizando o gzip (janela de compressao de 64KBytes) e o bzip (janela de 900KBytes).


    "Arguing on the Internet is like running in the Special Olympics -- Even if you win you're still retarded."

    Re:usa as técnicas anti-spam (Pontos:2)
    por cgd em 13-02-03 12:15 GMT (#13)
    (Utilizador Info)

    Já conhecia esse artigo (aliás, o do kuro5hin) thks, e não me impressionou muito, antes pelo contrário :-) A análise do conteúdo é praticamente cega, o algortimo de compressão apenas "mede" a redundância do texto para o classificar como spam. Provavelmente código copy-pasted (como não é assim tão infrequente ver) era todo classficado como spam :-)


    -- carlos

    Re:usa as técnicas anti-spam (Pontos:2)
    por mvalente em 13-02-03 11:52 GMT (#12)
    (Utilizador Info) http://www.ruido-visual.pt/
    parece-me uma tarefa mais ou menos impossível :-) não tanto pela classificação, mas mais pela sua correcção. Como é que tens a certeza que o doc x que o sistema classificou no tópico y está certa?

    Se leste os links dados e/ou o paper, ja deves ter percebido que a tarefa é perfeitamente possivel.

    Pensa numa coisa: imagina que defino eu o topico XML; e que digo que todos os documentos onde apareça a palavra XML pertencem ao topico com o mesmo nome. Basico, não e' ? Entao qual é a diferença de fazer ao contrario, ou seja,, deixar o computador obter uma lista de todas as palavras, eliminar as stopwords e as pouco frequentes e obter uma "lista de palavras que aparecem muito" a partir da qual se constroi o conjunto de topicos ? Esta 2a forma é equivalente à 1a, so que feita pela ordem inversa. Com alguma estatistica (frequencia de palavras e teorema de Bayes) essa tarefa pode ser automatizada. E depois pode ser extendida a grupos de 2 palavras, a grupos de 3 e a grupos de 4, obtendo-se assim uma lista de topicos mais precisa (ex: video games)

    Há uns tempos começou-se a popularizar uma nova técnica de combate ao mail spam, baseada em redes Bayesianas(?).
    A ideia pode ser generalizada para N tópicos. O catch é o seguinte: tens que programar numa fase inicial cada um dos tópicos

    A tecnica de usar o teorema de Bayes (que me permite calcular a probabilidade de A dado C a partir da probabilidade de C dado A) já é antiga e precisamente começou por ser usada na classificação de documentos (o chamado algoritmo naive Bayes); recentemente começou a ser usada para classificar spam.

    O seu problema é de facto o que referes: é preciso primeiro criar um grupo de documentos, dizer que pertencem ao topico X (ex: spam) e ensinar o "sistema" que depois pode validar se um documento D pertence ou nao a X. Isto nao me resolve o problema: nao quero ser eu a definir os topicos...

    Se estiveres interessado no uso do "naive Bayes" para classificação de documentos aqui está uma boa explicação com source em Perl. Sofre do mesmo problema que os links que deste e que agradeço: precisam de um training set inicial e de uma definicao humana do(s) topico(s).

    Cumprimentos

    Mario Valente

    Re:usa as técnicas anti-spam (Pontos:3, Esclarecedor)
    por cgd em 13-02-03 12:26 GMT (#14)
    (Utilizador Info)

    Nota que o que eu disse era que praticamente impossível é garantir a correcção do sistema. Mesmo que faças o trabalho de indução reversa como dizes, é provável que acabes com documentos classificados em categorias erradas. Por exemplo, acho dificil um sistema conseguir produzir automaticamente a categoria "programacao C", e mesmo criando-a, não aparecer lá lixo. Por exemplo, o teu post poderia lá aparecer (porque aparecem alguns "C"'s isolados) se tivesse mais uma ou outra keyword (programar,while) e não diz respeito a programação C.

    Já agora, dos links que mencionei o 'automated topic classifier' parece fazer exactamente o que queres (não precisa da fase de aprendizagem). Mas não é um sistema de produção. Nem sequer vem distribuido num "bundle".


    -- carlos

    Re:usa as técnicas anti-spam (Pontos:2)
    por mvalente em 13-02-03 14:40 GMT (#16)
    (Utilizador Info) http://www.ruido-visual.pt/
    Por exemplo, o teu post poderia lá aparecer (porque aparecem alguns "C"'s isolados) se tivesse mais uma ou outra keyword (programar,while) e não diz respeito a programação C.

    O meu post nao apareceria numa potencial categoria "programação C" por 2 razoes: 1o porque, como dizes, nao tem la' nenhuma keyword que indique nesse sentido; 2o porque, mesmo que tivesse uma ou varias dessas keywords, a sua frequencia nao iria ser congruente com a frequencia das mesmas keywords inclusas nos outros documentos candidatos a constituirem a categoria "programacao C". Ou seja, nao seria o facto de o meu post ter 40 ou 50 Cs e 1 ou 2 "programar" que o iria incluir na categoria "programacao C"; para ele ser incluido teria de ter valores proximos dos outros documentos constituintes da categoria (admitamos 20 ou 30 Cs e 14 ou 15 "programar"); um documento onde por exemplo aparecesse 20 ou 30 Cs e 2 ou 3 "programar" nao seria incluido na categoria "programacao C" já que, por exemplo, o facto de aparecer a palavra "vitamina" 20 vezes no mesmo documento o tornava melhor candidato para uma categoria "vitaminas" ou "vitamina C".

    Cumprimentos

    Mario Valente

    Classificação dirigida vs classificação automática (Pontos:3, Interessante)
    por joaobranco em 13-02-03 14:56 GMT (#17)
    (Utilizador Info)
    Devo avisar que não li os artigos, e se o que eu indico embaixo já tiver sido tratada lá, podem-me mandar RTFA (se quiserem ser amáveis, podem indicar-me exactamente qual dos artigos é que devo ler).

    A ideia que é proposta para classificação automática parece-me ter o problema potencial da explosão combinatória... De qualquer forma, não me parece que os problemas sejam da mesma ordem de dificuldade:
    • classificação dirigida (por keywords, tópicos, whatever): acaba por ser um problema de validação -> este documento possui esta característica? Logo, provavelmente pode ser resolvido por um algoritmo em tempo polinomial.
    • classificação automática (como propões, por detecção de todos os conjuntos de características "interessantes"): é um problema de partição/subsets. Provavelmente não pode ser resolvido em tempo polinomial (NP).
    Qual é a solução para este problema? De uma forma ingénua, pode-se usar uma heurística -> usar um subconjunto dos documentos para um treino prévio (detecção de características) - por exemplo escolher apenas os documentos mais acedidos e/ou os mais recentemente usados. Isso permite combinar os dois tipos de problemas e obter um provavelmente mais simples (mesmo que não garanta a detecção de todos os subconjuntos interessantes).

    De qualquer forma parece-me um problema muito engraçado.

    Cumps, JB

    Mais uma referencia... (Pontos:2)
    por mvalente em 13-02-03 20:11 GMT (#22)
    (Utilizador Info) http://www.ruido-visual.pt/
    Acabei de receber a revista Technology Review do MIT que traz um artigo sobre o assunto e o uso deste tipo de software pelos governos e policias. Tb pode ser lido online. Refere mais software que eu nao conhecia mas que, para variar, nao está acessivel para testes.

    Cumprimentos

    Mario Valente

    Re:coltura -- PARABÉNS (Pontos:1, Engraçado)
    por Anonimo Cobarde em 13-02-03 10:36 GMT (#4)
    Parabéns! Atribuo-te a GMMA ( Gigantesca e Medonha Medalha ASCII) de comentário mais despropositado da semana no gildot!!

                  _______________
                |@@@@|-----|####|
                |@@@@|-----|####|
                |@@@@|-----|####|
                \@@@@|-----|####/
                  \@@@|-----|###/
                    `@@|_____|##'
                              (O)
                        .-'''''-.
                    .'--*-*-*--`.
                  :--*--------*--:
                :-~----GMMA----~-:
                :-~----AWARD---~-:
                  :--*--------*--:
                    `.--*-*-*---.'
                        `-.....-'

    P.S.: o gidot não aceita e destroi a ascii art!!
    Re:coltura -- PARABÉNS (Pontos:2)
    por jmce em 13-02-03 12:34 GMT (#15)
    (Utilizador Info) http://jmce.artenumerica.org/
    Para desenrascar, pode-se usar <tt>...</tt>, <br> e &nbsp;...
    Re:coltura (Pontos:2)
    por mvalente em 13-02-03 11:35 GMT (#9)
    (Utilizador Info) http://www.ruido-visual.pt/
    Eu sabia que eras cota

    Obviamente, não me conheces...

    Cumprimentos

    Mario Valente

    Re:Mas farão os resultados sentido? (Pontos:2)
    por mvalente em 13-02-03 15:59 GMT (#19)
    (Utilizador Info) http://www.ruido-visual.pt/
    Pelo que eu me lembro dos meus tempos de estudante de doutoramento, o problema de usar algoritmos de classificação automáticos é o de os resultados fazerem sentido

    Se calhar, e pelo que dizes, desde esses tempos os algoritmos ja melhoraram :-) Nota que o paper que eu indico é de 1995... muito recente portanto. E acho que a prova que melhoraram e que fazem sentido é o facto de existirem produtos comerciais e esta ser uma area de grande interesse por parte de governos, investigadores e empresas.

    Por exemplo, o programa pode decidir criar a categoria "textos com a palavra 'de'", que qualquer humano consideraria inútil.

    Pelos vistos no na altura do doutoramento ainda nao se falava de stopwords e da eliminacao de palavras inuteis na indexacao de documentos.

    Ou seja, Mário, talvez o problema devesse ser "qual das tuas pastas com documentos é mais parecida com este documento novo?"

    Sim, essa é a tecnica já referida dos filtros bayesianos que é usada actualmente em alguns sistemas anti-spam. Assume que já existe um conjunto de documentos organizado por topicos pre-definidos. Nao é isso do que se trata e nao é isso do que estou à procura.

    Cumprimentos

    Mario Valente

     

     

    [ Topo | FAQ | Editores | Contacto ]