Divisive-Agglomerative Algorithm and Complexity of Automatic Classification Problems

NRU Higher School of Economics , 2015. No. WP7/2015/09.

Rubchinskiy A.

An algorithm of solution of the Automatic Classification (AC for brevity) problem is set forth in the paper. In the AC problem, it is required to find one or several partitions, starting with the given pattern matrix or dissimilarity / similarity matrix. The three-level scheme of the algorithm is suggested. The output of the procedure is a family of classifications, while the ratio between the cardinality of this family and the cardinality of the set of all the classifications, considered in the procedure, is taken as a measure of complexity of the initial AC problem. For classifications of parliament members according to their vote results, the general notion of complexity is interpreted as consistence or rationality of this parliament policy. For “tossing” deputies or ⁄ and whole fractions the corresponding clusters become poorly distinguished and partially perplexing that results in relatively high value of complexity of their classifications. By contrast, under consistent policy, deputies’ clusters are clearly distinguished and the complexity level is low enough (i.e. in a given parliament the level of consistency, accordance, rationality is high). The mentioned reasoning was applied to analysis of activity of 2-nd, 3-rd and 4-th RF Duma (Russian parliament, 1996–2007). The classifications based upon one-month votes were constructed for every month. The comparison of complexity for selected periods allows suggesting new meaningful interpretations of activity of various election bodies, including different country parliaments, international organizations and board of large corporations.

Keywords: entropy, энтропия, голосование, complexity, сложность, voting, automatic classification, автоматическая классификация

Publication based on the results of: Разработка моделей, методов и алгоритмов для разработки и анализа интеллектуальных систем (2015)