Date of Award


Document Type


Degree Name

Master of Science


Department of Mathematics and Statistics

First Advisor

J. D. Peterson, PhD.


DoD health care requires reform with growing costs causing concerns of decreased military capability. One proposed radical strategy to fix current health care delivery systems is to organize medical teams around patients with similar treatment requirements. This is a clustering problem; how do you partition the set of patients so that each group has similar treatment needs? We provide advances in clustering theory relevant to this new health care strategy. In particular, we create fast certifiably optimal k-means clustering using what is known as Probably Certifiably Correct (PCC) algorithms which achieves state-of-the-art performance under certain models. Inspired by the health care clustering problem, we pay particular attention to a Bipartite Stochastic Block Model and produce an alternative PCC algorithm specific to this model. We conclude by demonstrating the potential utility of applying these clustering methods in health care. Using conditional entropy as a metric, clusters obtained from our methods vastly outperform partitions prescribed by subject matter experts.

AFIT Designator


DTIC Accession Number