Expert System algoritmo

Question

Ho un problema algoritmico che può essere ridotto a questo compito:

Supponiamo di avere un elenco di malattie e nm sintomi.
per ogni malattia d e sintomo s, abbiamo una delle tre opzioni:

• il sintomo è positivamente correlato con la malattia: s => d
• il sintomo è correlato negativamente con la malattia: s => ~d
• la il sintomo non è correlato alla malattia

L'obiettivo dell'algoritmo è creare un elenco di domande si/no relative a s ymptoms (o anche meglio - un albero binario di domande), che può dedurre la malattia esatta in base ai sintomi.

Qualsiasi riferimento a algoritmi specifici, strumenti software pertinenti e persino gergo specifico del dominio sarebbe molto apprezzato.

Answer 1

È caso utilizzare un albero di decisione: http://en.wikipedia.org/wiki/Decision_tree_learning

Fondamentalmente trovare l'albero ottimale (cioè che ridurrà al minimo il numero medio di domande prima di poter identificare la malattia) è NP-hard.

È possibile utilizzare un algoritmo ingordo e quindi provare a ottimizzarlo (se necessario).

Ad ogni passaggio si desidera ridurre il più possibile il numero di decessi che sono ancora "possibili".

Tu sei nella parte superiore del vostro albero e in modo da avere tre possibili opzioni per un dato s, contare il numero di malattie in ogni opzione: pcncuc.

Da un lato si ha pc dall'altra nc e il uc non si può dire nulla (si può guardare a due livelli del vostro albero di avere alcune informazioni ma per ora non farlo).

Così peggiore delle ipotesi, si dispone di pc/nc + uc o pc + uc/nc, scegliere il s che minimizzano caso peggiore (cioè: lotto di un lato, solo pochi, dall'altro).

È necessario ridurre al minimo abs(pc - (nc + uc)) + abs ((pc+uc) - nc).

Ora hai il tuo s per la tua prima domanda e puoi costruire iterativamente il tuo albero.

Answer 2

Il tuo dominio è davvero "binario" o, di fatto, vorresti probabilmente utilizzare il coefficiente di correlazione per ogni coppia di sintomi/malattie come valore numerico? Ciò consentirebbe a forti correlazioni di influenzare il risultato più che debole correlazioni.

In tal caso, è consigliabile esaminare Support Vector Machines per analizzare i dati e riconoscere i motivi.

Answer 3

Se hai solo bisogno di un riferimento, dai un'occhiata al libro Russel & Norvig.Non ho la mia copia in mano in questo momento, ma posso aggiornare questa risposta con alcuni suggerimenti del capitolo domani.

Answer 4

Se ciascuna malattia presenta solo pochi sintomi, è possibile utilizzare modelli grafici per modellarne le probabilità.

http://en.wikipedia.org/wiki/Graphical_model

http://www.cs.ubc.ca/~murphyk/Software/bnsoft.html

Ma io non so se è possibile utilizzare un modello grafico per creare un albero di domande.

Answer 5

Il problema è molto simile alla questione dei batteri/antibiotici di Mycin, un precursore della tecnologia dei sistemi esperti più generalizzata basata sulle regole degli anni '80. C'erano altri programmi di diagnostica medica sviluppati con gli strumenti risultanti.

http://en.wikipedia.org/wiki/Mycin