6

我有一个算法问题可以简化为这个任务:

假设我们有一份n疾病和m症状列表。
对于每种疾病d和症状s,我们有以下三种选择之一:

  • 症状与疾病呈正相关:s => d
  • 症状与疾病呈负相关:s => ~d
  • 症状与疾病无关

该算法的目标是创建一个关于症状的是/否问题的列表(或者甚至更好 - 问题的二叉树),它可以根据症状推断出确切的疾病。

任何对特定算法、相关软件工具甚至特定领域行话的引用都将不胜感激。

4

5 回答 5

5

您的案例使用决策树:http ://en.wikipedia.org/wiki/Decision_tree_learning

基本上找到最佳树(即在您识别疾病之前将最小化问题的平均数量)是NP-hard。

您可以使用贪心算法,然后尝试优化它(如果需要)。

在每个步骤中,您都希望尽可能减少仍然“可能”的死亡人数。

你在你的树的顶端,所以你有给定的三个可能的选项s,计算每个选项中的疾病数量:pc nc uc

一方面你有pc另一方面ncuc你不能说什么(你可以查看你的树的两个级别以获得一些信息,但现在我们不这样做)。

所以最坏的情况,你有pc/nc + ucpc + uc/ nc,选择s最小化最坏情况的情况(即:一侧很多,另一侧只有少数)。

你需要最小化abs( pc - (nc + uc)) + abs ( (pc+uc) - nc).

你现在有你s的第一个问题,你可以迭代地构建你的树。

于 2010-11-04T16:10:02.190 回答
2

您的域真的是这个“二元”,还是实际上,您更可能希望将每个症状/疾病对的相关系数用作数值?这将允许强相关性比弱相关性更能影响结果。

如果是这样,那么您可能需要查看分析数据和识别模式的支持向量机。

于 2010-11-04T16:17:15.400 回答
1

该问题与 Mycin 的细菌/抗生素问题非常相似,Mycin 是 1980 年代更通用的基于规则的专家系统技术的先驱。使用由此产生的工具开发了其他医疗诊断程序。

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

于 2010-11-18T12:12:56.750 回答
0

如果您只需要参考,请查看Russel & Norvig的书。我现在手头没有我的副本,但明天我可以用一些章节建议来更新这个答案。

于 2010-11-04T17:14:33.077 回答
0

如果每种疾病只有几个症状,那么您可以使用图形模型对概率进行建模。

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

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

但我不知道您是否可以使用图形模型来创建问题树。

于 2010-11-04T18:01:18.470 回答