標題: Optimality of nested partitions and its application to cluster analysis
作者: Boros, E
Hwang, FK
應用數學系
Department of Applied Mathematics
關鍵字: clustering;nested partitions
公開日期: 1-十一月-1996
摘要: A partition of a set N of n distinct numbers is called nested if four numbers a < b < c < d in N such that a and c are in one part while b and d in another do not exist. A partition is called a p-partition if the number of parts is specified at p and a shape-partition if the sizes of the p parts are also specified. There are exponentially many p-partitions but only polynomially many nested p-partitions. In this paper we consider these notions in d-dimensional Euclidean spaces and give a general condition on the cost structure for which an optimal shape-partition is always nested. We illustrate applications of our results to some clustering problems, generalize some known results in this way, and propose some open problems.
URI: http://hdl.handle.net/11536/962
ISSN: 1052-6234
期刊: SIAM JOURNAL ON OPTIMIZATION
Volume: 6
Issue: 4
起始頁: 1153
結束頁: 1162
顯示於類別:期刊論文


文件中的檔案:

  1. A1996VP63000015.pdf