Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

Efficient Generation of Reducts and Discerns for Classification

Graham, James T.

Abstract Details

2007, Master of Science (MS), Ohio University, Electrical Engineering & Computer Science (Engineering and Technology).

The intent of this thesis is to improve on existing algorithms for determining classification rules by reducing the computational time to generate the reducts of an information system. Determining all reducts is an NP (Non-deterministic Polynomial time) complete problem and, therefore, as the data set grows in size, the time required for computation rapidly exceeds what is practical. This thesis has been able to significantly reduce the amount of time it takes to perform these computations. While the problem is still NP complete, the amount of time required by the methods introduced is less than other well-known methods provided by other software packages such as Rosetta [Ohr99] and RSES [RSES2].

Despite the reduct generation time improvements, larger databases still take far too long for effective reduct determination; therefore, heuristic non-exhaustive methods were also evaluated. In practical applications of rough sets, it is important that the obtained reducts retain most of the information about the original problem. In these applications, reducts of a dataset are used as classifiers to determine the “rules” for classification. The second half of this thesis proposes a method for rapidly producing effective classifiers of sufficient quality to get classification results of equal or better quality compared to exhaustive methods. The proposed method gives results that are at, or near, the same quality as those obtained from using the exhaustive method in only a fraction of the computational time.

Janusz Starzyk (Advisor)
116 p.

Recommended Citations

Citations

  • Graham, J. T. (2007). Efficient Generation of Reducts and Discerns for Classification [Master's thesis, Ohio University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1175639229

    APA Style (7th edition)

  • Graham, James. Efficient Generation of Reducts and Discerns for Classification. 2007. Ohio University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1175639229.

    MLA Style (8th edition)

  • Graham, James. "Efficient Generation of Reducts and Discerns for Classification." Master's thesis, Ohio University, 2007. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1175639229

    Chicago Manual of Style (17th edition)