Algorithms for the Unit-Cost Stochastic Score Classification Problem
Algorithms for the Unit-Cost Stochastic Score Classification Problem
复制标题
单位成本随机分数分类问题的算法
DOI：
10.1007/s00453-022-00982-4
复制
发表时间：
2022
期刊：
影响因子：
1.1
通讯作者：
Liu, Naifeng
中科院分区：
文献类型：
--
作者：
Grammel, Nathaniel;Hellerstein, Lisa;Kletenik, Devorah;Liu, Naifeng
考虑下面的随机分数分类问题。医生正在评估病人罹患疾病的风险，并可以对病人进行不同的二元测试。测试为阳性的概率是独立的，测试结果是独立的。患者的得分是阳性检测的总数。因此，可能的分数范围在0到n之间。根据风险类别(例如，低、中或高风险)，该范围被划分为子范围。每项测试都有相关的成本。为了降低测试成本，医生可以按顺序执行测试，并在可能确定患者的风险级别时停止测试，而不是执行所有测试并确定确切的分数。问题是确定医生应该进行测试的顺序，以便将预期的测试成本降至最低。我们讨论了随机得分分类问题的单位成本情况，并为该问题的自适应和非自适应版本提供了多项式时间近似算法。我们还提出了一些未解决的问题。
Consider the following Stochastic Score Classification problem. A doctor is assessing a patient’s risk of developing a disease and can performndifferent binary tests on the patient. The probability that testiis positive isand the outcomes of thentests are independent. A patient’s score is the total number of positive tests. Possible scores thus range between 0 andn. This range is divided into subranges, corresponding to risk classes (e.g., LOW, MEDIUM, or HIGH risk). Each test has an associated cost. To reduce testing cost, instead of performing all tests and determining an exact score, the doctor can perform tests sequentially and stop testing when it is possible to determine the patient’s risk class. The problem is to determine the order in which the doctor should perform the tests, so as to minimize expected testing cost. We address the unit-cost case of the Stochastic Score Classification problem, and provide polynomial-time approximation algorithms for adaptive and non-adaptive versions of the problem. We also pose a number of open questions.
登录
查看更多内容
DOI：
10.4230/lipics.esa.2018.36
发表时间：
2018
期刊：
Math. Oper. Res.
影响因子：
--
作者：
Dimitrios Gkenosis;Nathaniel Grammel;L. Hellerstein;Devorah Kletenik
通讯作者：
Devorah Kletenik
优化的风险评分
DOI：
10.1145/3097983.3098161
发表时间：
2017
期刊：
Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
影响因子：
--
作者：
Berk Ustun;C. Rudin
通讯作者：
C. Rudin
复杂决策的简单规则
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
Jongbin Jung;Connor Concannon;Ravi Shroff;Sharad Goel;D. Goldstein
通讯作者：
D. Goldstein
影响因子：
1.3
作者：
Deshpande, Amol;Hellerstein, Lisa;Kletenik, Devorah
通讯作者：
Kletenik, Devorah
一些对称相干系统的优化测试算法
DOI：
--
发表时间：
1984
期刊：
影响因子：
--
作者：
S. Salloum;M. Breuer
通讯作者：
M. Breuer