下载：文本聚类

下载：

TextVectorizer.java

package cn.edu.bjut.textmining.util;
 
import java.io.IOException;
import java.io.UncheckedIOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
 
/**
 * Shared utility for Chapter 5 demos. The input documents are assumed to be pre-tokenized with
 * spaces.
 */
public final class TextVectorizer {
    private TextVectorizer() {}
 
    public static double[][] tfIdf(List<String> documents) {
        Map<String, Integer> vocabulary = new LinkedHashMap<>();
        List<List<String>> tokenized = new ArrayList<>();
 
        for (String document : documents) {
            List<String> tokens = tokenize(document);
            tokenized.add(tokens);
            for (String token : tokens) {
                vocabulary.putIfAbsent(token, vocabulary.size());
            }
        }
 
        int n = documents.size();
        int v = vocabulary.size();
        int[] documentFrequency = new int[v];
        for (List<String> tokens : tokenized) {
            Set<String> uniqueTokens = new HashSet<>(tokens);
            for (String token : uniqueTokens) {
                documentFrequency[vocabulary.get(token)]++;
            }
        }
 
        double[][] vectors = new double[n][v];
        for (int i = 0; i < n; i++) {
            Map<String, Integer> termFrequency = new HashMap<>();
            for (String token : tokenized.get(i)) {
                termFrequency.put(token, termFrequency.getOrDefault(token, 0) + 1);
            }
            for (Map.Entry<String, Integer> entry : termFrequency.entrySet()) {
                int index = vocabulary.get(entry.getKey());
                double idf = Math.log((n + 1.0) / (documentFrequency[index] + 1.0)) + 1.0;
                vectors[i][index] = entry.getValue() * idf;
            }
            normalize(vectors[i]);
        }
        return vectors;
    }
 
    public static List<String> readDocuments(Path path) {
        try {
            List<String> lines = Files.readAllLines(path, StandardCharsets.UTF_8);
            List<String> documents = new ArrayList<>();
            for (String line : lines) {
                String trimmed = line.trim();
                if (!trimmed.isEmpty() && !trimmed.startsWith("#")) {
                    documents.add(trimmed);
                }
            }
            return documents;
        } catch (IOException e) {
            throw new UncheckedIOException("读取文本失败：" + path.toAbsolutePath(), e);
        }
    }
 
    public static double cosine(double[] a, double[] b) {
        if (a.length != b.length) {
            throw new IllegalArgumentException("向量维度不同");
        }
        double dot = 0.0;
        double normA = 0.0;
        double normB = 0.0;
        for (int i = 0; i < a.length; i++) {
            dot += a[i] * b[i];
            normA += a[i] * a[i];
            normB += b[i] * b[i];
        }
        if (normA == 0.0 || normB == 0.0) {
            return 0.0;
        }
        return Math.max(-1.0, Math.min(1.0, dot / (Math.sqrt(normA) * Math.sqrt(normB))));
    }
 
    public static double cosineDistance(double[] a, double[] b) {
        return 1.0 - cosine(a, b);
    }
 
    public static void normalize(double[] vector) {
        double sum = 0.0;
        for (double value : vector) {
            sum += value * value;
        }
        double norm = Math.sqrt(sum);
        if (norm == 0.0) {
            return;
        }
        for (int i = 0; i < vector.length; i++) {
            vector[i] /= norm;
        }
    }
 
    public static double[] centroid(double[][] data, int[] labels, int targetLabel) {
        int d = data[0].length;
        double[] center = new double[d];
        int count = 0;
        for (int i = 0; i < data.length; i++) {
            if (labels[i] == targetLabel) {
                count++;
                for (int j = 0; j < d; j++) {
                    center[j] += data[i][j];
                }
            }
        }
        if (count == 0) {
            return center;
        }
        for (int j = 0; j < d; j++) {
            center[j] /= count;
        }
        normalize(center);
        return center;
    }
 
    private static List<String> tokenize(String document) {
        String[] parts = document.trim().split("\\s+");
        List<String> tokens = new ArrayList<>();
        for (String part : parts) {
            if (!part.trim().isEmpty()) {
                tokens.add(part);
            }
        }
        return tokens;
    }
}

package cn.edu.bjut.textmining.chapter5.support;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;
 
/** 九篇标题和同一个词表，所有小样本实验保持一致。 */
public final class SampleNews {
    public static List<TNewsCorpusLoader.NewsRecord> load() {
        List<TNewsCorpusLoader.NewsRecord> result = new ArrayList<>();
        try (BufferedReader reader =
                Files.newBufferedReader(
                        ProjectPaths.data("news_sample.tsv"), StandardCharsets.UTF_8)) {
            reader.readLine();
            String line;
            while ((line = reader.readLine()) != null) {
                String[] fields = line.split("\t", 4);
                result.add(
                        new TNewsCorpusLoader.NewsRecord(
                                fields[2], fields[3], Integer.parseInt(fields[1])));
            }
        } catch (IOException e) {
            throw new UncheckedIOException("读取九条新闻失败", e);
        }
        if (result.size() != 9) {
            throw new IllegalStateException("样本清单应包含9篇新闻");
        }
        return result;
    }
 
    public static double[][] vectors() {
        return TNewsSmallVectorizer.tfIdf(TNewsCorpusLoader.titles(load()));
    }
 
    public static String[] goldLabels() {
        List<TNewsCorpusLoader.NewsRecord> records = load();
        String[] result = new String[records.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = records.get(i).getLabel();
        }
        return result;
    }
 
    public static void printClusters(int[] labels) {
        List<TNewsCorpusLoader.NewsRecord> records = load();
        for (int cluster : new TreeSet<Integer>(asList(labels))) {
            System.out.println("簇 " + (cluster + 1) + ":");
            for (int i = 0; i < labels.length; i++) {
                if (labels[i] == cluster) {
                    System.out.println("  N" + (i + 1) + " " + records.get(i).getTitle());
                }
            }
        }
    }
 
    private static List<Integer> asList(int[] values) {
        List<Integer> result = new ArrayList<>();
        for (int value : values) {
            result.add(value);
        }
        return result;
    }
}

AverageLinkage.java

package cn.edu.bjut.textmining.chapter5;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
import cn.edu.bjut.textmining.util.TextVectorizer;
 
/** 自底向上平均连接；每步比较所有现存簇对。 */
public final class AverageLinkage {
    private AverageLinkage() {}
 
    public static double distance(List<Integer> a, List<Integer> b, double[][] vectors) {
        double total = 0;
        for (int i : a) {
            for (int j : b) {
                total += TextVectorizer.cosineDistance(vectors[i], vectors[j]);
            }
        }
        return total / ((double) a.size() * b.size());
    }
 
    public static int[] fit(double[][] vectors, int k, boolean printSteps) {
        KMeansEngine.validate(vectors);
        if (k < 1 || k > vectors.length) {
            throw new IllegalArgumentException("目标簇数无效");
        }
        List<List<Integer>> clusters = new ArrayList<>();
        for (int i = 0; i < vectors.length; i++) {
            clusters.add(new ArrayList<>(Collections.singletonList(i)));
        }
        int step = 0;
        while (clusters.size() > k) {
            double minimum = Double.POSITIVE_INFINITY;
            int a = -1, b = -1;
            for (int i = 0; i < clusters.size(); i++) {
                for (int j = i + 1; j < clusters.size(); j++) {
                    double d = distance(clusters.get(i), clusters.get(j), vectors);
                    if (d < minimum) {
                        minimum = d;
                        a = i;
                        b = j;
                    }
                }
            }
            if (printSteps) {
                System.out.printf(
                        "第%d步：%s + %s，平均距离=%.9f%n",
                        ++step, names(clusters.get(a)), names(clusters.get(b)), minimum);
            }
            clusters.get(a).addAll(clusters.get(b));
            clusters.remove(b);
        }
        int[] labels = new int[vectors.length];
        for (int c = 0; c < clusters.size(); c++) {
            for (int i : clusters.get(c)) {
                labels[i] = c;
            }
        }
        return labels;
    }
 
    private static String names(List<Integer> values) {
        List<String> names = new ArrayList<>();
        for (int value : values) {
            names.add("N" + (value + 1));
        }
        return names.toString();
    }
}

HierarchicalClusteringDemo.java

package cn.edu.bjut.textmining.chapter5;
 
import cn.edu.bjut.textmining.chapter5.support.AverageLinkage;
import cn.edu.bjut.textmining.chapter5.support.SampleNews;
 
/** 九篇新闻的平均连接层次聚类。 */
public class HierarchicalClusteringDemo {
    public static void main(String[] args) {
        try {
            double[][] vectors = SampleNews.vectors();
            int[] labels = AverageLinkage.fit(vectors, 3, true);
            SampleNews.printClusters(labels);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

KMeansEngine.java

package cn.edu.bjut.textmining.chapter5;
 
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
 
import cn.edu.bjut.textmining.util.TextVectorizer;
 
/** 球面K-Means：单位向量按余弦分配，簇向量之和重新单位化。 */
public final class KMeansEngine {
    private KMeansEngine() {}
 
    public static final class Result {
        private final int[] labels;
        private final int iterations;
        private final double[][] centers;
        private final boolean converged;
 
        public Result(int[] labels, int iterations, double[][] centers, boolean converged) {
            this.labels = labels;
            this.iterations = iterations;
            this.centers = centers;
            this.converged = converged;
        }
 
        public int[] labels() {
            return labels.clone();
        }
 
        public int iterations() {
            return iterations;
        }
 
        public double[][] centers() {
            return centers;
        }
 
        public boolean converged() {
            return converged;
        }
    }
 
    public static Result fit(double[][] data, int k, int maxIterations, int... initial) {
        validate(data);
        if (k < 1 || k > data.length || initial.length != k || maxIterations < 1) {
            throw new IllegalArgumentException("请检查簇数、初始中心数和迭代上限");
        }
        int[] labels = new int[data.length];
        Arrays.fill(labels, -1);
        double[][] points = new double[data.length][];
        for (int i = 0; i < data.length; i++) {
            points[i] = data[i].clone();
            TextVectorizer.normalize(points[i]);
        }
        double[][] centers = new double[k][];
        Set<Integer> seen = new HashSet<>();
        for (int c = 0; c < k; c++) {
            if (initial[c] < 0 || initial[c] >= data.length || !seen.add(initial[c])) {
                throw new IllegalArgumentException("初始中心索引必须有效且互不相同");
            }
            centers[c] = points[initial[c]].clone();
        }
        int completed = 0;
        boolean converged = false;
        for (int iteration = 0; iteration < maxIterations; iteration++) {
            completed++;
            boolean changed = false;
            for (int i = 0; i < points.length; i++) {
                int best = 0;
                double score = -Double.MAX_VALUE;
                for (int c = 0; c < k; c++) {
                    double candidate = TextVectorizer.cosine(points[i], centers[c]);
                    if (candidate > score) {
                        score = candidate;
                        best = c;
                    }
                }
                if (labels[i] != best) {
                    labels[i] = best;
                    changed = true;
                }
            }
            // 空簇保留上一轮中心；不把零向量当作有效中心。
            for (int c = 0; c < k; c++) {
                double[] sum = TextVectorizer.centroid(points, labels, c);
                if (squaredNorm(sum) > 0.0) {
                    centers[c] = sum;
                }
            }
            if (!changed) {
                converged = true;
                break;
            }
        }
        return new Result(labels, completed, centers, converged);
    }
 
    public static void validate(double[][] points) {
        if (points == null || points.length == 0 || points[0].length == 0) {
            throw new IllegalArgumentException("输入矩阵不能为空");
        }
        int d = points[0].length;
        for (double[] row : points) {
            if (row.length != d) {
                throw new IllegalArgumentException("向量维度必须相同");
            }
            for (double value : row) {
                if (!Double.isFinite(value)) {
                    throw new IllegalArgumentException("向量必须是有限数值");
                }
            }
            if (squaredNorm(row) == 0.0) {
                throw new IllegalArgumentException("零向量没有余弦方向，请先移除");
            }
        }
    }
 
    public static double squaredNorm(double[] row) {
        double value = 0;
        for (double x : row) {
            value += x * x;
        }
        return value;
    }
 
    public static int[] farthestFirst(double[][] points, int k) {
        validate(points);
        if (k < 1 || k > points.length) {
            throw new IllegalArgumentException("簇数无效");
        }
        int[] selected = new int[k];
        boolean[] used = new boolean[points.length];
        used[0] = true;
        for (int c = 1; c < k; c++) {
            double best = -1;
            int index = -1;
            for (int i = 0; i < points.length; i++) {
                if (used[i]) {
                    continue;
                }
                double nearest = Double.POSITIVE_INFINITY;
                for (int j = 0; j < c; j++) {
                    nearest =
                            Math.min(
                                    nearest,
                                    TextVectorizer.cosineDistance(points[i], points[selected[j]]));
                }
                if (nearest > best) {
                    best = nearest;
                    index = i;
                }
            }
            selected[c] = index;
            used[index] = true;
        }
        return selected;
    }
 
    public static double objective(double[][] points, Result result) {
        double sum = 0;
        for (int i = 0; i < points.length; i++) {
            sum += TextVectorizer.cosineDistance(points[i], result.centers[result.labels[i]]);
        }
        return sum;
    }
}

TextKMeansDemo.java

package cn.edu.bjut.textmining.chapter5;
 
import cn.edu.bjut.textmining.chapter5.support.DocumentRegistry;
import cn.edu.bjut.textmining.chapter5.support.ResultWriter;
import cn.edu.bjut.textmining.chapter5.support.SampleNews;
import cn.edu.bjut.textmining.chapter5.support.TNewsCorpusLoader;
import cn.edu.bjut.textmining.chapter5.support.TextFeatures;
 
/** 对单位化TF-IDF进行球面K-Means。 */
public class TextKMeansDemo {
    public static void main(String[] args) {
        try {
            java.util.List<TNewsCorpusLoader.NewsRecord> records = SampleNews.load();
            TextFeatures.Result features = TextFeatures.fit(TNewsCorpusLoader.titles(records), false);
            double[][] vectors = features.vectors;
            KMeansEngine.Result result = KMeansEngine.fit(vectors, 3, 30, 0, 3, 6);
            System.out.printf(
                    "迭代轮数=%d，收敛=%s，目标值=%.9f%n",
                    result.iterations(),
                    result.converged(),
                    KMeansEngine.objective(vectors, result));
            SampleNews.printClusters(result.labels());
            ResultWriter.features("news_sample", features);
            DocumentRegistry.write("news_sample", records, features, result.labels(),
                    DocumentRegistry.SMALL_CONFIG);
            System.out.println("记录与向量行清单：outputs/chapter5/news_sample_document_registry.tsv");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}