A dynamic-programming algorithm for hierarchical discretization of continuous attributes

Ching-Cheng Shen

doi:10.1016/j.ejor.2006.12.013

2008-01-01

PRE

Ching-Cheng Shen

Yen‐Liang Chen *

DOI：10.1016/j.ejor.2006.12.013

原文链接

原文求助

摘要

En 中文

Discretization techniques can be used to reduce the number of values for a given continuous attribute, and a concept hierarchy can be used to define a discretization of a given continuous attribute. Traditional methods of building a concept hierarchy from a continuous attribute are usually based on the level-wise approach. Unfortunately, this approach suffers from three weaknesses: (1) it only seeks a local optimal solution instead of a global optimal, (2) it is usually subject to the constraint that each interval can only be partitioned into a fixed number of subintervals, and (3) the constructed tree may be unbalanced. In view of these weaknesses, this paper develops a new algorithm based on dynamic-programming strategy for constructing concept hierarchies from continuous attributes. The constructed trees have three merits: (1) they are global optimal trees, (2) each interval is partitioned into the most appropriate number of subintervals, and (3) the trees are balanced. Finally, we carry out an experimental study using real data to show its efficiency and effectiveness. (C) 2006 Elsevier B.V. All rights reserved.

Keyword:

dynamic programming

concept hierarchy

data mining

continuous data