A Binary Integer Program to Maximize the Agreement Between Partitions |
| |
Authors: | Michael J Brusco Douglas Steinley |
| |
Institution: | (1) Department of Marketing, Florida State University, Tallahassee, FL 32306-1110, USA;(2) Department of Psychological Sciences, University of Missouri, 210 McAlester Hall, Columbia, MO 65211, USA |
| |
Abstract: | This research note focuses on a problem where the cluster sizes for two partitions of the same object set are assumed known;
however, the actual assignments of objects to clusters are unknown for one or both partitions. The objective is to find a
contingency table that produces maximum possible agreement between the two partitions, subject to constraints that the row
and column marginal frequencies for the table correspond exactly to the cluster sizes for the partitions. This problem was
described by H. Messatfa (Journal of Classification, 1992, pp. 5–15), who provided a heuristic procedure based on the linear transportation problem. We present an exact solution
procedure using binary integer programming. We demonstrate that our proposed method efficiently obtains optimal solutions
for problems of practical size.
We would like to thank the Editor, Willem Heiser, and an anonymous reviewer for helpful comments that resulted in improvements
of this article. |
| |
Keywords: | Partition agreement Contingency table Binary integer programming |
本文献已被 SpringerLink 等数据库收录! |
|