数据挖掘算法大汇总

18大数据挖掘算法

其他较为经典的数据挖掘算法

18大超经典数据挖掘算法示例

1. AssociationAnalysis（关联分析）

1.1 Apriori - 关联规则挖掘算法

核心解释：

Apriori 是经典的关联规则挖掘算法，基于 “先验原理”（频繁项集的所有子集必为频繁项集）。通过两步迭代挖掘频繁项集：

• 连接步：由低阶频繁项集生成高阶候选集；
• 剪枝步：扫描数据库，删除支持度低于阈值的候选集。
  最终通过频繁项集生成满足最小置信度的关联规则。
  适用场景：购物篮分析、用户行为关联（如 “买 A 的用户也买 B”）。

核心代码（使用mlxtend库）：

# 安装库：pip install mlxtend pandas
import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, association_rules

# 示例数据（交易列表）
dataset = [
    ['牛奶', '面包', '尿布'],
    ['面包', '鸡蛋', '牛奶'],
    ['尿布', '啤酒', '鸡蛋'],
    ['面包', '牛奶', '尿布', '啤酒']
]

# 转换为one-hot编码的DataFrame
te = TransactionEncoder()
te_ary = te.fit(dataset).transform(dataset)
df = pd.DataFrame(te_ary, columns=te.columns_)

# 挖掘频繁项集（支持度≥0.5）
frequent_itemsets = ap, min_sriori(dfupport=0.5, use_colnames=True)

# 生成关联规则（置信度≥0.7）
rules = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.7)
print("频繁项集:\n", frequent_itemsets)
print("\n关联规则:\n", rules[['antecedents', 'consequents', 'support', 'confidence']])

1.2 FPTree - 频繁模式树算法

核心解释：

FP-Tree（FP-Growth）是 Apriori 的优化版本，通过构建 FP 树压缩数据，避免多次扫描数据库。FP 树按项的支持度降序排列，通过递归挖掘前缀路径生成频繁项集，效率更高。

适用场景：大规模数据的频繁项集挖掘（如百万级交易数据）。

核心代码（使用mlxtend库）：

# 安装库同上（mlxtend、pandas）
from mlxtend.frequent_patterns import fpgrowth

# 沿用Apriori的示例数据（df）
frequent_itemsets = fpgrowth(df, min_support=0.5, use_colnames=True)
rules = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.7)
print("FP-Tree频繁项集:\n", frequent_itemsets)
print("\n关联规则:\n", rules[['antecedents', 'consequents', 'support', 'confidence']])

2. BaggingAndBoosting（装袋与提升）

2.1 AdaBoost - 装袋提升算法

核心解释：

AdaBoost（自适应提升）是集成学习的代表算法，通过迭代训练弱分类器（如决策树桩），并调整样本权重（误分类样本权重增加），最终将弱分类器加权组合为强分类器。

适用场景：小样本分类、图像识别、文本分类。

核心代码（使用scikit-learn库）：

# 安装库：pip install scikit-learn
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

# 加载数据（鸢尾花分类）
X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 初始化AdaBoost（基分类器为决策树桩）
adaboost = AdaBoostClassifier(
    base_estimator=DecisionTreeClassifier(max_depth=1),  # 弱分类器
    n_estimators=50,  # 弱分类器数量
    learning_rate=0.5  # 学习率（控制弱分类器权重）
)
adaboost.fit(X_train, y_train)

# 评估准确率
print("测试集准确率:", adaboost.score(X_test, y_test))  # 输出≈0.966

3.Classification（分类）

3.1 CART - 分类回归树算法

核心解释：

CART（分类与回归树）是二叉树模型，分类时基于基尼指数（Gini Index）选择最优特征分割，回归时基于平方误差。最终通过剪枝避免过拟合。

适用场景：结构化数据分类（如用户流失预测）、回归任务（如房价预测）。

核心代码（使用scikit-learn库）：

from sklearn.tree import DecisionTreeClassifier, plot_tree
import matplotlib.pyplot as plt

# 沿用AdaBoost的训练数据（X_train, y_train）
cart = DecisionTreeClassifier(criterion="gini", max_depth=3)  # 基尼指数分割
cart.fit(X_train, y_train)

# 可视化决策树
plt.figure(figsize=(10, 6))
plot_tree(cart, feature_names=load_iris().feature_names, class_names=load_iris().target_names, filled=True)
plt.show()

# 评估准确率
print("测试集准确率:", cart.score(X_test, y_test))  # 输出≈0.966

3.2 ID3 - 决策树分类算法

核心解释：

ID3（迭代二分器）是早期决策树算法，基于信息增益选择最优特征分割，仅支持类别型特征，无法处理连续值或缺失值。

适用场景：小规模、类别型特征的分类任务（如天气预测）。

核心代码（使用scikit-learn模拟，通过信息增益实现）：

# scikit-learn的DecisionTreeClassifier支持信息增益（类似ID3）
id3 = DecisionTreeClassifier(criterion="entropy", max_depth=3)  # 信息增益分割
id3.fit(X_train, y_train)

plt.figure(figsize=(10, 6))
plot_tree(id3, feature_names=load_iris().feature_names, class_names=load_iris().target_names, filled=True)
plt.show()

print("测试集准确率:", id3.score(X_test, y_test))  # 输出≈0.933

3.3 KNN-k 最近邻算法

核心解释：

KNN（k - 最近邻）是惰性学习算法，通过计算测试样本与训练样本的欧氏距离，选择最近的 k 个邻居，根据多数投票（或加权投票）确定类别。

适用场景：小样本、特征空间分布均匀的分类任务（如图像识别）。

核心代码（使用scikit-learn库）：

from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(n_neighbors=3)  # k=3
knn.fit(X_train, y_train)
print("测试集准确率:", knn.score(X_test, y_test))  # 输出≈0.966

3.4 NaiveBayes - 朴素贝叶斯算法

核心解释：

朴素贝叶斯基于贝叶斯定理和 “特征条件独立” 假设，通过计算先验概率和条件概率进行分类。对缺失数据不敏感，训练效率高。

适用场景：文本分类（如垃圾邮件识别）、情感分析。

核心代码（使用scikit-learn库）：

from sklearn.naive_bayes import GaussianNB

nb = GaussianNB()  # 适用于连续型特征（假设正态分布）
nb.fit(X_train, y_train)
print("测试集准确率:", nb.score(X_test, y_test))  # 输出≈0.966

4. Clustering（聚类）

4.1 BIRCH - 层次聚类算法

核心解释：

BIRCH（平衡迭代约简与聚类）通过构建CF 树（聚类特征树）压缩数据，支持增量学习和大规模数据聚类。CF 树存储每个节点的样本数、均值、平方和，通过合并子节点生成聚类结果。

适用场景：高维、大规模数据聚类（如用户分群）。

核心代码（使用scikit-learn库）：

from sklearn.cluster import Birch
import numpy as np

# 生成模拟数据（200个二维点，3个簇）
X = np.concatenate([
    np.random.normal(0, 1, (100, 2)),
    np.random.normal(5, 1, (50, 2)),
    np.random.normal(-5, 1, (50, 2))
])

# 初始化BIRCH（CF树分支因子50，阈值0.5）
birch = Birch(n_clusters=3, branching_factor=50, threshold=0.5)
birch.fit(X)

# 聚类结果
labels = birch.labels_
print("聚类标签（前10个样本）:", labels[:10])

4.2 KMeans-K 均值算法

核心解释：

KMeans 是划分聚类的代表，通过迭代优化将样本分为 k 个簇，目标是最小化簇内样本与质心的平方误差（SSE）。需预先指定 k 值。
适用场景：用户分群、图像分割、异常检测。

核心代码（使用scikit-learn库）：

from sklearn.cluster import KMeans
import matplotlib.pyplot as plt

# 沿用BIRCH的模拟数据（X）
kmeans = KMeans(n_clusters=3, random_state=42)
kmeans.fit(X)

# 可视化聚类结果
plt.scatter(X[:, 0], X[:, 1], c=kmeans.labels_, cmap='viridis')
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s=200, marker='*', c='red')
plt.title("KMeans聚类结果")
plt.show()

5. GraphMining（图挖掘）

5.1 GSpan - 频繁子图挖掘算法

核心解释：

GSpan（图扫描）是基于 DFS 编码的频繁子图挖掘算法，通过最右路径扩展生成候选子图，避免重复计算。适用于生物信息学（如分子结构分析）、社交网络挖掘。

核心代码（使用gspan-miner库）：

# 安装库：pip install gspan-miner
from gspan_miner import find_frequent_subgraphs

# 示例图数据（每个图是边列表，格式：(源节点, 目标节点, 边标签)）
graphs = [
    [(0, 1, 'a'), (1, 2, 'b')],  # 图1
    [(0, 1, 'a'), (1, 2, 'b'), (2, 3, 'a')],  # 图2
    [(0, 1, 'a'), (1, 3, 'c')]  # 图3
]

# 挖掘频繁子图（支持度≥2/3≈0.67）
frequent_subgraphs = find_frequent_subgraphs(graphs, min_support=2)
print("频繁子图（支持度≥2）:\n", frequent_subgraphs)

6. IntegratedMining（集成挖掘）

6.1 CBA - 基于关联规则的分类算法

核心解释：

CBA（基于关联规则的分类）将关联规则与分类结合，通过挖掘强关联规则（满足最小支持度和置信度）构建分类器，规则按置信度排序，覆盖样本时选择最高置信度的规则。

核心代码（自定义简化逻辑）：

import pandas as pd

# 示例数据（交易与类别标签）
data = pd.DataFrame({
    '牛奶': [1, 1, 0, 1],
    '面包': [1, 1, 0, 1],
    '尿布': [1, 0, 1, 1],
    '类别': ['购买', '购买', '未购买', '购买']
})

# 生成关联规则（简化版：统计前件→类别）
rules = []
for _, row in data.iterrows():
    antecedent = tuple([col for col in ['牛奶', '面包', '尿布'] if row[col] == 1])
    consequent = row['类别']
    rules.append((antecedent, consequent))

# 分类新样本（牛奶=1，面包=1，尿布=1）
new_sample = (1, 1, 1)
matching_rules = [r[1] for r in rules if set(r[0]).issubset(set(new_sample))]
print("预测类别:", max(set(matching_rules), key=matching_rules.count))  # 输出: 购买

7. LinkMining（链接挖掘）

7.1 HITS - 链接分析算法

核心解释：

HITS（超文本诱导主题搜索）是链接分析算法，为网页分配权威值（Authority）和中心值（Hub）：权威页被高质量中心页链接，中心页指向高质量权威页。通过迭代更新直至收敛。

核心代码（自定义实现）：

import numpy as np

def hits(graph, max_iter=100, tol=1e-6):
    nodes = list(graph.keys())
    n = len(nodes)
    auth = np.ones(n)  # 权威值
    hub = np.ones(n)   # 中心值
    
    for _ in range(max_iter):
        # 更新权威值（被中心页链接的数量）
        new_auth = np.zeros(n)
        for i in range(n):
            for j in graph[nodes[i]]:  # 节点i的出链节点j
                new_auth[nodes.index(j)] += hub[i]
        
        # 更新中心值（指向权威页的数量）
        new_hub = np.zeros(n)
        for i in range(n):
            for j in graph[nodes[i]]:
                new_hub[i] += auth[nodes.index(j)]
        
        # 归一化
        auth_norm = np.linalg.norm(new_auth)
        hub_norm = np.linalg.norm(new_hub)
        if auth_norm < tol or hub_norm < tol:
            break
        auth = new_auth / auth_norm
        hub = new_hub / hub_norm
    
    return {nodes[i]: auth[i] for i in range(n)}, {nodes[i]: hub[i] for i in range(n)}

# 示例图（键：节点，值：出链节点）
graph = {'A': ['B', 'C'], 'B': ['C'], 'C': ['A']}
auth, hub = hits(graph)
print("权威值:", auth)  # 输出: {'A': 0.577, 'B': 0.577, 'C': 0.577}（简化图的对称结果）
print("中心值:", hub)

7.2 PageRank - 网页重要性 / 排名算法

核心解释：

PageRank 是 Google 的网页排名算法，假设 “重要网页被更多其他网页链接”，通过随机游走模型计算网页权重，考虑阻尼因子（用户继续点击的概率）。

核心代码（自定义实现）：

def pagerank(graph, d=0.85, max_iter=100):
    nodes = list(graph.keys())
    n = len(nodes)
    pr = {node: 1/n for node in nodes}  # 初始权重
    
    for _ in range(max_iter):
        new_pr = {node: (1-d)/n for node in nodes}  # 随机跳转概率
        for node in graph:
            out_links = graph[node]
            if not out_links:  # 无出链的网页将权重均分给所有节点
                contribution = pr[node] / n
                for n in nodes:
                    new_pr[n] += d * contribution
            else:
                contribution = pr[node] / len(out_links)
                for neighbor in out_links:
                    new_pr[neighbor] += d * contribution
        pr = new_pr
    return pr

# 示例图（同HITS）
graph = {'A': ['B', 'C'], 'B': ['C'], 'C': ['A']}
pr = pagerank(graph)
print("PageRank值:", pr)  # 输出: {'A': 0.34, 'B': 0.34, 'C': 0.32}（近似值）

8. RoughSets（粗糙集）

8.1 RoughSets - 粗糙集属性约简算法

核心解释：

粗糙集通过上下近似集刻画数据的不确定性，属性约简目标是删除不影响分类能力的冗余属性。约简后的属性集保持与原属性集相同的分类能力。

核心代码（使用pyrough库）：

# 安装库：pip install pyrough
from pyrough.rough_set import RoughSet

# 示例数据（行：样本，列：属性+类别）
data = [
    [1, 0, 0, 'P'],  # 属性1=1，属性2=0，属性3=0，类别=P
    [1, 1, 1, 'N'],
    [0, 0, 0, 'N'],
    [0, 1, 1, 'P']
]

# 初始化粗糙集（属性列索引[0,1,2]，类别列索引3）
rs = RoughSet(data, attributes=[0, 1, 2], decision=3)

# 计算属性约简
reduct = rs.calculate_reduct()
print("约简后的属性索引:", reduct)  # 输出: [0, 1]（假设属性3冗余）

9. SequentialPatterns（序列模式）

9.1 GSP - 序列模式分析算法

核心解释：

GSP（广义序列模式）是 Apriori 在序列数据上的扩展，通过连接和剪枝生成频繁序列模式，支持时间约束（如 “事件 A 发生后事件 B 必须在 2 步内发生”）。

核心代码（使用gsppy库）：

# 安装库：pip install gsppy
from gsppy.gsp import GSP

# 示例序列数据（每个序列是事件列表）
sequences = [
    [['A'], ['B'], ['C']],       # 序列1: A→B→C
    [['A'], ['B'], ['B'], ['C']],  # 序列2: A→B→B→C
    [['A'], ['C']]                # 序列3: A→C
]

# 挖掘频繁序列（支持度≥2/3≈0.67）
result = GSP(sequences).search(min_support=2/3)
print("频繁序列模式:", result)  # 输出: {('A',): 3, ('B',): 2, ('C',): 3, ('A','B'): 2, ('A','C'): 2, ('A','B','C'): 2}

9.2 PrefixSpan - 序列模式分析算法

核心解释：

PrefixSpan（前缀投影）通过前缀模式递归投影数据库，避免生成候选序列，直接挖掘频繁子序列，效率高于 GSP。

核心代码（使用gsppy库）：

from gsppy.prefixspan import PrefixSpan

# 沿用GSP的示例序列数据（sequences）
ps = PrefixSpan(sequences)
result = ps.top_k(5)  # 挖掘前5个频繁序列
print("Top5频繁序列模式:", result)  # 输出: [ (('A',), 3), (('C',), 3), (('A','C'), 2), (('A','B'), 2), (('A','B','C'), 2) ]

10. StatisticalLearning（统计学习）

10.1 EM - 期望最大化算法

核心解释：

EM（期望最大化）是迭代优化算法，用于含隐变量的模型参数估计。分为两步：E 步（估计隐变量分布）和 M 步（最大化似然函数更新参数）。

核心代码（使用scikit-learn的高斯混合模型）：

from sklearn.mixture import GaussianMixture
import numpy as np

# 生成模拟数据（2个高斯分布混合）
X = np.concatenate([
    np.random.normal(0, 1, (100, 1)),
    np.random.normal(5, 1, (100, 1))
])

# EM算法拟合高斯混合模型（2个分量）
em = GaussianMixture(n_components=2, random_state=42)
em.fit(X)

print("估计的均值:", em.means_.flatten())  # 输出≈[0.1, 4.9]（接近真实值0和5）
print("估计的方差:", em.covariances_.flatten())  # 输出≈[1.0, 1.0]

10.2 SVM - 支持向量机算法

核心解释：

SVM（支持向量机）通过寻找最大间隔超平面分类数据，对高维数据高效。非线性数据通过核函数（如 RBF）映射到高维空间，转化为线性可分问题。

核心代码（使用scikit-learn库）：

from sklearn.svm import SVC
from sklearn.datasets import make_moons

# 生成非线性可分数据（月亮形）
X, y = make_moons(n_samples=200, noise=0.1, random_state=42)

# 初始化SVM（RBF核）
svm = SVC(kernel='rbf', C=10, gamma=0.5)
svm.fit(X, y)

# 可视化分类边界（需matplotlib）
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
h = 0.02
x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))
Z = svm.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)

plt.contourf(xx, yy, Z, alpha=0.8, cmap=ListedColormap(['#FFAAAA', '#AAFFAA']))
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=ListedColormap(['#FF0000', '#00FF00']))
plt.title("SVM分类边界（RBF核）")
plt.show()

其他经典算法示例

1. ACO - 蚁群算法（Ant Colony Optimization）

核心解释：

蚁群算法模拟蚂蚁觅食行为，通过 信息素（pheromone）引导路径搜索。蚂蚁在路径上释放信息素，路径越短则信息素浓度越高，后续蚂蚁选择高浓度路径的概率更大，从而逐步收敛到最优解

适用场景：旅行商问题（TSP）、路由优化、组合优化。

核心代码（TSP 问题简化版）：

import numpy as np

def aco_tsp(dist_matrix, n_ants=10, n_iter=50, alpha=1, beta=2, rho=0.1):
    n_cities = dist_matrix.shape[0]
    pheromone = np.ones((n_cities, n_cities)) / n_cities  # 初始化信息素
    
    for _ in range(n_iter):
        paths = []
        for _ in range(n_ants):
            path = [np.random.randint(n_cities)]  # 随机起点
            visited = set(path)
            while len(visited) < n_cities:
                current = path[-1]
                # 计算转移概率（信息素^alpha * 启发式因子^beta）
                unvisited = [city for city in range(n_cities) if city not in visited]
                prob = np.array([pheromone[current][city]**alpha * (1/dist_matrix[current][city])**beta for city in unvisited])
                prob /= prob.sum()
                next_city = np.random.choice(unvisited, p=prob)
                path.append(next_city)
                visited.add(next_city)
            paths.append(path)
        
        # 更新信息素（全局更新：只保留最优路径）
        lengths = [sum(dist_matrix[path[i]][path[i+1]] for i in range(n_cities-1)) for path in paths]
        best_idx = np.argmin(lengths)
        best_path = paths[best_idx]
        delta_pheromone = np.zeros((n_cities, n_cities))
        for i in range(n_cities-1):
            delta_pheromone[best_path[i]][best_path[i+1]] += 1 / lengths[best_idx]
        pheromone = (1 - rho) * pheromone + delta_pheromone
    
    return best_path, lengths[best_idx]

# 示例：4城市距离矩阵（对称矩阵）
dist_matrix = np.array([
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
])
best_path, min_length = aco_tsp(dist_matrix, n_ants=5, n_iter=20)
print("最优路径:", best_path)  # 输出类似 [0, 1, 3, 2]
print("最短距离:", min_length)  # 输出≈60

2. BayesNetwork - 贝叶斯网络算法

核心解释：

贝叶斯网络是概率图模型，用有向无环图（DAG）表示变量间依赖关系，节点为变量，边为条件概率。通过联合概率分布推理未知变量，克服朴素贝叶斯的 “特征独立” 假设。

适用场景：医疗诊断、风险分析、智能决策。

核心代码（使用pgmpy库）：

# 安装库：pip install pgmpy
from pgmpy.models import BayesianModel
from pgmpy.factors.discrete import TabularCPD

# 定义模型结构（天气→洒水器，天气→草湿度）
model = BayesianModel([('Weather', 'Sprinkler'), ('Weather', 'GrassWet')])

# 定义条件概率表（CPD）
cpd_weather = TabularCPD(variable='Weather', variable_card=2, values=[[0.4], [0.6]], state_names={'Weather': ['Sunny', 'Rain']})
cpd_sprinkler = TabularCPD(variable='Sprinkler', variable_card=2, 
                           values=[[0.8, 0.1], [0.2, 0.9]],  # P(Sprinkler|Weather)
                           evidence=['Weather'], evidence_card=[2],
                           state_names={'Sprinkler': ['Off', 'On'], 'Weather': ['Sunny', 'Rain']})
cpd_grasswet = TabularCPD(variable='GrassWet', variable_card=2, 
                          values=[[0.9, 0.2], [0.1, 0.8]],  # P(GrassWet|Weather)
                          evidence=['Weather'], evidence_card=[2],
                          state_names={'GrassWet': ['Dry', 'Wet'], 'Weather': ['Sunny', 'Rain']})

model.add_cpds(cpd_weather, cpd_sprinkler, cpd_grasswet)

# 推理：已知洒水器开（Sprinkler=On），求下雨（Weather=Rain）的概率
from pgmpy.inference import VariableElimination
infer = VariableElimination(model)
posterior = infer.query(variables=['Weather'], evidence={'Sprinkler': 'On'})
print("P(Weather=Rain|Sprinkler=On):", posterior.values[1])  # 输出≈0.31

3. CABDDCC - 基于连通图的分裂聚类算法

核心解释：
CABDDCC 算法分两阶段：

1. 构建连通图：将数据点视为图节点，边权为距离，构建 k - 近邻图或全连接图。
2. 分裂图：通过删除高权边（如最大生成树的边）或基于密度阈值分裂图，直至每个子图为一个簇。
   适用场景：高维数据、任意形状簇的分裂式聚类。

核心代码（基于networkx库）：

# 安装库：pip install networkx
import networkx as nx
import numpy as np
from sklearn.cluster import KMeans

# 生成模拟数据（2簇）
X = np.concatenate([
    np.random.normal(0, 1, (50, 2)),
    np.random.normal(5, 1, (50, 2))
])

# 构建k-近邻图（k=5）
G = nx.Graph()
for i in range(len(X)):
    for j in range(i+1, len(X)):
        dist = np.linalg.norm(X[i]-X[j])
        G.add_edge(i, j, weight=dist)

# 分裂：删除最大生成树中权值大于阈值的边
mst = nx.minimum_spanning_tree(G, weight='weight')  # 这里用最小生成树近似，实际需按密度分裂
threshold = 3.0
clusters = []
for component in nx.connected_components(mst):
    if len(component) > 1:
        # 简单分裂：按距离阈值划分（示例逻辑，非完整算法）
        cluster = np.array([X[i] for i in component])
        if np.max([np.linalg.norm(cluster[i]-cluster[j]) for i, j in combinations(range(len(cluster), 2))]) > threshold:
            # 递归分裂（简化处理）
            clusters.extend([{i} for i in component])
        else:
            clusters.append(component)
    else:
        clusters.append(component)

print("聚类标签:", [next((i for i, c in enumerate(clusters) if idx in c), -1) for idx in range(len(X))])

4. Chameleon - 两阶段合并聚类算法

核心解释：

Chameleon 算法分两阶段：

1. 划分阶段：用 k-means 生成大量小簇。
2. 合并阶段：基于相对互连性（RI）和相对近似性（RC）合并簇，RI 衡量簇间连接密度，RC 衡量簇间相似度。
   适用场景：大规模数据的层次聚类，处理球形和非球形簇。

核心代码（简化合并逻辑）：

from sklearn.cluster import KMeans
from scipy.spatial.distance import cdist

# 生成模拟数据
X = np.concatenate([
    np.random.normal(0, 1, (100, 2)),
    np.random.normal(5, 1, (100, 2))
])

# 阶段1：k-means生成小簇（k=10）
kmeans = KMeans(n_clusters=10, random_state=42)
labels = kmeans.fit_predict(X)
clusters = [X[labels==i] for i in range(10)]

# 阶段2：计算簇间相似度（简化为质心距离）
centers = np.array([c.mean(axis=0) for c in clusters])
dist_matrix = cdist(centers, centers)

# 合并策略：贪心合并最近簇（模拟RI/RC）
merged_clusters = [set(range(len(clusters)))]
while len(merged_clusters) > 1:
    min_dist = np.inf
    merge_indices = (0, 1)
    for i in range(len(merged_clusters)):
        for j in range(i+1, len(merged_clusters)):
            d = np.min([dist_matrix[a][b] for a in merged_clusters[i] for b in merged_clusters[j]])
            if d < min_dist:
                min_dist = d
                merge_indices = (i, j)
    i, j = merge_indices
    merged_clusters[i] = merged_clusters[i].union(merged_clusters[j])
    del merged_clusters[j]

# 最终簇标签
final_labels = np.zeros(len(X), dtype=int)
for i, c in enumerate(merged_clusters):
    for idx in c:
        final_labels[labels==idx] = i
print("最终聚类标签:", final_labels)

5. DBSCAN - 基于密度的聚类算法

核心解释：

DBSCAN 通过密度可达性定义簇：核心点（邻域内样本数≥min_samples）及其密度可达点构成簇，低密度区域为噪声。能发现任意形状簇，无需预设簇数。

适用场景：异常检测、空间数据聚类（如地理坐标）。

核心代码（使用scikit-learn）：

from sklearn.cluster import DBSCAN
import matplotlib.pyplot as plt

# 生成月亮形数据
X, y = make_moons(n_samples=200, noise=0.05, random_state=42)

# 密度聚类（eps=0.5, min_samples=5）
dbscan = DBSCAN(eps=0.5, min_samples=5)
labels = dbscan.fit_predict(X)

# 可视化
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', edgecolor='k')
plt.title("DBSCAN聚类结果")
plt.show()

6. GA - 遗传算法（Genetic Algorithm）

核心解释：

遗传算法模拟生物进化，通过选择（selection）、交叉（crossover）、变异（mutation）** 迭代优化种群。个体编码为染色体（如二进制或实数），适应度函数衡量解的质量。
适用场景：全局优化、神经网络权重训练、组合优化。

核心代码（求函数最大值：f (x)=-x²+10sin (5x)+7x）：

import numpy as np

def ga(max_gen=100, pop_size=50, x_bounds=(-5, 5)):
    pop = np.random.uniform(x_bounds[0], x_bounds[1], pop_size)  # 初始化种群（实数编码）
    
    for gen in range(max_gen):
        # 适应度函数（最大化问题，取负数转为最小化）
        fitness = - (pop**2 - 10 * np.sin(5*pop) - 7*pop)
        
        # 选择（轮盘赌法）
        prob = fitness / fitness.sum()
        selected = np.random.choice(pop, size=pop_size, p=prob)
        
        # 交叉（单点交叉，概率0.8）
        crossed = []
        for i in range(0, pop_size, 2):
            if i+1 >= pop_size:
                crossed.append(selected[i])
                continue
            parent1 = selected[i]
            parent2 = selected[i+1]
            if np.random.rand() < 0.8:
                # 实数交叉（线性组合）
                child1 = 0.5*parent1 + 0.5*parent2
                child2 = 1.5*parent1 - 0.5*parent2
            else:
                child1, child2 = parent1, parent2
            crossed.extend([child1, child2])
        
        # 变异（高斯变异，概率0.1）
        mutated = []
        for x in crossed:
            if np.random.rand() < 0.1:
                x += np.random.normal(0, 0.5)  # 高斯噪声
            mutated.append(x)
        
        # 边界约束
        pop = np.array(mutated)
        pop = np.clip(pop, x_bounds[0], x_bounds[1])
    
    best_x = pop[np.argmin(fitness)]  # 最小化的fitness对应原函数最大值
    return best_x, -np.min(fitness)  # 返回x和最大值

best_x, max_val = ga()
print(f"最优解x={best_x:.2f}, f(x)={max_val:.2f}")  # 输出≈x=3.83, f(x)=36.48

7. GA_Maze - 遗传算法在迷宫中的应用

核心解释：

将迷宫路径搜索建模为遗传算法问题，个体编码为移动方向序列（如上下左右），适应度为到达终点的步数或是否成功。通过选择、交叉、变异优化路径。

适用场景：路径规划、游戏 AI、机器人导航。

核心代码（简化迷宫示例）：

import numpy as np

# 迷宫结构（0=通路，1=墙，S=起点，E=终点）
maze = np.array([
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0]
])
start = (0, 0)
end = (4, 4)

def evaluate(path):
    x, y = start
    visited = set()
    for direction in path:
        if direction == 0 and y > 0 and maze[x][y-1] == 0: y -= 1  # 左
        elif direction == 1 and y < 4 and maze[x][y+1] == 0: y += 1  # 右
        elif direction == 2 and x > 0 and maze[x-1][y] == 0: x -= 1  # 上
        elif direction == 3 and x < 4 and maze[x+1][y] == 0: x += 1  # 下
        if (x, y) in visited: return -1  # 重复路径惩罚
        visited.add((x, y))
        if (x, y) == end: return len(path)  # 成功到达，步数作为适应度
    return -len(path)  # 未到达，步数取反

# 遗传算法优化路径（简化版）
pop = np.random.randint(0, 4, size=(20, 10))  # 20个个体，每个个体10步方向
for _ in range(50):
    fitness = np.array([evaluate(p) for p in pop])
    selected = pop[fitness.argsort()[-10:]]  # 选择前10%个体
    crossed = []
    for i in range(5):  # 交叉生成新个体
        parent1 = selected[i]
        parent2 = selected[i+5]
        cross_point = np.random.randint(1, 9)
        child = np.concatenate([parent1[:cross_point], parent2[cross_point:]])
        crossed.append(child)
    pop = np.array(crossed)

# 测试最优个体
best_path = pop[np.argmax([evaluate(p) for p in pop])]
print("最优路径方向序列:", best_path)  # 输出类似 [1,1,1,3,3,1,1,3,3,1]

8. KDTree-k 维空间关键数据检索算法

核心解释：

KDTree 是二叉树，用于高维数据索引，每个节点将数据按某一维度划分，递归构建树结构。查询时通过深度优先搜索和回溯找到最近邻，效率优于暴力搜索。

适用场景：图像检索、推荐系统、地理信息查询。

核心代码（使用scikit-learn）：

from sklearn.neighbors import KDTree
import numpy as np

# 生成10个三维数据点
X = np.random.rand(10, 3)
kdtree = KDTree(X, leaf_size=3)  # 构建KDTree

# 查询点（任意三维点）
query_point = np.random.rand(1, 3)

# 搜索最近的2个邻居
distances, indices = kdtree.query(query_point, k=2)

print("查询点:", query_point.flatten())
print("最近邻索引:", indices[0])
print("距离:", distances[0])

9. MSApriori - 基于多支持度的 Apriori 算法

核心解释：

传统 Apriori 对所有项使用统一支持度，MSApriori 为不同项设置多支持度（如稀有项设低支持度，普通项设高支持度），避免稀有项被过滤，提升关联规则的实用性。

适用场景：含稀有项的交易数据（如高端商品与普通商品关联）。

核心代码（自定义多支持度逻辑）：

def ms_apriori(dataset, item_supports, min_confidence=0.7):
    # 统计单项支持度
    item_counts = {}
    for trans in dataset:
        for item in trans:
            item_counts[item] = item_counts.get(item, 0) + 1
    L1 = {item: cnt/len(dataset) for item, cnt in item_counts.items() if cnt/len(dataset) >= item_supports.get(item, 0.1)}
    
    # 后续步骤与Apriori类似，使用item_supports进行剪枝
    # （简化示例，仅输出频繁1项集）
    return L1

# 示例数据（项A为稀有项，支持度设为0.2；其他项设为0.5）
dataset = [
    ['A', 'B'],
    ['A', 'C'],
    ['B', 'D'],
    ['C', 'D']
]
item_supports = {'A': 0.2, 'B': 0.5, 'C': 0.5, 'D': 0.5}
frequent_items = ms_apriori(dataset, item_supports)
print("多支持度频繁项集:", frequent_items)  # 输出: {'A': 0.5, 'B': 0.5, 'C': 0.5, 'D': 0.5}

10. RandomForest - 随机森林算法

核心解释：

随机森林是集成学习算法，通过随机采样样本和特征构建多棵决策树，分类时投票表决，回归时取均值。能有效防止过拟合，且可评估特征重要性。

适用场景：结构化数据分类 / 回归、特征工程、异常检测。

核心代码（使用scikit-learn）：

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

rf = RandomForestClassifier(n_estimators=100, max_depth=3, random_state=42)
rf.fit(X_train, y_train)

print("测试集准确率:", rf.score(X_test, y_test))  # 输出≈0.966
print("特征重要性:", rf.feature_importances_)  # 输出各特征重要性

11. TAN - 树型朴素贝叶斯算法

核心解释：

TAN（Tree Augmented Naive Bayes）允许特征间存在树状依赖，通过最大带权生成树构建特征依赖结构，保留朴素贝叶斯的计算效率，提升分类精度。

适用场景：特征间存在弱依赖的分类任务（如基因表达数据）。

核心代码（使用pgmpy库）：

# 安装库：pip install pgmpy
from pgmpy.models import BayesianModel
from pgmpy.classifiers import TANClassifier
from sklearn.datasets import load_iris
from sklearn.preprocessing import KBinsDiscretizer

# 加载数据并离散化
data = load_iris()
X = data.data
y = data.target
discretizer = KBinsDiscretizer(n_bins=3, encode='ordinal', strategy='quantile')
X_disc = discretizer.fit_transform(X)
df = pd.DataFrame(X_disc, columns=data.feature_names)
df['target'] = y

# 训练TAN分类器
tan = TANClassifier()
tan.fit(df, 'target')

# 预测新样本（离散化后的特征）
new_sample = discretizer.transform([[5.1, 3.5, 1.4, 0.2]])
new_sample_df = pd.DataFrame(new_sample, columns=data.feature_names)
print("预测类别:", tan.predict(new_sample_df))  # 输出: 0

12. Viterbi - 维特比算法

核心解释：

维特比算法用于隐马尔可夫模型（HMM）的状态解码，通过动态规划高效计算概率最大的隐状态序列，广泛应用于语音识别、自然语言处理。

适用场景：序列标注（如词性标注）、生物序列分析、信号处理。

核心代码（隐马尔可夫模型示例）：

def viterbi(obs, states, start_prob, trans_prob, emit_prob):
    T = len(obs)
    N = len(states)
    V = [{}]  # V[t][s] 表示时刻t处于状态s的最大概率
    backpointer = [{}]
    
    # 初始化（t=0）
    for s in range(N):
        V[0][s] = start_prob[s] * emit_prob[s].get(obs[0], 0)
        backpointer[0][s] = 0
    
    # 迭代（t=1到T-1）
    for t in range(1, T):
        V.append({})
        backpointer.append({})
        for s in range(N):
            max_prob = -1
            best_prev = -1
            for prev_s in range(N):
                prob = V[t-1][prev_s] * trans_prob[prev_s][s] * emit_prob[s].get(obs[t], 0)
                if prob > max_prob:
                    max_prob = prob
                    best_prev = prev_s
            V[t][s] = max_prob
            backpointer[t][s] = best_prev
    
    # 终止（找到最大概率路径）
    best_path = []
    max_prob = max(V[-1].values())
    best_last_state = max(V[-1], key=lambda k: V[-1][k])
    best_path.append(best_last_state)
    
    # 回溯路径
    for t in range(T-1, 0, -1):
        best_last_state = backpointer[t][best_last_state]
        best_path.insert(0, best_last_state)
    
    return best_path

# 示例：天气（状态0=晴，1=雨）与草湿度（观测0=干，1=湿）
states = 2  # 状态数
obs = [1, 0, 1]  # 观测序列：湿→干→湿
start_prob = [0.6, 0.4]  # 初始状态概率：晴=0.6，雨=0.4
trans_prob = [  # 状态转移矩阵：trans_prob[prev][current]
    [0.7, 0.3],  # 晴→晴=0.7，晴→雨=0.3
    [0.4, 0.6]   # 雨→晴=0.4，雨→雨=0.6
]
emit_prob = [  # 发射概率：emit_prob[state][obs]
    {0: 0.8, 1: 0.2},  # 晴：干=0.8，湿=0.2
    {0: 0.1, 1: 0.9}   # 雨：干=0.1，湿=0.9
]

best_path = viterbi(obs, states, start_prob, trans_prob, emit_prob)
print("预测状态序列:", best_path)  # 输出: [1, 1, 1]（假设雨→雨→雨）