Por favor, use este identificador para citar o enlazar este ítem:
http://inaoe.repositorioinstitucional.mx/jspui/handle/1009/2163| Algoritmo para la búsqueda de todos los reductos más cortos | |
| Yanir González | |
| José Francisco Martínez Trinidad Jesús Ariel Carrasco Ochoa MANUEL SABINO LAZO CORTES | |
| Acceso Abierto | |
| Atribución-NoComercial-SinDerivadas | |
| Shortest Reducts Rough Sets Decision Systems | |
| In Rough Set Theory (RST) a supervised classification problem is represented through Decision Systems. A Decision System is a table in which the rows and columns represent objects and attributes respectively of a data set. On the other hand, the minimum subsets of attributes that preserve the ability to discern the set of objects in the decision system are called reducts. The problem of computing all reducts has an exponential complexity with respect to the number of attributes in a decision system. Therefore, some authors have chosen to calculate only the shortest reducts. In the literature, some algorithms for the computation of all shortest reducts have been reported. However, most of these algorithms are based on time consuming operations for the evaluation of reducts candidates. In this thesis, an algorithm to calculate all the shortest reducts in a decision system, which is based on estimating the size of the shortest reducts and some pruning strategies based on the concepts of core and contribution of an attribute, is introduced. In the proposed algorithm, first, the size of the shortest reducts is approximated, then starting from this approximation and performing some pruning of the search space, the real size of the shortest reducts is determined. Finally, knowing the real size of the shortest reducts and also pruning the search space all the shortest reducts are computed. The results of the experiments over several synthetic and real-world decision systems show that the proposed algorithm is faster than the algorithms reported in the literature in most simplified binary discernibility matrices. En la Teoría de Conjuntos Rugosos (TCR) un problema de clasificación supervisado se representa a través de los Sistemas de Decisión. Un Sistema de Decisión es una tabla en la cual las filas y las columnas representan objetos y atributos, respectivamente, de un conjunto de datos. Por otro lado, los subconjuntos mínimos de atributos que conservan la capacidad de discernir al conjunto de objetos en el sistema de decisión son denominados reductos. El cálculo de todos los reductos en un sistema de decisión tiene una complejidad exponencial con respecto al número de atributos. Por lo tanto, algunos autores han optado por calcular solo los reductos más cortos. En la literatura existen algunos algoritmos para calcular todos los reductos más cortos. Sin embargo, la mayoría de estos algoritmos se basan en operaciones costosas para la evaluación de candidatos a reductos. En el algoritmo propuesto, primero, se aproxima el tamaño de los reductos más cortos, luego, a partir de esta aproximación y realizando una poda del espacio de búsqueda, se determina el tamaño real de los reductos más cortos. Finalmente, conociendo el tamaño real de los reductos más cortos y también podando el espacio de búsqueda, se calculan todos los reductos más cortos. Los resultados de los experimentos realizados sobre sistemas de decisión sintéticos y reales, muestran que el algoritmo propuesto es más rápido que los algoritmos reportados en la literatura, en la mayoría de las matrices de discernibilidad binaria simplificada. | |
| Instituto Nacional de Astrofísica, Óptica y Electrónica | |
| 2021-04 | |
| Tesis de maestría | |
| Español | |
| Estudiantes Investigadores Público en general | |
| González Díaz, Yanir., (2021), Algoritmo para la búsqueda de todos los reductos más cortos, Tesis de Maestría, Instituto Nacional de Astrofísica, Óptica y Electrónica. | |
| LENGUAJES ALGORÍTMICOS | |
| Versión aceptada | |
| acceptedVersion - Versión aceptada | |
| Aparece en las colecciones: | Maestría en Ciencias Computacionales |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| Yanir-González-Díaz-thesis.pdf | 783.32 kB | Adobe PDF | Visualizar/Abrir |