first solution knn

[vshandrikov]

import numpy as np
from collections import Counter
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris, load_digits
iris = load_iris()
digits=load_digits()

class AdvancedKNN:
"""
Расширенный KNN-классификатор с различными функциями весов
"""

def __init__(self, k=5, metric='euclidean', weighting='uniform', 
            weight_function='inverse', epsilon=1e-6, p=2):
    """
    Инициализация классификатора
    
    Parameters:
    -----------
    k : int, количество соседей
    metric : str, метрика расстояния ('euclidean', 'manhattan', 'minkowski', 'chebyshev')
    weighting : str, тип взвешивания ('uniform', 'weighted')
    weight_function : str, функция веса ('inverse', 'inverse_square', 'exponential', 'gaussian')
    epsilon : float, малая константа для избежания деления на ноль
    p : float, параметр для метрики Минковского
    """
    self.k = k
    self.metric = metric
    self.weighting = weighting
    self.weight_function = weight_function
    self.epsilon = epsilon
    self.p = p
    self.X_train = None
    self.y_train = None
    
def _calculate_distance(self, x1, x2):
    """Вычисление расстояния между двумя точками по различным метрикам"""
    diff = x1 - x2
    
    if self.metric == 'euclidean':
        # Евклидово расстояние (L2)
        return np.sqrt(np.sum(diff ** 2))
        
    elif self.metric == 'manhattan':
        # Манхэттенское расстояние (L1)
        return np.sum(np.abs(diff))
        
    elif self.metric == 'minkowski':
        # Метрика Минковского (обобщение Lp)
        return np.sum(np.abs(diff) ** self.p) ** (1.0 / self.p)
        
    elif self.metric == 'chebyshev':
        # Расстояние Чебышева (L∞)
        return np.max(np.abs(diff))
        
    elif self.metric == 'cosine':
        # Косинусное расстояние (1 - косинусная близость)
        dot_product = np.dot(x1, x2)
        norm1 = np.linalg.norm(x1)
        norm2 = np.linalg.norm(x2)
        if norm1 == 0 or norm2 == 0:
            return 1.0
        return 1.0 - dot_product / (norm1 * norm2)
        
    else:
        raise ValueError(f"Метрика '{self.metric}' не поддерживается")

def _calculate_weight(self, distance):
    """Вычисление веса соседа на основе расстояния"""
    if self.weight_function == 'inverse':
        # Обратная пропорциональность: w = 1/(d + ε)
        return 1.0 / (distance + self.epsilon)
        
    elif self.weight_function == 'inverse_square':
        # Обратный квадрат: w = 1/(d² + ε)
        return 1.0 / (distance ** 2 + self.epsilon)
        
    elif self.weight_function == 'exponential':
        # Экспоненциальное убывание: w = exp(-d)
        return np.exp(-distance)
        
    elif self.weight_function == 'gaussian':
        # Гауссово ядро: w = exp(-d²/2σ²)
        sigma = 1.0  # параметр ширины ядра
        return np.exp(-distance ** 2 / (2 * sigma ** 2))
        
    elif self.weight_function == 'linear':
        # Линейное убывание: w = max(0, 1 - d/d_max)
        # (требует знания максимального расстояния)
        return max(0, 1.0 - distance)
        
    else:
        raise ValueError(f"Функция веса '{self.weight_function}' не поддерживается")

def _get_k_neighbors(self, x):
    """Поиск k ближайших соседей для точки x"""
    distances = []
    
    for i, x_train in enumerate(self.X_train):
        dist = self._calculate_distance(x, x_train)
        distances.append((dist, i))
    
    distances.sort(key=lambda x: x[0])
    return distances[:self.k]

def _predict_one(self, x):
    """Предсказание для одной точки"""
    neighbors = self._get_k_neighbors(x)
    
    if self.weighting == 'uniform':
        # Равномерное взвешивание
        neighbor_labels = [self.y_train[idx] for _, idx in neighbors]
        most_common = Counter(neighbor_labels).most_common(1)
        return most_common[0][0]
        
    elif self.weighting == 'weighted':
        # Взвешенное голосование
        label_weights = {}
        
        for dist, idx in neighbors:
            label = self.y_train[idx]
            weight = self._calculate_weight(dist)
            
            if label in label_weights:
                label_weights[label] += weight
            else:
                label_weights[label] = weight
        
        return max(label_weights.items(), key=lambda x: x[1])[0]
    
    else:
        raise ValueError(f"Тип взвешивания '{self.weighting}' не поддерживается")

def fit(self, X, y):
    """Обучение модели"""
    self.X_train = np.array(X)
    self.y_train = np.array(y)
    return self

def predict(self, X):
    """Предсказание меток для новых данных"""
    predictions = []
    for x in X:
        pred = self._predict_one(x)
        predictions.append(pred)
    return np.array(predictions)

def analyze_weight_functions():
"""Анализ различных функций весов"""
distances = np.linspace(0.1, 5, 100)

weight_functions = {
    'inverse': lambda d: 1.0 / (d + 1e-6),
    'inverse_square': lambda d: 1.0 / (d ** 2 + 1e-6),
    'exponential': lambda d: np.exp(-d),
    'gaussian': lambda d: np.exp(-d ** 2 / 2),
    'linear': lambda d: np.maximum(0, 1 - d/5)
}

plt.figure(figsize=(12, 8))

for name, func in weight_functions.items():
    weights = func(distances)
    plt.plot(distances, weights, label=name, linewidth=2)

plt.xlabel('Расстояние (d)', fontsize=12)
plt.ylabel('Вес соседа (w)', fontsize=12)
plt.title('Сравнение функций весов для KNN', fontsize=14)
plt.grid(True, alpha=0.3)
plt.legend(fontsize=11)
plt.tight_layout()
plt.show()

print("\nАнализ функций весов:")
print("-" * 60)
print("1. inverse (1/d):")
print("   - Быстро убывает при малых расстояниях")
print("   - Чувствительна к очень близким соседям")
print("   - Может быть нестабильной при d → 0")

print("\n2. inverse_square (1/d²):")
print("   - Убывает быстрее, чем 1/d")
print("   - Еще сильнее подчеркивает близких соседей")
print("   - Подавляет влияние дальних соседей")

print("\n3. exponential (exp(-d)):")
print("   - Плавное убывание")
print("   - Никогда не достигает нуля")
print("   - Хорошо работает при нормальном распределении ошибок")

print("\n4. gaussian (exp(-d²/2σ²)):")
print("   - Очень быстрое убывание")
print("   - Эффективно подавляет далекие точки")
print("   - Параметр σ контролирует ширину окрестности")

print("\n5. linear (max(0, 1-d/d_max)):")
print("   - Линейное убывание до нуля при d_max")
print("   - Простая интерпретация")
print("   - Требует знания или оценки максимального расстояния")

def test_weight_functions(dataset_name, X, y):
"""Тестирование различных функций весов на датасете"""
print(f"\n{'='*60}")
print(f"Тестирование функций весов на датасете {dataset_name}")
print('='*60)

# Разделение данных
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42, stratify=y
)

# Нормализация
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

results = {}
weight_functions = ['inverse', 'inverse_square', 'exponential', 'gaussian']

for wf in weight_functions:
    model = AdvancedKNN(k=5, metric='euclidean', 
                    weighting='weighted', weight_function=wf)
    model.fit(X_train_scaled, y_train)
    y_pred = model.predict(X_test_scaled)
    accuracy = accuracy_score(y_test, y_pred)
    results[wf] = accuracy
    
    print(f"{wf}: Точность = {accuracy:.4f}")

# Сравнение с равномерным взвешиванием
model_uniform = AdvancedKNN(k=5, metric='euclidean', weighting='uniform')
model_uniform.fit(X_train_scaled, y_train)
y_pred_uniform = model_uniform.predict(X_test_scaled)
accuracy_uniform = accuracy_score(y_test, y_pred_uniform)

print(f"\nРавномерное взвешивание: Точность = {accuracy_uniform:.4f}")

return results