stringtranslate.com

Enfoque de conjunto aproximado basado en la dominancia

El enfoque de conjuntos aproximados basado en el dominio ( DRSA ) es una extensión de la teoría de conjuntos aproximados para el análisis de decisiones de criterios múltiples (MCDA), introducida por Greco, Matarazzo y Słowiński. [1] [2] [3] El principal cambio en comparación con los conjuntos aproximados clásicos es la sustitución de la relación de indiscernibilidad por una relación de dominio, que permite abordar las inconsistencias típicas de la consideración de criterios y clases de decisión ordenadas por preferencias .

Clasificación multicriterio (ordenación)

La clasificación multicriterio (ordenamiento) es uno de los problemas considerados dentro del MCDA y puede enunciarse de la siguiente manera: dado un conjunto de objetos evaluados por un conjunto de criterios (atributos con dominios de orden de preferencia), asignar estos objetos a algunas clases de decisión predefinidas y ordenadas por preferencia, de modo que cada objeto se asigne exactamente a una clase. Debido al orden de preferencia, la mejora de las evaluaciones de un objeto en los criterios no debería empeorar su asignación de clase. El problema de ordenamiento es muy similar al problema de clasificación , sin embargo, en este último, los objetos se evalúan por atributos regulares y las clases de decisión no están necesariamente ordenadas por preferencia. El problema de la clasificación multicriterio también se conoce como problema de clasificación ordinal con restricciones de monotonía y a menudo aparece en aplicaciones de la vida real cuando las propiedades ordinales y monótonas se desprenden del conocimiento del dominio sobre el problema.

Como ejemplo ilustrativo, considere el problema de la evaluación en una escuela secundaria. El director de la escuela quiere asignar estudiantes ( objetos ) a tres clases: malo , medio y bueno (observe que la clase bueno se prefiere a medio y medio se prefiere a malo ). Cada estudiante se describe mediante tres criterios: nivel en Física, Matemáticas y Literatura, cada uno tomando uno de tres valores posibles malo , medio y bueno . Los criterios están ordenados por preferencia y mejorar el nivel de una de las materias no debería resultar en una peor evaluación global (clase).

Como ejemplo más serio, considere la clasificación de los clientes bancarios, desde el punto de vista del riesgo de quiebra, en clases seguras y riesgosas . Esto puede involucrar características tales como " rendimiento sobre el capital (ROE)", " rendimiento sobre la inversión (ROI)" y " rendimiento sobre las ventas (ROS)". Los dominios de estos atributos no están simplemente ordenados sino que involucran un orden de preferencia ya que, desde el punto de vista de los gerentes bancarios, mayores valores de ROE, ROI o ROS son mejores para los clientes que se analizan para el riesgo de quiebra. Por lo tanto, estos atributos son criterios. Ignorar esta información en el descubrimiento de conocimiento puede llevar a conclusiones erróneas.

Representación de datos

Tabla de decisiones

En DRSA, los datos se presentan a menudo utilizando una forma particular de tabla de decisiones . Formalmente, una tabla de decisiones DRSA es una tupla de 4 , donde es un conjunto finito de objetos, es un conjunto finito de criterios, donde es el dominio del criterio y es una función de información tal que para cada . El conjunto se divide en criterios de condición (conjunto ) y el criterio de decisión ( clase ) . Observe que es una evaluación del objeto en criterio , mientras que es la asignación de clase (valor de decisión) del objeto. En la Tabla 1 a continuación se muestra un ejemplo de tabla de decisiones.

Relación de superioridad

Se supone que el dominio de un criterio está completamente preordenado por una relación de clasificación superior ; significa que es al menos tan bueno como (clasifica superiormente) con respecto al criterio . Sin pérdida de generalidad, suponemos que el dominio de es un subconjunto de los números reales , , y que la relación de clasificación superior es un orden simple entre números reales tal que se cumple la siguiente relación: . Esta relación es sencilla para el criterio de tipo ganancia ("cuanto más, mejor"), p. ej., beneficio de la empresa . Para el criterio de tipo coste ("cuanto menos, mejor"), p. ej., precio del producto , esta relación se puede satisfacer negando los valores de .

Clases de decisión y uniones de clases

Sea . El dominio del criterio de decisión, consiste en elementos (sin pérdida de generalidad suponemos ) e induce una partición de en clases , donde . Cada objeto se asigna a una y sólo una clase . Las clases están ordenadas por preferencia según un orden creciente de índices de clase, es decir, para todos tales que , los objetos de son estrictamente preferidos a los objetos de . Por esta razón, podemos considerar las uniones ascendentes y descendentes de clases , definidas respectivamente, como:

Conceptos principales

Dominio

Decimos que domina con respecto a , denotado por , si es mejor que en cada criterio desde , . Para cada , la relación de dominancia es reflexiva y transitiva , es decir, es un preorden parcial . Dados y , sea

representan el conjunto P -dominante y el conjunto P -dominado con respecto a , respectivamente.

Aproximaciones aproximadas

La idea clave de la filosofía de los conjuntos aproximados es la aproximación de un conocimiento por medio de otro. En DRSA, el conocimiento que se aproxima es una colección de uniones ascendentes y descendentes de clases de decisión y los "gránulos de conocimiento" utilizados para la aproximación son conjuntos P -dominantes y P -dominantes.

La aproximación P -inferior y P -superior de con respecto a , denotadas como y , respectivamente, se definen como:

De manera análoga, la aproximación P -inferior y la aproximación P -superior de con respecto a , denotadas como y , respectivamente, se definen como:

Las aproximaciones inferiores agrupan los objetos que pertenecen con certeza a la unión de clases (respectivamente ). Esta certeza proviene del hecho de que el objeto pertenece a la aproximación inferior (respectivamente ), si ningún otro objeto en contradice esta afirmación, es decir, todo objeto que P -domina , también pertenece a la unión de clases (respectivamente ). Las aproximaciones superiores agrupan los objetos que podrían pertenecer a (respectivamente ), ya que el objeto pertenece a la aproximación superior (respectivamente ), si existe otro objeto P -dominado por de la unión de clases (respectivamente ).

Las aproximaciones P -inferior y P -superior definidas anteriormente satisfacen las siguientes propiedades para todos y para cualquier :

Los límites P ( regiones P-dudosas ) de y se definen como:

Calidad de aproximación y reducciones

La proporción

define la calidad de aproximación de la partición en clases mediante el conjunto de criterios . Esta relación expresa la relación entre todos los objetos P -correctamente clasificados y todos los objetos de la tabla.

Cada subconjunto mínimo tal que se denomina reduct de y se denota por . Una tabla de decisión puede tener más de un reduct. La intersección de todos los reduct se conoce como el núcleo .

Reglas de decisión

A partir de las aproximaciones obtenidas mediante las relaciones de dominancia, es posible inducir una descripción generalizada de la información preferencial contenida en la tabla de decisión, en términos de reglas de decisión . Las reglas de decisión son expresiones de la forma si [condición] entonces [consecuente], que representan una forma de dependencia entre criterios de condición y criterios de decisión. Los procedimientos para generar reglas de decisión a partir de una tabla de decisión utilizan un principio de aprendizaje inductivo. Podemos distinguir tres tipos de reglas: ciertas, posibles y aproximadas. Las reglas ciertas se generan a partir de aproximaciones inferiores de uniones de clases; las reglas posibles se generan a partir de aproximaciones superiores de uniones de clases y las reglas aproximadas se generan a partir de regiones límite.

Ciertas reglas tienen la siguiente forma:

Si y y entonces

Si y y entonces

Las reglas posibles tienen una sintaxis similar, sin embargo la parte consecuente de la regla tiene la forma: podría pertenecer a o la forma: podría pertenecer a .

Finalmente, las reglas aproximadas tienen la sintaxis:

si y y y y y entonces

Las reglas ciertas, posibles y aproximadas representan conocimiento cierto, posible y ambiguo extraído de la tabla de decisiones.

Cada regla de decisión debe ser mínima. Como una regla de decisión es una implicación, por regla de decisión mínima entendemos una implicación tal que no existe otra implicación con un antecedente de al menos la misma debilidad (en otras palabras, regla que utiliza un subconjunto de condiciones elementales o/y condiciones elementales más débiles) y un consecuente de al menos la misma fuerza (en otras palabras, regla que asigna objetos a la misma unión o subunión de clases).

Un conjunto de reglas de decisión es completo si es capaz de cubrir todos los objetos de la tabla de decisiones de tal manera que los objetos consistentes se reclasifiquen en sus clases originales y los objetos inconsistentes se clasifiquen en grupos de clases que hagan referencia a esta inconsistencia. Llamamos mínimo a todo conjunto de reglas de decisión que sea completo y no redundante, es decir, la exclusión de cualquier regla de este conjunto lo hace no completo. Se puede adoptar una de tres estrategias de inducción para obtener un conjunto de reglas de decisión: [4]

El algoritmo de inducción de reglas más popular para el enfoque de conjuntos aproximados basado en dominancia es DOMLEM, [5] que genera un conjunto mínimo de reglas.

Ejemplo

Consideremos el siguiente problema de evaluaciones de estudiantes de secundaria:

Cada objeto (estudiante) se describe mediante tres criterios , relacionados con los niveles en Matemáticas, Física y Literatura, respectivamente. Según el atributo de decisión, los estudiantes se dividen en tres clases ordenadas por preferencia: , y . De esta forma, se aproximaron las siguientes uniones de clases:

Obsérvese que las evaluaciones de los objetos y son inconsistentes, porque tiene mejores evaluaciones en los tres criterios pero una puntuación global peor.

Por lo tanto, las aproximaciones inferiores de las uniones de clases consisten en los siguientes objetos:

Por lo tanto, sólo las clases y no se pueden aproximar con precisión. Sus aproximaciones superiores son las siguientes:

mientras que sus regiones límite son:

Por supuesto, dado que y se aproximan con precisión, tenemos , y

El siguiente conjunto mínimo de 10 reglas se puede inducir a partir de la tabla de decisiones:

  1. Si entonces
  2. Si y y entonces
  3. Si entonces
  4. Si y entonces
  5. Si y entonces
  6. Si y entonces
  7. Si y entonces
  8. Si entonces
  9. Si entonces
  10. Si y entonces

La última regla es aproximada, mientras que el resto son seguras.

Extensiones

Problemas de elección y clasificación de criterios múltiples

Los otros dos problemas considerados en el análisis de decisiones multicriterio , los problemas de elección multicriterio y de clasificación , también pueden resolverse utilizando el enfoque de conjunto aproximado basado en la dominancia. Esto se hace convirtiendo la tabla de decisiones en una tabla de comparación por pares (PCT). [1]

DRSA de consistencia variable

Las definiciones de aproximaciones aproximadas se basan en una aplicación estricta del principio de dominancia. Sin embargo, al definir objetos no ambiguos, es razonable aceptar una proporción limitada de ejemplos negativos, en particular para tablas de decisión grandes. Esta versión extendida de DRSA se denomina modelo DRSA de consistencia variable (VC-DRSA) [6].

DRSA estocástico

En los datos de la vida real, en particular para grandes conjuntos de datos, se encontró que las nociones de aproximaciones aproximadas eran excesivamente restrictivas. Por lo tanto, se ha introducido una extensión de DRSA, basada en el modelo estocástico ( Stochastic DRSA ), que permite inconsistencias hasta cierto punto. [7] Habiendo enunciado el modelo probabilístico para problemas de clasificación ordinal con restricciones de monotonía, los conceptos de aproximaciones inferiores se extienden al caso estocástico. El método se basa en la estimación de las probabilidades condicionales utilizando el método de máxima verosimilitud no paramétrico que conduce al problema de la regresión isotónica .

Los conjuntos aproximados basados ​​en el dominio estocástico también pueden considerarse como una especie de modelo de consistencia variable.

Software

4eMka2 es un sistema de soporte de decisiones para problemas de clasificación de criterios múltiples basado en conjuntos aproximados basados ​​en dominancia (DRSA). JAMM es un sucesor mucho más avanzado de 4eMka2. Ambos sistemas están disponibles de forma gratuita para fines no lucrativos en el sitio web del Laboratorio de Sistemas Inteligentes de Soporte de Decisiones (IDSS) .

Véase también

Referencias

  1. ^ ab Greco, S., Matarazzo, B., Słowiński, R.: Teoría de conjuntos aproximados para el análisis de decisiones multicriterio. Revista Europea de Investigación Operativa, 129 , 1 (2001) 1–47
  2. ^ Greco, S., Matarazzo, B., Słowiński, R.: Clasificación multicriterio mediante un enfoque de conjunto aproximado basado en la dominancia. En: W. Kloesgen y J. Zytkow (eds.), Handbook of Data Mining and Knowledge Discovery, Oxford University Press, Nueva York, 2002
  3. ^ Słowiński, R., Greco, S., Matarazzo, B.: Soporte de decisiones basado en conjuntos aproximados. Capítulo 16 [en]: EK Burke y G. Kendall (eds.), Metodologías de búsqueda: Tutoriales introductorios en técnicas de optimización y soporte de decisiones, Springer-Verlag, Nueva York (2005) 475–527
  4. ^ Stefanowski, J.: Un enfoque basado en conjuntos aproximados para la inducción de reglas de decisión. En Skowron, A., Polkowski, L. (eds.): Rough Set in Knowledge Discovering, Physica Verlag, Heidelberg (1998) 500--529
  5. ^ Greco S., Matarazzo, B., Słowiński, R., Stefanowski, J.: Un algoritmo para la inducción de reglas de decisión consistentes con el principio de dominancia. En W. Ziarko, Y. Yao (eds.): Conjuntos aproximados y tendencias actuales en computación. Apuntes de clase sobre inteligencia artificial 2005 (2001) 304--313. Springer-Verlag
  6. ^ Greco, S., B. Matarazzo, R. Slowinski y J. Stefanowski: Modelo de consistencia variable del enfoque de conjuntos aproximados basado en la dominancia. En W. Ziarko, Y. Yao (eds.): Conjuntos aproximados y tendencias actuales en computación. Apuntes de clase sobre inteligencia artificial 2005 (2001) 170–181. Springer-Verlag
  7. ^ Dembczyński, K., Greco, S., Kotłowski, W., Słowiński, R.: Modelo estadístico para el enfoque de conjuntos aproximados para la clasificación multicriterio. En Kok, JN, Koronacki, J., de Mantaras, RL, Matwin, S., Mladenic, D., Skowron, A. (eds.): Descubrimiento de conocimiento en bases de datos: PKDD 2007, Varsovia, Polonia. Apuntes de clase en informática 4702 (2007) 164–175.

Enlaces externos