机器学习进阶算法：AODE（Averaged One-Dependence Estimators）原理、手动计算与Python/Java双代码实战

import numpy as np
from collections import defaultdict

class AODE:
    def __init__(self, min_freq=1, alpha=1):
        self.min_freq = min_freq
        self.alpha = alpha
    
    def fit(self, X, y):
        """
        X: list of list, e.g., [['晴','热','高','弱'], ...]
        y: list of labels
        """
        self.n_samples = len(y)
        self.n_features = len(X[0])
        self.classes = list(set(y))
        
        # 统计 P(C, Xi=xi)
        self.joint_count = defaultdict(int)  # (class, feature_idx, value) -> count
        
        # 统计 P(Xj=xj | C, Xi=xi)
        self.cond_count = defaultdict(int)   # (class, parent_fi, parent_val, child_fj, child_val) -> count
        self.parent_total = defaultdict(int) # (class, parent_fi, parent_val) -> total count
        
        # 填充计数
        for i in range(self.n_samples):
            label = y[i]
            features = X[i]
            for fi in range(self.n_features):
                xi = features[fi]
                self.joint_count += 1
                self.parent_total += 1
                
                for fj in range(self.n_features):
                    if fj == fi: 
                        continue
                    xj = features[fj]
                    self.cond_count += 1
        
        # 构建唯一值集合（用于平滑）
        self.feature_values = [set() for _ in range(self.n_features)]
        for features in X:
            for fi, val in enumerate(features):
                self.feature_values[fi].add(val)
    
    def predict(self, X_test):
        predictions = []
        for features in X_test:
            class_scores = defaultdict(float)
            
            # 对每个类别
            for c in self.classes:
                total_score = 0.0
                
                # 尝试每个特征作为父节点
                for fi in range(self.n_features):
                    xi = features[fi]
                    parent_key = (c, fi, xi)
                    joint_freq = self.joint_count[parent_key]
                    
                    # 检查是否满足最小频次
                    if joint_freq < self.min_freq:
                        continue
                    
                    # 计算联合概率 P(C, Xi=xi) （平滑）
                    n_parent_vals = len(self.feature_values[fi])
                    smoothed_joint = joint_freq + self.alpha
                    # 分母可省略（比较用）
                    
                    # 计算条件概率乘积
                    cond_prob = 1.0
                    valid = True
                    for fj in range(self.n_features):
                        if fj == fi: 
                            continue
                        xj = features[fj]
                        cond_key = (c, fi, xi, fj, xj)
                        count = self.cond_count[cond_key]
                        total = self.parent_total[parent_key]
                        n_child_vals = len(self.feature_values[fj])
                        
                        # 平滑后的条件概率
                        p = (count + self.alpha) / (total + self.alpha * n_child_vals)
                        cond_prob *= p
                    
                    total_score += smoothed_joint * cond_prob
                
                class_scores[c] = total_score
            
            # 选择得分最高的类别
            pred = max(class_scores, key=class_scores.get)
            predictions.append(pred)
        
        return predictions

# 测试数据
X_train = [
    ["晴", "热", "高", "弱"],
    ["晴", "热", "高", "强"],
    ["阴", "热", "高", "弱"],
    ["雨", "凉", "正常", "弱"],
    ["雨", "冷", "正常", "弱"]
]
y_train = ["否", "否", "是", "是", "是"]

aode = AODE(min_freq=1, alpha=1)
aode.fit(X_train, y_train)

# 预测
X_test = 
pred = aode.predict(X_test)
print("预测结果:", pred[0])  # 输出: 否

import java.util.*;

public class AODE {
    private int minFreq;
    private double alpha;
    private Map<String, Integer> classSet = new HashMap<>();
    private List<Set<String>> featureValues = new ArrayList<>();
    private Map<List<Object>, Integer> jointCount = new HashMap<>();
    private Map<List<Object>, Integer> condCount = new HashMap<>();
    private Map<List<Object>, Integer> parentTotal = new HashMap<>();
    private int nFeatures;

    public AODE(int minFreq, double alpha) {
        this.minFreq = minFreq;
        this.alpha = alpha;
    }

    public void fit(List<List<String>> X, List<String> y) {
        nFeatures = X.get(0).size();
        for (int i = 0; i < nFeatures; i++) {
            featureValues.add(new HashSet<>());
        }
        Set<String> uniqueClasses = new HashSet<>(y);
        int idx = 0;
        for (String c : uniqueClasses) classSet.put(c, idx++);

        // 收集特征值
        for (List<String> row : X) {
            for (int i = 0; i < nFeatures; i++) {
                featureValues.get(i).add(row.get(i));
            }
        }

        // 统计
        for (int i = 0; i < X.size(); i++) {
            String label = y.get(i);
            List<String> features = X.get(i);
            for (int fi = 0; fi < nFeatures; fi++) {
                String xi = features.get(fi);
                List<Object> parentKey = Arrays.asList(label, fi, xi);
                jointCount.put(parentKey, jointCount.getOrDefault(parentKey, 0) + 1);
                parentTotal.put(parentKey, parentTotal.getOrDefault(parentKey, 0) + 1);

                for (int fj = 0; fj < nFeatures; fj++) {
                    if (fj == fi) continue;
                    String xj = features.get(fj);
                    List<Object> condKey = Arrays.asList(label, fi, xi, fj, xj);
                    condCount.put(condKey, condCount.getOrDefault(condKey, 0) + 1);
                }
            }
        }
    }

    public String predict(List<String> features) {
        Map<String, Double> scores = new HashMap<>();
        for (String c : classSet.keySet()) {
            double totalScore = 0.0;
            for (int fi = 0; fi < nFeatures; fi++) {
                String xi = features.get(fi);
                List<Object> parentKey = Arrays.asList(c, fi, xi);
                int jointFreq = jointCount.getOrDefault(parentKey, 0);
                if (jointFreq < minFreq) continue;

                double smoothedJoint = jointFreq + alpha;
                double condProb = 1.0;
                for (int fj = 0; fj < nFeatures; fj++) {
                    if (fj == fi) continue;
                    String xj = features.get(fj);
                    List<Object> condKey = Arrays.asList(c, fi, xi, fj, xj);
                    int count = condCount.getOrDefault(condKey, 0);
                    int total = parentTotal.getOrDefault(parentKey, 0);
                    int nChildVals = featureValues.get(fj).size();
                    double p = (count + alpha) / (total + alpha * nChildVals);
                    condProb *= p;
                }
                totalScore += smoothedJoint * condProb;
            }
            scores.put(c, totalScore);
        }

        return Collections.max(scores.entrySet(), Map.Entry.comparingByValue()).getKey();
    }

    // 测试
    public static void main(String[] args) {
        List<List<String>> X = Arrays.asList(
            Arrays.asList("晴", "热", "高", "弱"),
            Arrays.asList("晴", "热", "高", "强"),
            Arrays.asList("阴", "热", "高", "弱"),
            Arrays.asList("雨", "凉", "正常", "弱"),
            Arrays.asList("雨", "冷", "正常", "弱")
        );
        List<String> y = Arrays.asList("否", "否", "是", "是", "是");

        AODE aode = new AODE(1, 1.0);
        aode.fit(X, y);

        List<String> test = Arrays.asList("晴", "凉", "高", "弱");
        System.out.println("预测结果: " + aode.predict(test)); // 输出: 否
    }
}