第五十五 数据挖掘

数据挖掘（Data Mining）是从大规模数据集中自动发现隐藏的、有价值的模式与知识的过程。它是连接数据库、统计学和机器学习的桥梁，在商业决策、科学研究、医疗健康、金融风控等领域有着广泛应用。Rust 以其卓越的性能和内存安全特性，正逐渐成为构建高性能数据处理管线的优选语言。本章将系统介绍数据挖掘的核心概念、经典算法，并展示如何用 Rust 实现关键的数据挖掘任务。

一、什么是数据挖掘

1.1 定义与目标

数据挖掘是从大量数据中提取隐含的、先前未知的、潜在有用信息的过程。它不是简单的数据查询或统计，而是通过算法自动发现数据中隐藏的模式（Pattern）、关联（Association）、异常（Anomaly）和趋势（Trend）。

数据挖掘的核心目标是将数据转化为知识。

1.2 KDD 过程

数据挖掘通常是**知识发现（Knowledge Discovery in Databases, KDD）**过程的核心步骤之一。完整的 KDD 流程包括：

数据选择 → 数据预处理 → 数据变换 → 数据挖掘 → 模式评估 → 知识表示

二、数据挖掘的核心任务

数据挖掘的任务可分为两大类：描述性任务和预测性任务。

2.1 描述性任务

描述性任务旨在发现数据中的内在结构和模式。

2.2 预测性任务

预测性任务利用已知数据预测未知属性或未来趋势。

三、经典数据挖掘算法

3.1 关联规则：Apriori 算法

Apriori 算法是挖掘频繁项集和关联规则的经典算法。其核心思想是：如果一个项集是频繁的，那么它的所有子集也必须是频繁的（Apriori 性质）。

关键指标：

#![allow(unused)]
fn main() {
use std::collections::{HashMap, HashSet};

/// 统计候选项集的支持度计数
fn scan_transactions(
    transactions: &[HashSet<&str>],
    candidates: &[HashSet<&str>],
) -> HashMap<HashSet<String>, usize> {
    let mut counts: HashMap<HashSet<String>, usize> = HashMap::new();
    for candidate in candidates {
        let mut count = 0;
        for transaction in transactions {
            if candidate.is_subset(transaction) {
                count += 1;
            }
        }
        counts.insert(
            candidate.iter().map(|s| s.to_string()).collect(),
            count,
        );
    }
    counts
}

/// 生成频繁项集（简化版 Apriori）
fn apriori_frequent_itemsets(
    transactions: &[HashSet<&str>],
    min_support: f64,
) -> Vec<(HashSet<String>, f64)> {
    let total = transactions.len() as f64;

    // 第一步：找出所有频繁 1-项集
    let mut item_counts: HashMap<&str, usize> = HashMap::new();
    for t in transactions {
        for item in t {
            *item_counts.entry(item).or_insert(0) += 1;
        }
    }

    let frequent_1: Vec<HashSet<String>> = item_counts
        .iter()
        .filter(|(_, &count)| count as f64 / total >= min_support)
        .map(|(&item, _)| {
            let mut set = HashSet::new();
            set.insert(item.to_string());
            set
        })
        .collect();

    let mut result: Vec<(HashSet<String>, f64)> = frequent_1
        .iter()
        .map(|itemset| {
            let support = item_counts[&*itemset.iter().next().unwrap()] as f64 / total;
            (itemset.clone(), support)
        })
        .collect();

    // 后续步骤：逐步生成 k-项集（简化，仅展示 2-项集）
    let mut prev_frequent = frequent_1;
    let mut k = 2;

    loop {
        let mut candidates: Vec<HashSet<String>> = Vec::new();
        let prev_vec: Vec<&HashSet<String>> = prev_frequent.iter().collect();
        for i in 0..prev_vec.len() {
            for j in (i + 1)..prev_vec.len() {
                let mut candidate = prev_vec[i].clone();
                candidate.extend(prev_vec[j].clone());
                if candidate.len() == k && !candidates.contains(&candidate) {
                    candidates.push(candidate);
                }
            }
        }

        if candidates.is_empty() {
            break;
        }

        let candidate_refs: Vec<HashSet<&str>> = candidates
            .iter()
            .map(|c| c.iter().map(|s| s.as_str()).collect())
            .collect();

        let counts = scan_transactions(transactions, &candidate_refs);

        prev_frequent.clear();
        for (itemset, count) in &counts {
            let support = *count as f64 / total;
            if support >= min_support {
                result.push((itemset.clone(), support));
                prev_frequent.push(itemset.clone());
            }
        }

        if prev_frequent.is_empty() {
            break;
        }
        k += 1;
    }

    result
}
}

3.2 聚类分析：K-Means 算法

K-Means 是最常用的划分聚类算法。它将 n 个数据点划分为 k 个簇，使得每个点到其所属簇中心的距离之和最小。

算法步骤：

1. 随机选择 k 个点作为初始簇中心
2. 将每个点分配到最近的簇中心
3. 重新计算每个簇的中心
4. 重复步骤 2-3 直到收敛

#![allow(unused)]
fn main() {
/// 二维数据点
#[derive(Debug, Clone, Copy)]
struct Point {
    x: f64,
    y: f64,
}

impl Point {
    fn distance(&self, other: &Point) -> f64 {
        ((self.x - other.x).powi(2) + (self.y - other.y).powi(2)).sqrt()
    }
}

/// K-Means 聚类
fn kmeans(data: &[Point], k: usize, max_iters: usize) -> Vec<(Point, Vec<usize>)> {
    let n = data.len();
    // 初始化：选择前 k 个点作为初始中心
    let mut centroids: Vec<Point> = data[..k].to_vec();
    let mut assignments = vec![0usize; n];

    for _ in 0..max_iters {
        // 分配：将每个点分配到最近的簇中心
        let mut changed = false;
        for (i, point) in data.iter().enumerate() {
            let nearest = centroids
                .iter()
                .enumerate()
                .min_by(|(_, a), (_, b)| {
                    a.distance(point).partial_cmp(&b.distance(point)).unwrap()
                })
                .map(|(idx, _)| idx)
                .unwrap();
            if assignments[i] != nearest {
                assignments[i] = nearest;
                changed = true;
            }
        }

        if !changed {
            break; // 已收敛
        }

        // 更新：重新计算每个簇的中心
        let mut sums = vec![(0.0f64, 0.0f64); k];
        let mut counts = vec![0usize; k];
        for (i, point) in data.iter().enumerate() {
            let c = assignments[i];
            sums[c].0 += point.x;
            sums[c].1 += point.y;
            counts[c] += 1;
        }
        for (j, centroid) in centroids.iter_mut().enumerate() {
            if counts[j] > 0 {
                centroid.x = sums[j].0 / counts[j] as f64;
                centroid.y = sums[j].1 / counts[j] as f64;
            }
        }
    }

    // 组装结果
    let mut clusters: Vec<(Point, Vec<usize>)> = centroids
        .into_iter()
        .map(|c| (c, Vec::new()))
        .collect();
    for (i, &cluster_id) in assignments.iter().enumerate() {
        clusters[cluster_id].1.push(i);
    }
    clusters
}
}

3.3 异常检测：基于 Z-Score 的方法

异常检测旨在识别偏离正常模式的数据点。Z-Score 方法是一种简单有效的统计方法。

$$Z = \frac{X - \mu}{\sigma}$$

其中 $\mu$ 为均值，$\sigma$ 为标准差。$|Z| > 3$ 通常被视为异常点。

#![allow(unused)]
fn main() {
/// 计算均值
fn mean(data: &[f64]) -> f64 {
    data.iter().sum::<f64>() / data.len() as f64
}

/// 计算标准差
fn std_dev(data: &[f64]) -> f64 {
    let m = mean(data);
    let variance = data.iter().map(|x| (x - m).powi(2)).sum::<f64>() / data.len() as f64;
    variance.sqrt()
}

/// Z-Score 异常检测
fn detect_anomalies_zscore(data: &[f64], threshold: f64) -> Vec<(usize, f64, f64)> {
    let m = mean(data);
    let s = std_dev(data);
    let mut anomalies = Vec::new();

    if s == 0.0 {
        return anomalies;
    }

    for (i, &value) in data.iter().enumerate() {
        let z = (value - m) / s;
        if z.abs() > threshold {
            anomalies.push((i, value, z));
        }
    }
    anomalies
}
}

3.4 分类：决策树

决策树是一种直观的分类算法，通过一系列 if-then 规则对数据进行分类。构建决策树的关键是选择最优划分属性，常用指标包括：

信息熵：

$$H(D) = -\sum_{k=1}^{K} p_k \log_2 p_k$$

其中 $p_k$ 是第 $k$ 类样本在数据集中的比例。

四、数据预处理

数据质量直接决定挖掘结果的好坏。“垃圾进，垃圾出”（Garbage In, Garbage Out）是数据挖掘领域的经典格言。

4.1 缺失值处理

4.2 数据归一化

不同特征的量纲差异会影响算法效果，需要进行标准化处理。

#![allow(unused)]
fn main() {
/// Min-Max 归一化
fn min_max_normalize(data: &[f64]) -> Vec<f64> {
    let min = data.iter().cloned().fold(f64::INFINITY, f64::min);
    let max = data.iter().cloned().fold(f64::NEG_INFINITY, f64::max);
    let range = max - min;
    if range == 0.0 {
        return vec![0.0; data.len()];
    }
    data.iter().map(|x| (x - min) / range).collect()
}

/// Z-Score 标准化
fn zscore_standardize(data: &[f64]) -> Vec<f64> {
    let m = mean(data);
    let s = std_dev(data);
    if s == 0.0 {
        return vec![0.0; data.len()];
    }
    data.iter().map(|x| (x - m) / s).collect()
}
}

4.3 特征工程

特征工程是数据挖掘中最关键的环节之一，好的特征往往比好的算法更重要。

五、模型评估

5.1 分类评估指标

5.2 交叉验证

交叉验证（Cross-Validation）是评估模型泛化能力的标准方法。最常用的是 k 折交叉验证：将数据分为 k 份，依次用每一份作为验证集，其余 k-1 份作为训练集，取 k 次评估的平均值作为最终结果。

#![allow(unused)]
fn main() {
/// k 折交叉验证的索引划分
fn k_fold_indices(n: usize, k: usize) -> Vec<(Vec<usize>, Vec<usize>)> {
    let fold_size = n / k;
    let mut folds = Vec::new();

    for i in 0..k {
        let start = i * fold_size;
        let end = if i == k - 1 { n } else { (i + 1) * fold_size };
        let val_indices: Vec<usize> = (start..end).collect();
        let train_indices: Vec<usize> = (0..start).chain(end..n).collect();
        folds.push((train_indices, val_indices));
    }
    folds
}
}

5.3 混淆矩阵

混淆矩阵是分类模型评估的基础工具：

六、Rust 数据挖掘生态

Rust 生态中有多个可用于数据挖掘任务的 crate：

6.1 使用 Polars 进行数据处理

Polars 是 Rust 生态中最强大的数据处理库，类似于 Python 的 Pandas，但性能更优。

use polars::prelude::*;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // 读取 CSV 文件
    let df = CsvReadOptions::default()
        .try_into_reader_with_file_path(Some("data.csv".into()))?
        .finish()?;

    // 基本统计信息
    println!("数据形状: {} 行 × {} 列", df.height(), df.width());
    println!("{}", df.describe(None)?);

    // 过滤和选择
    let filtered = df.clone().lazy()
        .filter(col("age").gt(lit(18)))
        .select([col("name"), col("age"), col("income")])
        .collect()?;

    println!("过滤后:\n{}", filtered);
    Ok(())
}

6.2 使用 Linfa 进行聚类

Linfa 提供了多种机器学习算法的 Rust 原生实现。

/*
[dependencies]
ndarray = "0.16"
*/
use linfa::prelude::*;
use linfa_clustering::KMeans;
use ndarray::Array2;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // 构造数据
    let data = Array2::from_shape_vec((6, 2), vec![
        1.0, 2.0,  1.5, 1.8,  5.0, 8.0,
        8.0, 8.0,  1.0, 0.6,  9.0, 11.0,
    ])?;

    let dataset = Dataset::from(data);

    // K-Means 聚类，k=2
    let model = KMeans::params(2)
        .max_n_iterations(100)
        .fit(&dataset)?;

    println!("簇中心:\n{}", model.centroids());

    // 预测新数据点的簇归属
    let prediction = model.predict(
        &Array2::from_shape_vec((1, 2), vec![2.0, 1.5])?
    );
    println!("新点所属簇: {:?}", prediction);

    Ok(())
}

七、数据挖掘的应用场景

八、总结与练习

本章小结

练习建议

1. 购物篮分析：用 Rust 实现 Apriori 算法，对一组交易数据挖掘频繁项集和关联规则，分析哪些商品经常一起被购买。
2. 客户分群：生成模拟的客户数据（年龄、收入、消费金额），使用 K-Means 进行聚类，分析不同客户群体的特征。
3. 异常检测器：实现 Z-Score 和 IQR（四分位距）两种异常检测方法，对比它们在含噪声数据上的检测效果。
4. 数据清洗管线：使用 Polars 读取 CSV 文件，完成缺失值填充、重复行删除、数据类型转换，输出清洗后的数据。
5. 分类器比较：用 Linfa 或 SmartCore 分别训练决策树和 KNN 分类器，使用交叉验证比较它们在鸢尾花数据集上的表现。
6. 端到端挖掘项目：选择一个公开数据集（如 Kaggle 上的泰坦尼克号数据集），完成从数据加载、探索性分析、特征工程到模型训练和评估的完整流程。