专家系统（？）算法
我有一个算法问题，可以简化为这个任务：
假设我们有一个 n 种疾病和 m 症状的列表。
对于每种疾病d和症状s，我们有以下三个选项之一：
- 症状与疾病正相关：
s => d - 症状与疾病呈负相关：
s => ~d - 症状与疾病不相关
该算法的目标是创建一个关于症状的是/否问题的列表（或者更好的是问题的二叉树），它可以根据症状。
任何对特定算法、相关软件工具甚至特定领域术语的参考都将非常感激。
I have an algorithmic problem which can be reduced to this task:
Suppose we have a list of n diseases and m symptoms.
For each disease d and symptom s, we have one of three options:
- the symptom is positively correlated with the disease:
s => d - the symptom is negatively correlated with the disease:
s => ~d - the symptom is uncorrelated with the disease
The goal of the algorithm is to create a list of yes/no questions regarding symptoms (or even better - a binary tree of questions), which can deduce the exact disease according to the symptoms.
Any references to specific algorithms, relevant software tools and even domain-specific jargon would be very appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您使用决策树： http://en.wikipedia.org/wiki/Decision_tree_learning
基本上找到最优的树（即，在你能够识别疾病之前，它将最大限度地减少提出的问题的平均数量）是 NP 困难的。
您可以使用贪心算法，然后尝试优化它（如果需要的话）。
在每一步中，您都希望尽可能减少仍然“可能”的死亡人数。
您位于树的顶部，因此对于给定的
s，您有三个可能的选项，计算每个选项中的疾病数量：pcncuc。一侧有 pc，另一侧有 nc，而 uc 则无话可说（您可以查看树的两层）以获得一些信息，但目前我们不这样做）。
最坏的情况是，您有
pc/nc + uc或pc + uc/nc，选择 <最小化最坏情况的代码（即：一侧有很多，另一侧只有少数）。您需要最小化
abs( pc - (nc + uc)) + abs ( (pc+uc) - nc)。您现在已经有了第一个问题的
s，并且可以迭代地构建您的树。You case use a decision tree : http://en.wikipedia.org/wiki/Decision_tree_learning
Basically finding the optimum tree (ie which will minimize the average number of questions asked before you can identify the desease) is NP-hard.
You can can use a greedy algorithm and then try to optimise it (if you need it).
At each step you want to reduce at much as possible the number of deceases that are still "possible".
You are at the top of your tree and so you have three possible options for a given
s, count the number of diseases in each option :pcncuc.On one side you have
pcon the otherncand theucyou can't say anything (you can look at two level of your tree to have some info but for now we don't do that).So worst case scenario, you have
pc/nc + ucorpc + uc/nc, choose thesthat minimize worst case (ie : lot of one side, only a few on the other).You need to minimize
abs( pc - (nc + uc)) + abs ( (pc+uc) - nc).You now have your
sfor your first question and you can iteratively build your tree.您的领域真的是这个“二元”吗？或者事实上，您是否更可能希望使用每个症状/疾病对的相关系数作为数值？这将使强相关性比弱相关性对结果的影响更大。
如果是这样，那么您可能需要查看分析数据和识别模式的支持向量机。
Is your domain really this 'binary' or in fact, would you more likely want to use the correlation coefficient for each symptom/disease pair as a numeric value? This would allow strong correlations to influence the result more than weak correlations.
If so then you might want to look at Support Vector Machines that analyze data and recognize patterns.
这个问题与 Mycin 的细菌/抗生素问题非常相似，Mycin 是 20 世纪 80 年代更通用的基于规则的专家系统技术的先驱。使用由此产生的工具开发了其他医疗诊断程序。
http://en.wikipedia.org/wiki/Mycin
The problem is very similar to the bacteria / antibiotic question of Mycin, a forerunner to more generalized rule-based expert systems technology of the 1980s. There were other medical diagnostic programs developed with the resulting tools.
http://en.wikipedia.org/wiki/Mycin
如果您只需要参考，请查看 Russel &诺维格书。我现在手边没有副本，但明天我可以用一些章节建议更新这个答案。
If you just need a reference, take a look at the Russel & Norvig book. I don't have my copy at hand right now, but I can update this answer with some chapter suggestions tomorrow.
如果每种疾病只有几种症状，那么您可以使用图形模型来对概率进行建模。
http://en.wikipedia.org/wiki/Graphical_model
http://www.cs.ubc.ca/~murphyk/Software/bnsoft.html
但我不知道是否可以使用图形模型来创建问题树。
If each disease only has a few symptoms, then you can use graphical models to model the probabilities.
http://en.wikipedia.org/wiki/Graphical_model
http://www.cs.ubc.ca/~murphyk/Software/bnsoft.html
But I don't know if you can use a graphical model to create a tree of questions.