Repository: dpuenteramirez/Semisupervised-learning-and-instance-selection-methods (language: python)

Issue:
DROP3 - Report

DROP3  Implementation

DROP3 - Report



Discussion / hints:

Fix patch:
diff --git a/Instance Selection Algorithms/DROP3.py b/Instance Selection Algorithms/DROP3.py
new file mode 100644
index 0000000..13533e0
--- /dev/null
+++ b/Instance Selection Algorithms/DROP3.py
@@ -0,0 +1,162 @@
+#!/usr/bin/env python
+# -*- coding:utf-8 -*-
+# @Filename:    DROP3.py
+# @Author:      Daniel Puente Ramírez
+# @Time:        31/12/21 16:00
+
+from sys import maxsize
+
+import numpy as np
+from sklearn.datasets import load_iris
+
+from ENN import ENN
+from graficas import grafica_2D
+
+
+def with_without(x_sample, sample_associates, samples_labels, neighs):
+    with_ = 0
+    without = 0
+    for a_sample in sample_associates:
+        a_label = samples_labels[tuple(a_sample)]
+        for y_sample, y_neighs, y_labels in neighs:
+            if np.array_equal(a_sample, y_sample):
+                count = np.bincount(y_labels)
+                max_class = np.where(count == np.amax(count))[0][0]
+                if max_class == a_label:
+                    was_in = False
+                    for a_neigh in y_neighs:
+                        if np.array_equal(x_sample, a_neigh):
+                            was_in = True
+                            break
+                    if was_in:
+                        with_ += 1
+                    else:
+                        without += 1
+                break
+
+    return with_, without
+
+
+def DROP3(X, k):
+    """
+
+    :param X:
+    :param k:
+    :return:
+    """
+    # Filtro de ruido
+    S = ENN(X, k)
+
+    # Ordenar las instancias en S por la distancia a su enemigo más próximo
+    # de más lejano a más cercano
+    initial_samples, initial_labels = S['data'], S['target']
+    initial_distances = []
+
+    for x_sample, x_label in zip(initial_samples, initial_labels):
+        min_distance = maxsize
+        for y_sample, y_label in zip(initial_samples, initial_labels):
+            if x_label != y_label:
+                xy_distance = np.linalg.norm(x_sample - y_sample)
+                if xy_distance < min_distance:
+                    min_distance = xy_distance
+        initial_distances.append([x_sample, x_label, min_distance])
+
+    initial_distances.sort(key=lambda x: x[2], reverse=True)
+
+    # Para cada x en S, encontrar sus k-NN y añadir x a la lista de asociados
+    # de sus k-NN
+    sample_neighs = []
+    sample_associates = [[x, []] for x, _, _ in initial_distances]
+
+    for x_sample, _, _ in initial_distances:
+        y_sample_distance = []
+        for y_sample, y_label in zip(initial_samples, initial_labels):
+            if not np.array_equal(x_sample, y_sample):
+                y_sample_distance.append([y_sample, y_label, np.linalg.norm(
+                    x_sample - y_sample)])
+        y_sample_distance.sort(key=lambda x: x[2])
+        x_neighs = [x for x, _, _ in y_sample_distance[:k]]
+        x_neighs_labels = [x for _, x, _ in y_sample_distance[:k]]
+        sample_neighs.append([x_sample, x_neighs, x_neighs_labels])
+
+        for index, a in enumerate(sample_associates):
+            a_sample = a[0]
+            for y_sample, _, _ in y_sample_distance[:k]:
+                if np.array_equal(a_sample, y_sample):
+                    sample_associates[index][1].append(x_sample)
+                    break
+
+    # Para cada x en S calcular with and without
+    final_samples = [x for x, _, _ in initial_distances]
+    final_labels = [x for _, x, _ in initial_distances]
+    samples_labels_dict = {tuple(x): y for x, y, _ in initial_distances}
+    removed = 0
+
+    for index in range(len(initial_distances)):
+        x_sample, x_label = initial_distances[index][0], initial_distances[
+            index][1]
+        x_associates = sample_associates[index]
+        with_, without = with_without(x_sample, x_associates[1],
+                                      samples_labels_dict, sample_neighs)
+
+        if without >= with_:
+            final_samples = np.delete(final_samples, index - removed, axis=0)
+            final_labels = np.delete(final_labels, index - removed, axis=0)
+
+            removed += 1
+            for associate in x_associates[1]:
+                for index_y, y in enumerate(sample_neighs):
+                    y_sample, y_neighs, y_neighs_labels = y
+                    if np.array_equal(associate, y_sample):
+                        # Eliminar x de la lista de vecinos de a
+                        for x_index, neigh in enumerate(y_neighs):
+                            if np.array_equal(x_sample, neigh):
+                                break
+                        del y_neighs[x_index]
+                        del y_neighs_labels[x_index]
+
+                        # Encontrar un nuevo vecino para a
+                        z_distances = []
+                        for z_sample, z_label in zip(final_samples,
+                                                     final_labels):
+                            if not np.array_equal(associate, z_sample):
+                                z_distance = np.linalg.norm(associate -
+                                                            z_sample)
+                                z_distances.append([z_sample, z_label,
+                                                    z_distance])
+                        z_distances.sort(key=lambda x: x[2])
+
+                        for neigh_sample, neigh_label, _ in z_distances[:k]:
+                            was_in = False
+                            for index_z, old_neigh in enumerate(y_neighs):
+                                if np.array_equal(neigh_sample, old_neigh):
+                                    was_in = True
+                                    break
+                            if not was_in:
+                                y_neighs.append(neigh_sample)
+                                y_neighs_labels.append(neigh_label)
+                                break
+                        sample_neighs[index_y][1] = y_neighs
+                        sample_neighs[index_y][2] = y_neighs_labels
+
+                        # Añadir a en la lista de asociados del nuevo vecino
+                        for index_z, z in enumerate(sample_associates):
+                            z_sample, z_associates = z
+                            if np.array_equal(z_sample, neigh_sample):
+                                z_associates.append(associate)
+                                break
+                        sample_associates[index_z][1] = z_associates
+                        break
+
+    S['data'] = final_samples
+    S['target'] = final_labels.tolist()
+
+    return S
+
+
+if __name__ == '__main__':
+    iris = load_iris()
+    print(f'Input samples: {len(iris.data)}')
+    S = DROP3(iris, 3)
+    print(f'Output samples: {len(S.data)}')
+    grafica_2D(S)
diff --git a/docs/bibliografia.bib b/docs/bibliografia.bib
index 3a73461..ba9934c 100644
--- a/docs/bibliografia.bib
+++ b/docs/bibliografia.bib
@@ -348,4 +348,15 @@ @inproceedings{zhou2004democratic
   pages={594--602},
   year={2004},
   organization={IEEE}
-}
\ No newline at end of file
+}
+
+@article{wilson2000reduction,
+  title={Reduction techniques for instance-based learning algorithms},
+  author={Wilson, D Randall and Martinez, Tony R},
+  journal={Machine learning},
+  volume={38},
+  number={3},
+  pages={257--286},
+  year={2000},
+  publisher={Springer}
+}
diff --git a/docs/memoria.pdf b/docs/memoria.pdf
index c0d1fb6..68f0a82 100644
Binary files a/docs/memoria.pdf and b/docs/memoria.pdf differ
diff --git a/docs/tex/3_Conceptos_teoricos.tex b/docs/tex/3_Conceptos_teoricos.tex
index fe8f6f1..f05d7f5 100644
--- a/docs/tex/3_Conceptos_teoricos.tex
+++ b/docs/tex/3_Conceptos_teoricos.tex
@@ -607,6 +607,58 @@ \subsubsection{Algoritmos de selección de instancias}\label{subsubsec:Instance-
 \end{algorithmic}
 \end{algorithm}
 
+\paragraph{\textit{Decremental Reduction Optimization Procedure}}\label{paragraph:DROP}
+\hfill \break
+Bajo el nombre de \textit{Decremental Reduction Optimization Procedure, DROP}~\cite{wilson2000reduction} nos encontramos con hasta 5 aproximaciones para la resolución del mismo problema. Todas ellas seleccionan prototipos en función de \textit{socio} y \textit{asociado}. Definidos como:
+\begin{itemize}
+\item Socio. Sea $X \not= \emptyset$, el socio de un objeto $P$ el cual pertence al conjunto $X$, es aquél objeto que tiene a $P$ como uno de sus $k$ vecinos más cercanos.
+\item Asociado. Todo prototipo que contenga a $P$ como a uno de sus $k$ vecinos más cercanos, será denominado asociado de $P$, denotado con la expresión $P.A_{1,\dots,a}$ donde $a$ es el número de asociados de $P$.
+\end{itemize}
+
+\begin{algorithm}[H]
+\caption{Algoritmo \textit{Decremental Reduction Optimization Procedure 3}, \textit{DROP3}.}\label{alg:DROP3}
+\begin{algorithmic}[1]
+\Require Conjunto de entrenamiento $X$ y número de vecinos más cercanos a considerar, $k$
+\Ensure Conjunto editado $S \subset X$
+\Statex
+\Procedure{DROP3}{$X, k$}
+	\State $T \leftarrow \text{Filtrado de ruido}(X)$ 
+	\State $S \leftarrow T$
+	\State Ordenar las instancias de $S$ por la distancia a su enemigo más próximo \Comment de mayor a menor
+	\ForAll{$x \in S$}
+		\State Encontrar los $x.N_{1\dots k+1}$, los $k+1$ vecniso más cercanos de $x$ en $S$
+		\State Añadir $x$ a la lista de asociados de cada uno de sus vecinos
+	\EndFor
+	\ForAll{$x \in S$}
+		\State $with \leftarrow$ \# número de asociados de $x$ clasificados correctamente \textbf{con} $x$ como vecino
+		\State $without \leftarrow$ \# número de asociados de $x$ clasificados correctamente \textbf{sin} $x$ como vecino
+		\If{$without \geq with$}
+			\State Eliminar $x$ de $S$
+			\ForAll{Asociado $a$ de $x$}
+				\State Eliminar $x$ de la lista de vecinos de $a$
+				\State Encontrar nuevo vecino para $a$
+				\State Añadir $a$ en la lista de asociados del nuevo vecino
+			\EndFor
+		\EndIf
+	\EndFor
+	\State \textbf{return} $S$
+\EndProcedure
+\end{algorithmic}
+\end{algorithm}
+
+Todas las aproximaciones de $DROP\lbrace 1\dots5\rbrace$ se basan en el mismo algoritmo~\cite{wilson2000reduction} pero con modificaciones el las técnicas de pre-procesado de los prototipos. Sus diferencias son:
+\begin{itemize}
+\item \textit{DROP1}. Eliminará un objeto $P$ de $S$ si sus socios en $S$ se clasifican correctamente sin $P$, i.e. la ausencia de $P$ no impide la correcta clasificación del resto de prototipos.
+\item \textit{DROP2}. Eliminará un objeto $P$ de $S$ si los socios que tiene $P$ en $TS$ se clasifican correctamente sin $P$, i.e., verificará el efecto que causa esta eliminación sobre la muestra original. Previo al proceso de eliminación de objetos $P$, ordena los prototipos a tratar en orden a su enemigo más cercano, permitiendo que los primeros prototipos que se van a tratar serán aquellos más alejados de las fronteras de decisión.
+\item \textit{DROP3}. Lo primero de todo realiza un filtrado de ruido, muy similar a la edición de Wilson, ver~en~\ref{paragraph:ENN}. Seguidamente aplica el algoritmo \textit{DROP2}, ver algoritmo~\ref{alg:DROP3}
+\item \textit{DROP4}. Aplica un filtro de ruido diferente, en este casos consistirá en eliminar un prototipo solo si su eliminación no provoca que alguna otra instancia sea mal clasificada.
+\item \textit{DROP5}. Modificación sobre \textit{DROP2}, en este algoritmo el proceso de eliminación de objetos comienza por aquellos más cercanos a sus enemigos. 
+\end{itemize}
+
+El concepto \textit{with} permite recoger el número de asociados correctamente clasificados teniendo en cuenta un prototipo $x$ como vecino, en cambio \textit{without} tiene en cuenta el número de asociados correctamente clasificados los cuales no tienen el prototipo $x$ como vecino. En los casos en los que $withput > with$ se está tratando con un prototipo el cual no aporta información sobre el conjunto $S$ permitiendo su eliminación.
+
+
+
 \vfill
 \section{Función distancia entre instancias}
 Una función distancia proporciona la proximidad entre dos instancias en función de todos sus parámetros. Si la distancia que separa dos instancias es cero, ambas instancias son idénticas. Se tiende a trabajar con conjuntos de datos normalizados, i.e. todos los datos son ajustados a una escala común, independientemente de la escala en la que hayan sido medidos, para evitar que atributos/características con mucha varianza puedan <<despistar>> a los algoritmos.


Test patch:
diff --git a/Instance Selection Algorithms/testing.py b/Instance Selection Algorithms/testing.py
index 7876a5b..9f74f5d 100644
--- a/Instance Selection Algorithms/testing.py
+++ b/Instance Selection Algorithms/testing.py
@@ -21,7 +21,7 @@
 
 from CNN import CNN
 from ENN import ENN
-from ICF_V2 import ICF
+from ICF import ICF
 from MSS import MSS
 from RNN import RNN