How to build a decision tree with a constraint on sensitivity? I am trying to develop a classification model on a sample of people which will discriminate between "Type A" and "Not-Type A" people.  Due to external factors, the minimum sensitivity for this classification--that is, the minimum probability that person will be classified as Type A given that they actually are Type A--must be greater than or equal to 95%.
Given these constraints, I already performed an ROC analysis by fitting my class variable on the available covariates using logistic regression, subsequently using the predicted probabilities as a classifier (i.e.: p-hat>=threshold means "type A", otherwise "Not-Type-A").  The ROC curve from this method looks roughly like this:

Basically, my discrimination function works very, very well for high specificity and (relatively) low sensitivity, but performance (i.e., the distance between the ROC curve and the diagonal line) becomes progressively worse as one moves to other extreme of high sensitivity/low specificity.
Initially, this was OK because in an ROC analysis, I can take the point that performs "best" between [0.95,1] sensitivity and use the corresponding threshold for the predicted probabilities to classify my sample--the discriminant isn't optimal, but it's as optimal as it can be given my constraints.
The problem is, my end user doesn't want to use the logit formula to calculate predicted probabilities and compare that to a threshold.  They need to be able to discriminate classes "in the field" without using a calculator, so they want a decision tree instead.
I can build a decision tree with recursive partition methods.  The results are uncannily similar to what they would be if I was able to use the "optimal" point in the ROC curve--if you average up the mis-classification rates in the terminal nodes, the decision tree results in a specificity of 97.6%, and a sensitivity of 49.5%.
However, I don't need a perfectly optimal classifier, I need a classifier that's as optimal as possible given a required sensitivity greater than 95%.  I have no idea how to modify the recursive partitioning algorithm to apply this constraint, and I can't find any literature on the subject.  Is it even possible?  Is there some other method for constructing a decision tree that will converge on a tree with the required sensitivity?
 A: Summary:
Q: Grow a decision tree such that $se \ge 0.95$A: Substitute the tree decision evaluation criterion by one that has a tuning parameter that controls how much to reward sensitivity. Test this decision tree (using k-fold cross-validation) and measure the sensitivity. If $se \ge 0.95$ is not true, repeat the process but with more aggressive parameters for the criterion until you get a tree that satisfies $se \ge 0.95$.
Overview on decision trees:
Suppose that you choose C4.5 as your decision tree generation algorithm (which is also known to generate small trees in case your end-users like small trees).
Growing C4.5 trees is generally simple: you perform a series of splits until you reach a stopping condition. A stopping condition could be things like:


*

*Purity of the leaf node (e.g. entropy of samples in the leaf node with respect to their target variable is small enough).

*Maximum tree branch depth is reached (this is a parameter to ensure that your model does not overfit the training samples).

*Leaf boundary tightness around samples that are inside it (Google for "tree grafting").

*Etc.


Other stopping criteria exist and you may wish to look at them, but this is not our main focus.
The main focus here is identifying which binary split is the optimal split that satisfies your $se \ge 0.95$ constraint.
To address this we need to look at how it's done with our example decision tree, the C4.5 algorithm. Generally, it:


*

*All possible split using all available features are evaluated. Then split that causes maximum Information Gain will be chosen as the 1st split. Now we have split our dataset into two subsets: subset right, and subset left.

*Then, for each of those subsets, we evaluate all the possible splits, and then choose one that gives us maximum Information Gain.

*This process is repeated recursively for the subsequent subsets as we keep splitting the leaf nodes further down the tree (until we reach the stopping conditions above).


A classical split evaluation criterion: Information Gain
Let $\mathcal{X}$ be your dataset, $\mathcal{Y}$ be their corresponding labels, and $f:\mathcal{X} \rightarrow \mathcal{Y}$ be sample-to-label mapping function.
Suppose that for any sample $x \in \mathcal{X}$, $x$ is represented as a $k$ dimensional vector, where, for any $i \in \{1, 2, 
\ldots, k\}$, $x[i]$ represents the value of the $i^{th}$ component or feature.
Also, we define $s_{i,v}$ as a decision split on feature $i$  by using value $v \in \mathbb{R}$. An example of such decision split is:
\begin{equation}
s_{i,v}(x) = \begin{cases}
  \textbf{True} & \text{if } x[i] \ge v\\
  \textbf{False} & \text{else}
\end{cases}
\end{equation}
Then, if we apply split $s_{i,v}$ on samples in set $\mathcal{X}$, we obtain subsets $\mathcal{X}_{left} = \{x:x\in\mathcal{X}, s_{i,v}(x) = \textbf{True}\}$ and $\mathcal{X}_{right} = \{x:x\in\mathcal{X}, s_{i,v}(x) = \textbf{False}\}$.
Finally, we calculate the Information Gain of $s_{i,v}$ on $\mathcal{X}$ as follows: $IG(\mathcal{X}, s_{i,v}) = H(\mathcal{X}) -  \big(\frac{1}{|\mathcal{X}_{left}|}H(\mathcal{X}_{left}) + \frac{1}{|\mathcal{X}_{right}|}H(\mathcal{X}_{right})\big)$, where $H$ is Shannon's entropy (not gonna explain it here).
The process above is repeated for all possible splits $s_{i,v}$ on $\mathcal{X}$. I.e., all evaluatable values of $i$ and $v$ are evaluated exhaustively. Then, the split that has maximum IG is chosen.
Once the above happens, we repeat all that again, but this time with the subsets that are created by apply the optimal split above. This process is repeated recursively.
A new split evaluation criterion to satisfy $se \ge 0.95$
Let $se:\mathcal{X} \rightarrow [0,1]$ and $sp:\mathcal{X} \rightarrow [0,1]$ be functions that output sensitivity and specificity of their input sets. Then we define our split evaluation criterion as follows: 
\begin{equation}\begin{split}
New(\mathcal{X}, s_{i,v}, t) &= \begin{split}&\left(\begin{split}&\frac{1}{\mathcal{X}_{left}}\Big(t \times se(\mathcal{X}_{left}) + (1-t) \times sp(\mathcal{X}_{left})\Big)\\  &+\\
 &\frac{1}{\mathcal{X}_{right}}\Big(t \times se(\mathcal{X}_{right}) + (1-t) \times sp(\mathcal{X}_{right})\Big) \end{split}\right)\end{split}\\
\end{split}
\end{equation} where $t \in [0,1]$ is a threshold that favors splits that return higher specificity the higher it is, and favors splits that return higher sensitivity the lower it is.
If you replace IG (or Gini index, or whatever criterion) by $New$, and set $t$ large enough, then as the individual splits in your tree are biased towards better sensitivity, the sensitivity of your whole tree should too be biased towards better sensitivity. If $t$ is large enough, then your tree as a whole should satisfy your $se \ge 0.95$ constraint.
Extra notes
You may wish to explore ensembles of decision trees, such as Random Forests, Extra Trees, etc as they are more accurate than C4.5 in general. However, a challenge would be representing such ensemble of trees as a single tree to your end users.
A: You could consider formulating your problem as Neyman-Pearson's classification where you minimize false negative rate subject to a constraint on false positive.  One paper describing a method for training such decision trees is here:
http://nowak.ece.wisc.edu/np.pdf
It does a global optimization which may be what you want for a single tree.
I implemented a related criteria for greedy CART growth here:
https://github.com/ryanbressler/CloudForest/blob/master/NPtarget.go
It works okay in an ensemble though I've never tried it in a single tree and they're may be issues with overfitting. I've found predicting the probabilities and using a cutoff as you suggest works best. 
I'd also consider simply growing a tree to predict probabilities and then relabeling the nodes using the optimal cutoff. In this case you may be able to shift the sensitivity/specificity by using either class weights or resampling your training data set. Ie over sample or up weight the minority class members until they are about even with the majority class...this is usually referred to unbalanced or imbalanced classification. Cost sensitive classification is closely related. Searching those terms will yield lots of results. 
A: Using a recursive tree building algorithm, which makes decisions on splits based solely on information available at each individual node, cannot conform to a constraint on specificity or sensitivity.  Sensitivity and specificity are performance measures that apply to an entire tree; they cannot be calculated until a tree or sub-tree is finished, at which point it is too late.
In the end, I went in a different direction for my end-users, building a nomogram with the regression results I obtained earlier.  While this method is still more complicated than referencing a decision tree it is all very simple addition, as opposed to calculating the full linear regression formula.
