Name
Abstract | ||
|---|---|---|
The problem of real value attribute discretization can be converted into the reduct problem in the Rough Set Theory, which is NP-hard and can be solved by some heuristic algorithms. In this paper we show that the straightforward conversion is not scalable and propose a divide-and-conquer algorithm. This algorithm is fully scalable and can reduce the time complexity dramatically especially while integrated with the tournament discretization algorithm. Parallel versions of this algorithm can be easily written, and their complexity depends on the number of objects in each subtable rather than the number of objects in the initial decision table. There is a tradeoff between the time complexity and the quality of the discretization scheme obtained, and this tradeoff can be made through adjusting the number of subtables, or equivalently, the number of objects in each subtable. Experimental results confirm our analysis and indicate appropriate parameter setting. |
Year | DOI | Venue |
|---|---|---|
2005 | null | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
Keywords | Field | DocType |
reduct problem,rough set theory,appropriate parameter setting,divide-and-conquer algorithm,real value attribute discretization,discretization scheme,divide-and-conquer discretization algorithm,tournament discretization algorithm,heuristic algorithm,time complexity,decision table,divide and conquer | Discretization,Heuristic,Reduct,Decision table,Parallel algorithm,Computer science,Algorithm,Rough set,Divide and conquer algorithms,Time complexity | Conference |
Volume | Issue | ISSN |
3613 LNAI | null | 16113349 |
ISBN | Citations | PageRank |
3-540-28312-9 | 3 | 0.41 |
References | Authors | |
4 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fan Min | 1 | 838 | 46.96 |
| Lijun Xie | 2 | 24 | 4.56 |
| Qihe Liu | 3 | 153 | 12.32 |
| Hongbin Cai | 4 | 6 | 0.85 |