# 传统编程 vs 机器学习
# 传统编程：人写规则
def is_good_watermelon_traditional(weight, color, root_sound):
    if weight > 3 and color == 'dark_green' and root_sound == '浊响':
        return '好瓜'
    else:
        return '坏瓜'

# 机器学习：从数据中学规则
def learn_from_data(data):
    """
    data: [(weight, color, root_sound, label), ...]
    算法自动从数据中学习判断规则
    """
    # 这里用简单的决策树作为示例
    from collections import Counter
    labels = [d[3] for d in data]
    return Counter(labels).most_common(1)[0][0]  # 返回多数类

import numpy as np

# 西瓜数据集（简化版）
# 特征：色泽(0=青绿,1=乌黑), 根蒂(0=蜷缩,1=稍蜷,2=硬挺), 敲声(0=浊响,1=沉闷)
X_train = np.array([
    [0, 0, 0],  # 青绿, 蜷缩, 浊响
    [1, 0, 0],  # 乌黑, 蜷缩, 浊响
    [1, 0, 1],  # 乌黑, 蜷缩, 沉闷
    [0, 0, 0],  # 青绿, 蜷缩, 浊响
    [1, 1, 0],  # 乌黑, 稍蜷, 浊响
    [0, 2, 0],  # 青绿, 硬挺, 浊响
    [1, 0, 0],  # 乌黑, 蜷缩, 浊响
    [0, 1, 1],  # 青绿, 稍蜷, 沉闷
])
y_train = np.array([1, 1, 0, 1, 1, 0, 1, 0])  # 1=好瓜, 0=坏瓜

import numpy as np
from collections import defaultdict

def simple_kmeans(X, k, max_iter=100):
    """
    K-Means 聚类算法
    X: 数据矩阵 (n_samples, n_features)
    k: 聚类数
    """
    n_samples = X.shape[0]
    # 随机初始化聚类中心
    centroids = X[np.random.choice(n_samples, k, replace=False)]
    
    for iteration in range(max_iter):
        # 分配样本到最近的聚类中心
        distances = np.sqrt(((X[:, np.newaxis] - centroids) ** 2).sum(axis=2))
        labels = np.argmin(distances, axis=1)
        
        # 更新聚类中心
        new_centroids = np.array([
            X[labels == i].mean(axis=0) if np.sum(labels == i) > 0 
            else centroids[i]
            for i in range(k)
        ])
        
        # 检查收敛
        if np.allclose(centroids, new_centroids):
            print(f"在第 {iteration + 1} 次迭代后收敛")
            break
        centroids = new_centroids
    
    return labels, centroids

# 生成模拟数据：两簇西瓜
np.random.seed(42)
cluster1 = np.random.randn(20, 2) + [2, 2]   # 好瓜簇
cluster2 = np.random.randn(20, 2) + [-1, -1]  # 坏瓜簇
X_unlabeled = np.vstack([cluster1, cluster2])

labels, centroids = simple_kmeans(X_unlabeled, k=2)
print(f"聚类中心:\n{centroids}")

# 半监督学习的直觉：标签传播
# 假设有少量标记数据和大量未标记数据
# 核心思想：相似的样本应该有相似的标签

def label_propagation_simple(X_labeled, y_labeled, X_unlabeled, k=3):
    """
    简单的KNN标签传播
    """
    y_unlabeled = np.zeros(len(X_unlabeled), dtype=int)
    X_all = np.vstack([X_labeled, X_unlabeled])
    
    for i, x in enumerate(X_unlabeled):
        # 计算与所有标记样本的距离
        distances = np.sqrt(((X_labeled - x) ** 2).sum(axis=1))
        # 找到最近的k个标记样本
        nearest_indices = np.argsort(distances)[:k]
        # 投票决定标签
        nearest_labels = y_labeled[nearest_indices]
        y_unlabeled[i] = np.bincount(nearest_labels).argmax()
    
    return y_unlabeled

# K-摇臂赌博机：最简单的强化学习问题
import numpy as np

class KArmedBandit:
    def __init__(self, k=10):
        self.k = k
        # 每个摇臂的真实奖励均值（智能体不知道）
        self.true_values = np.random.randn(k)
    
    def pull(self, action):
        """拉动某个摇臂，返回奖励"""
        return np.random.normal(self.true_values[action], 1.0)

class EpsilonGreedy:
    def __init__(self, k, epsilon=0.1):
        self.k = k
        self.epsilon = epsilon
        self.q_estimates = np.zeros(k)  # 估计价值
        self.action_counts = np.zeros(k)  # 动作计数
    
    def select_action(self):
        if np.random.random() < self.epsilon:
            return np.random.randint(self.k)  # 探索
        return np.argmax(self.q_estimates)     # 利用
    
    def update(self, action, reward):
        self.action_counts[action] += 1
        # 增量更新估计价值
        n = self.action_counts[action]]
        self.q_estimates[action] += (reward - self.q_estimates[action]) / n

# 模拟
bandit = KArmedBandit(k=10)
agent = EpsilonGreedy(k=10, epsilon=0.1)

rewards = []
for _ in range(1000):
    action = agent.select_action()
    reward = bandit.pull(action)
    agent.update(action, reward)
    rewards.append(reward)

print(f"真实最优动作: {np.argmax(bandit.true_values)}")
print(f"估计最优动作: {np.argmax(agent.q_estimates)}")
print(f"平均奖励: {np.mean(rewards[-100:]):.2f}")

# 假设空间的枚举
# 简化版：每个特征有3种取值 + "任意"（通配符*）
color_options = ['青绿', '乌黑', '*']      # * 表示任意色泽
root_options = ['蜷缩', '稍蜷', '硬挺', '*']
sound_options = ['浊响', '沉闷', '*']

hypothesis_space = []
for c in color_options:
    for r in root_options:
        for s in sound_options:
            if c == '*' and r == '*' and s == '*':
                continue  # 排除"什么都行"的假设
            hypothesis_space.append((c, r, s))

print(f"假设空间大小: {len(hypothesis_space)}")
# 输出: 假设空间大小: 3*4*3 - 1 = 35

# 训练数据
training_data = [
    {'color': '青绿', 'root': '蜷缩', 'sound': '浊响', 'label': '好瓜'},
    {'color': '乌黑', 'root': '蜷缩', 'sound': '浊响', 'label': '好瓜'},
    {'color': '乌黑', 'root': '蜷缩', 'sound': '沉闷', 'label': '坏瓜'},
    {'color': '青绿', 'root': '蜷缩', 'sound': '浊响', 'label': '好瓜'},
]

# 版本空间：与训练数据一致的所有假设
# 好瓜样本的色泽：青绿、乌黑 → 色泽不能确定（用*表示）
# 好瓜样本的根蒂：都是蜷缩 → 根蒂=蜷缩
# 好瓜样本的敲声：都是浊响 → 敲声=浊响
# 但还要检查是否与坏瓜样本不矛盾
# 坏瓜样本3：乌黑+蜷缩+沉闷 → 与假设 (*，蜷缩，浊响) 不矛盾（因为敲声不同）

# 版本空间中的一个假设示例
version_space_example = ('*', '蜷缩', '浊响')
print(f"版本空间中的一个假设: 色泽=任意, 根蒂=蜷缩, 敲声=浊响")

# 奥卡姆剃刀的直觉
# 假设有两个假设都能完美拟合训练数据：
# 假设1（简单）：如果色泽=乌黑且根蒂=蜷缩，则是好瓜
# 假设2（复杂）：如果(色泽=乌黑且根蒂=蜷缩且敲声=浊响)
#               或(色泽=青绿且根蒂=蜷缩且敲声=浊响且重量>3)，则是好瓜
# 奥卡姆剃刀倾向于选择假设1

# 在决策树中，这体现为偏好更浅的树
# 在线性模型中，这体现为正则化（偏好权重更小的模型）

# NFL定理的直觉演示
import numpy as np

def evaluate_algorithm(algo_func, target_func, X_test):
    """评估算法在某个目标函数上的表现"""
    predictions = algo_func(X_test)
    true_labels = target_func(X_test)
    return np.mean(predictions == true_labels)

# 算法A：简单线性分类器
def algo_a(X):
    return (X[:, 0] + X[:, 1] > 0).astype(int)

# 算法B：基于距离的分类器
def algo_b(X):
    return (np.sqrt(X[:, 0]**2 + X[:, 1]**2) > 1).astype(int)

# 在问题1上，A可能更好
# 在问题2上，B可能更好
# NFL定理说：对所有可能的问题取平均，A和B的期望性能相同

# NFL定理的实践启示
# 不要这样做：
# "我听说XGBoost是最好的算法，所有问题都用它"

# 应该这样做：
# 1. 理解数据特性（线性？非线性？高维？稀疏？）
# 2. 根据问题选择合适的候选算法
# 3. 通过交叉验证比较算法性能
# 4. 选择性能、效率、可解释性的最佳平衡

problem_characteristics = {
    '数据量': '大/中/小',
    '特征维度': '高维/低维',
    '特征类型': '连续/离散/混合',
    '线性可分性': '线性/非线性',
    '噪声水平': '高/中/低',
    '可解释性需求': '高/低',
}

# 机器学习算法发展时间线（简化）
timeline = {
    1957: "感知机 (Perceptron)",
    1967: "最近邻算法 (KNN)",
    1979: "决策树 (CART)",
    1986: "反向传播算法 (Backpropagation)",
    1995: "支持向量机 (SVM)",
    1997: "AdaBoost",
    2001: "随机森林 (Random Forest)",
    2006: "深度学习 (Deep Learning)",
    2012: "AlexNet - ImageNet竞赛冠军",
    2014: "GAN - 生成对抗网络",
    2017: "Transformer - Attention Is All You Need",
    2020: "GPT-3 - 大规模预训练语言模型",
}

for year, event in sorted(timeline.items()):
    print(f"{year}: {event}")

import numpy as np
from collections import Counter

# 西瓜数据集（周志华《机器学习》表1.1）
watermelon_data = [
    {'色泽': '青绿', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '好瓜': True},
    {'色泽': '乌黑', '根蒂': '蜷缩', '敲声': '沉闷', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '好瓜': True},
    {'色泽': '乌黑', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '好瓜': True},
    {'色泽': '青绿', '根蒂': '蜷缩', '敲声': '沉闷', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '好瓜': True},
    {'色泽': '乌黑', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '好瓜': True},
    {'色泽': '青绿', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '稍凹', '触感': '软粘', '好瓜': False},
    {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '稍糊', '脐部': '稍凹', '触感': '软粘', '好瓜': False},
    {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '稍凹', '触感': '硬滑', '好瓜': False},
    {'色泽': '青绿', '根蒂': '稍蜷', '敲声': '沉闷', '纹理': '稍糊', '脐部': '稍凹', '触感': '硬滑', '好瓜': False},
    {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '沉闷', '纹理': '稍糊', '脐部': '凹陷', '触感': '硬滑', '好瓜': False},
]

# 简单的统计学习：计算每个特征值与好瓜的关联
def analyze_feature(data, feature_name):
    """分析单个特征与标签的关联"""
    feature_values = set(d[feature_name] for d in data)
    print(f"\n特征: {feature_name}")
    for val in sorted(feature_values):
        subset = [d for d in data if d[feature_name] == val]
        good_count = sum(1 for d in subset if d['好瓜'])
        bad_count = len(subset) - good_count
        print(f"  {val}: 好瓜 {good_count}/{len(subset)}, "
              f"坏瓜 {bad_count}/{len(subset)}, "
              f"好瓜率 {good_count/len(subset):.1%}")

for feature in ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']:
    analyze_feature(watermelon_data, feature)

import numpy as np
from itertools import product

def nfl_simulation(n_problems=1000, n_train=10, n_test=10):
    """
    数值模拟NFL定理
    在所有可能的目标函数上比较两个算法的平均性能
    """
    n_samples = n_train + n_test
    n_features = 2
    X_all = np.random.randn(n_samples, n_features)
    
    # 生成所有可能的二分类目标函数
    # 对于n个样本，有2^n种可能的标签组合
    all_possible_targets = list(product([0, 1], repeat=n_samples))
    
    algo_a_scores = []
    algo_b_scores = []
    
    for target_labels in all_possible_targets[:n_problems]:  # 取部分问题
        y = np.array(target_labels)
        X_train, X_test = X_all[:n_train], X_all[n_train:]
        y_train, y_test = y[:n_train], y[n_train:]
        
        # 算法A：最近邻
        pred_a = np.zeros(n_test)
        for i, x in enumerate(X_test):
            dists = np.sqrt(((X_train - x) ** 2).sum(axis=1))
            pred_a[i] = y_train[np.argmin(dists)]
        
        # 算法B：多数类
        majority_class = 1 if y_train.sum() > n_train / 2 else 0
        pred_b = np.full(n_test, majority_class)
        
        algo_a_scores.append(np.mean(pred_a == y_test))
        algo_b_scores.append(np.mean(pred_b == y_test))
    
    print(f"算法A（最近邻）平均准确率: {np.mean(algo_a_scores):.4f}")
    print(f"算法B（多数类）平均准确率: {np.mean(algo_b_scores):.4f}")
    print(f"差异: {abs(np.mean(algo_a_scores) - np.mean(algo_b_scores)):.4f}")
    print("NFL定理预测：在所有问题上取平均，两个算法性能接近")

nfl_simulation(n_problems=100)

import numpy as np
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt

# 生成西瓜数据
np.random.seed(42)
n_good = 30
n_bad = 30

# 好瓜：重量大、颜色深、声音浊
good_weight = np.random.normal(3.5, 0.5, n_good)
good_density = np.random.normal(0.8, 0.1, n_good)

# 坏瓜：重量小、颜色浅、声音闷
bad_weight = np.random.normal(2.0, 0.5, n_bad)
bad_density = np.random.normal(0.4, 0.1, n_bad)

X = np.vstack([
    np.column_stack([good_weight, good_density]),
    np.column_stack([bad_weight, bad_density])
])
y = np.array([1] * n_good + [0] * n_bad)

# 监督学习：用标签训练分类器
from collections import defaultdict

def knn_predict(X_train, y_train, X_test, k=3):
    """KNN分类器"""
    predictions = []
    for x in X_test:
        dists = np.sqrt(((X_train - x) ** 2).sum(axis=1))
        nearest = np.argsort(dists)[:k]
        label = np.bincount(y_train[nearest].astype(int)).argmax()
        predictions.append(label)
    return np.array(predictions)

# 无监督学习：K-Means聚类
def kmeans(X, k, max_iter=100):
    centroids = X[np.random.choice(len(X), k, replace=False)]
    for _ in range(max_iter):
        dists = np.sqrt(((X[:, np.newaxis] - centroids) ** 2).sum(axis=2))
        labels = np.argmin(dists, axis=1)
        new_centroids = np.array([X[labels == i].mean(axis=0) for i in range(k)])
        if np.allclose(centroids, new_centroids):
            break
        centroids = new_centroids
    return labels

# 对比
# 监督学习：使用训练数据的标签
train_idx = np.random.choice(len(X), 40, replace=False)
test_idx = np.setdiff1d(np.arange(len(X)), train_idx)
pred_supervised = knn_predict(X[train_idx], y[train_idx], X[test_idx], k=3)
acc_supervised = np.mean(pred_supervised == y[test_idx])

# 无监督学习：不使用标签
cluster_labels = kmeans(X, k=2)
# 聚类结果需要与真实标签对齐
from scipy import stats
mode_labels = np.zeros_like(cluster_labels)
for c in range(2):
    mask = cluster_labels == c
    if mask.sum() > 0:
        mode_labels[mask] = stats.mode(y[mask], keepdims=True).mode[0]
acc_unsupervised = np.mean(mode_labels == y)

print(f"监督学习（KNN）准确率: {acc_supervised:.2%}")
print(f"无监督学习（K-Means）准确率: {acc_unsupervised:.2%}")
print("监督学习利用标签信息，通常效果更好")
print("无监督学习不需要标签，但性能通常较低")