Antecedentes
Hace unos 15 años, aprendí sobre la existencia de
caminos fundamentales , grupos que pueden distinguir los espacios topológicos por la conectividad. El resto no será sobre ellos, pero se les ocurrió la idea de un regresor y un clasificador, sin ninguna optimización basada en el almacenamiento de la muestra.
Más detalles
Ideas y conjeturas.
Dado que las rutas fundamentales son bucles desde un punto seleccionado y equivalencia en ellos, entonces, ¿cómo pueden encontrarse dichos bucles en los datos? ¿Y es necesario?
La idea surgió por analogía con KNN y SVM: algoritmos "análogos". ¿Qué sucede si el bucle se reemplaza con una "tubería", un cilindro de un punto de datos a otro, y lo que cayó dentro de la tubería se asigna a la misma clase que estos dos puntos de la ruta (ya no es fundamental)? La "tubería" debe ser de un ancho tal que clasifique correctamente las clases ... y en el límite es una línea recta. La distancia a un nuevo punto desconocido debe ser mínima en el camino, entonces podemos atribuirla a la misma clase que la ruta.
Se puede construir un regresor proyectando un punto en una línea recta entre los puntos de datos e interpolando valores objetivo correspondientes a puntos de datos con la misma relación en la que la proyección divide la ruta.
Este método de construcción recuerda la muestra completa y proporciona predicciones precisas sobre el conjunto de entrenamiento.
Implementación primitiva
¿Cómo construir un camino? Tomé el elemento máximo de acuerdo con la norma y comencé a buscar el más cercano, conectando la ruta recibida. Al final, cerrado con el principio (discutible, por supuesto, pero así).
EstimadorEsta es la primera versión del código, vea el cuaderno actualizado a continuación.class PathMachine(BaseEstimator): def __init__(self, norm=np.linalg.norm, classify=False): self.norm = norm self.classify = classify def find_start(self, X): index_max = None value_max = -np.inf for index, x in enumerate(X): value = self.norm(x) if value > value_max: index_max = index value_max = value return index_max def find_next(self, point, target, X, y): index_min = None value_min = np.inf for index, x in enumerate(X): if self.classify and (y[index] != target): continue value = self.norm(x - point) if value < value_min: index_min = index value_min = value return index_min def fit(self, X, y): X = np.copy(X) y = np.copy(y).flatten() self.paths = {} if self.classify else [] start_index = self.find_start(X) start_value = X[start_index] start_target = y[start_index] X = np.delete(X, start_index, axis=0) y = np.delete(y, start_index, axis=0) while len(X) > 0: next_index = self.find_next(start_value, start_target, X, y) if self.classify and next_index is None: start_index = self.find_start(X) start_value = X[start_index] start_target = y[start_index] continue next_target = y[next_index] if self.classify: if not next_target in self.paths: self.paths[next_target] = [] self.paths[next_target].append({ 'start': start_value, 'next': X[next_index] }) else: self.paths.append({ 'start': start_value, 'next': X[next_index], 'value': start_target, 'target': next_target }) start_value = X[next_index] start_target = y[next_index] X = np.delete(X, next_index, axis=0) y = np.delete(y, next_index, axis=0) if self.classify: self.paths[start_target].append({ 'start': start_value, 'next': self.paths[start_target][0]['start'] }) else: self.paths.append({ 'start': start_value, 'next': self.paths[0]['start'], 'value': start_target, 'target': self.paths[0]['target'] }) return self def predict(self, X): result = [] for x in X: if self.classify: predicted = None min_distance = np.inf for target in self.paths: for path in self.paths[target]: point = x - path['start'] line = path['next'] - path['start'] if np.allclose(self.norm(line), 0): continue direction = line / self.norm(line) product = np.dot(point, direction) projection = product * direction distance = self.norm(projection - point) if distance < min_distance: predicted = target min_distance = distance result.append(predicted) else: predicted = None min_distance = np.inf for path in self.paths: point = x - path['start'] line = path['next'] - path['start'] if np.allclose(self.norm(line), 0): continue direction = line / self.norm(line) product = np.dot(point, direction) projection = product * direction parameter = np.sign(product) * self.norm(projection) /\ self.norm(line) distance = self.norm(projection - point) if distance < min_distance: predicted = (1 - parameter) * path['value'] +\ parameter * path['target'] min_distance = distance result.append(predicted) return np.array(result) def score(self, X, y): if self.classify: return f1_score(y.flatten(), self.predict(X), average='micro') else: return r2_score(y.flatten(), self.predict(X))
Teóricamente (y técnicamente), es posible hacer predic_proba de la misma manera, como 1, distancias normalizadas. Pero no tuve la oportunidad de probar realmente las probabilidades, así que ...
Algunas pruebas
Comencé con el clásico Boston Housing e Iris, y para la línea de base elegí Ridge y LogisticRegression. Bueno, qué, y si.
En general, sugiero mirar el
cuaderno jupyter .
En resumen: el regresor funcionó peor, el clasificador funcionó mejor.
Actualización: después de StandardScaler, el regresor funcionó mejor.También monté en conjuntos de datos sintéticos. Generalmente hay algo en el bosque, que es leña.
Pero esto se notó:
- El regresor funciona bien en espacios de pequeñas dimensiones,
- Tanto el regresor como el clasificador son sensibles al ruido, comenzando desde un cierto umbral,
- El regresor, a diferencia de la línea, sospechaba multimodalidad (en Boston Housing),
- Por construcción, el clasificador funcionó bien (lo mejor de todo ... :)) en un conjunto de lunas linealmente inseparable.
Conclusiones, pros, contras y aplicabilidad
Personalmente, no veo ninguna ventaja en la implementación actual. Tanto técnica como matemáticamente. Quizás esto se pueda modificar a algo más sensato. Por consiguiente, tampoco veo ninguna aplicabilidad particular. ¿Es posible trabajar con datos muy pequeños sin preprocesamiento ...
Hay muchas desventajas: es necesario mantener todo el conjunto de datos en la memoria, la capacidad de generalización se basa en la extrapolación, el hiperparámetro principal y único, la norma, no es susceptible de una enumeración de selección especial.
Pero, de todos modos, para mí lo recibido fue una sorpresa, que decidí compartir aquí.