差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- zh:courses:textmining2026:ch05 [2026/10/12 14:35]
pzczxs [课件]
+++ zh:courses:textmining2026:ch05 [2026/10/20 07:27] (当前版本)
pzczxs [AP聚类方法]
@@ 行 1: / 行 1: @@
 ====== 第五章：文本聚类 ======
 ===== 课件 =====
-下载：文本聚类
+下载：{{ :zh:courses:textmining2026:ch05.pptx |文本聚类}}
 ===== 数据集 =====
-下载：
+下载：{{ :zh:courses:textmining2026:chapter5.zip |}}
+===== 工具类 =====
+<file java 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;
+    }
+}
+</file>
+===== 支持类 =====
+<file java SampleNews.java>
+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;
+    }
+}
+</file>
+<file java DocumentRegistry.java>
+package cn.edu.bjut.textmining.chapter5.support;
+import java.io.InputStream;
+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.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Locale;
+import cn.edu.bjut.textmining.chapter5.KMeansEngine;
+/** 将原始记录、特征矩阵行与聚类结果连接起来，不改变特征或聚类计算。 */
+public final class DocumentRegistry {
+    public static final String SMALL_CONFIG = "ch5-char12-rawtf-smoothidf-l2-v1";
+    public static final String LARGE_CONFIG = "ch5-char23-filter-df2-60pct-top5000-rawtf-smoothidf-l2-v1";
+    private DocumentRegistry() {}
+    /** clusterByInput 使用算法内部的零基簇号；-1 表示零向量未进入聚类。 */
+    public static void write(String prefix, List<TNewsCorpusLoader.NewsRecord> records,
+            TextFeatures.Result features, int[] clusterByInput, String config) {
+        if (records.size() != features.vectors.length || records.size() != clusterByInput.length) {
+            throw new IllegalArgumentException("原始记录、向量行和聚类状态必须一一对应");
+        }
+        Path source = ProjectPaths.data("tnews_public/train.json");
+        List<TNewsCorpusLoader.NewsRecord> original = TNewsCorpusLoader.readAll(source);
+        String sourceHash = sha256(source);
+        List<String> rows = new ArrayList<String>();
+        rows.add("local_id\tsource_id\tsource_physical_line\tsource_file\tsource_file_sha256"
+                + "\ttext_sha256\ttext\tpreprocess_version\tvector_row_0based\tfeature_dimension"
+                + "\tstatus\tcluster_id\treference_label");
+        for (int i = 0; i < records.size(); i++) {
+            TNewsCorpusLoader.NewsRecord record = records.get(i);
+            int line = record.getSourceLine();
+            if (line < 1 || line > original.size()
+                    || !record.getTitle().equals(original.get(line - 1).getTitle())
+                    || !record.getLabel().equals(original.get(line - 1).getLabel())) {
+                throw new IllegalStateException("清单与原始文件不符：source_line=" + line);
+            }
+            boolean zero = KMeansEngine.squaredNorm(features.vectors[i]) == 0.0;
+            if ((clusterByInput[i] < 0) != zero) {
+                throw new IllegalArgumentException("只有零向量可以没有聚类结果，向量行=" + i);
+            }
+            String sourceId = String.format(Locale.ROOT, "tnews-train-%06d", line);
+            String localId = ("news_sample".equals(prefix) ? "N" : "selection-") + (i + 1);
+            rows.add(localId + "\t" + sourceId + "\t" + line
+                    + "\tdata/chapter5/tnews_public/train.json\t" + sourceHash
+                    + "\t" + sha256(record.getTitle().getBytes(StandardCharsets.UTF_8))
+                    + "\t" + tsv(record.getTitle()) + "\t" + config + "\t" + i
+                    + "\t" + features.vocabulary.size() + "\t" + (zero ? "zero_vector" : "clustered")
+                    + "\t" + (zero ? "" : Integer.toString(clusterByInput[i] + 1))
+                    + "\t" + record.getLabel());
+        }
+        ResultWriter.lines(prefix + "_document_registry.tsv", rows);
+    }
+    private static String tsv(String value) {
+        // JSON 风格反斜杠转义，避免原文制表符/换行破坏列结构。
+        return value.replace("\\", "\\\\").replace("\t", "\\t")
+                .replace("\r", "\\r").replace("\n", "\\n");
+    }
+    private static MessageDigest digest() {
+        try {
+            return MessageDigest.getInstance("SHA-256");
+        } catch (NoSuchAlgorithmException e) {
+            throw new IllegalStateException("JDK 缺少 SHA-256", e);
+        }
+    }
+    public static String sha256(Path path) {
+        MessageDigest digest = digest();
+        try (InputStream in = Files.newInputStream(path)) {
+            byte[] buffer = new byte[8192];
+            int count;
+            while ((count = in.read(buffer)) != -1) {
+                digest.update(buffer, 0, count);
+            }
+            return hex(digest.digest());
+        } catch (IOException e) {
+            throw new UncheckedIOException("无法校验来源文件：" + path, e);
+        }
+    }
+    private static String sha256(byte[] bytes) { return hex(digest().digest(bytes)); }
+    private static String hex(byte[] bytes) {
+        StringBuilder result = new StringBuilder();
+        for (byte b : bytes) result.append(String.format(Locale.ROOT, "%02x", b & 0xff));
+        return result.toString();
+    }
+}
+</file>
+<file java ResultWriter.java>
+package cn.edu.bjut.textmining.chapter5.support;
+import java.io.BufferedWriter;
+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;
+/** 结果表使用UTF-8，运行入口只需指定文件名和行。 */
+public final class ResultWriter {
+    private ResultWriter() {}
+    public static void lines(String name, List<String> lines) {
+        try (BufferedWriter writer =
+                Files.newBufferedWriter(ProjectPaths.output(name), StandardCharsets.UTF_8)) {
+            for (String line : lines) {
+                writer.write(line);
+                writer.newLine();
+            }
+        } catch (IOException e) {
+            throw new UncheckedIOException("保存结果失败：" + name, e);
+        }
+    }
+    public static void features(String prefix, TextFeatures.Result result) {
+        List<String> vocab = new ArrayList<>();
+        vocab.add("column\tfeature\tdf");
+        for (int j = 0; j < result.vocabulary.size(); j++) {
+            vocab.add(j + "\t" + result.vocabulary.get(j) + "\t" + result.documentFrequencies[j]);
+        }
+        lines(prefix + "_vocabulary.tsv", vocab);
+        List<String> rows = new ArrayList<>();
+        for (double[] vector : result.vectors) {
+            StringBuilder line = new StringBuilder();
+            for (int j = 0; j < vector.length; j++) {
+                if (j > 0) {
+                    line.append(',');
+                }
+                line.append(Double.toString(vector[j]));
+            }
+            rows.add(line.toString());
+        }
+        lines(prefix + "_vectors.csv", rows);
+    }
+}
+</file>
+<file java TNewsCorpusLoader.java>
+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.nio.file.Path;
+import java.text.Normalizer;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Locale;
+import java.util.Map;
+import java.util.Set;
+import java.util.regex.Matcher;
+import java.util.regex.Pattern;
+/** 读取官方 JSONL；类别仅用于选择样本和事后评价。 */
+public final class TNewsCorpusLoader {
+    private static final Pattern FIELD =
+            Pattern.compile("\\\"(label_desc|sentence)\\\"\\s*:\\s*\\\"((?:\\\\.|[^\\\"])*)\\\"");
+    private TNewsCorpusLoader() {}
+    public static final class NewsRecord {
+        private final String label;
+        private final String title;
+        private final int sourceLine;
+        public NewsRecord(String label, String title) {
+            this(label, title, 0);
+        }
+        public NewsRecord(String label, String title, int sourceLine) {
+            this.label = label;
+            this.title = title;
+            this.sourceLine = sourceLine;
+        }
+        public String getLabel() {
+            return label;
+        }
+        public String getTitle() {
+            return title;
+        }
+        public int getSourceLine() {
+            return sourceLine;
+        }
+    }
+    public static List<NewsRecord> readAll(Path file) {
+        List<NewsRecord> records = new ArrayList<>();
+        try (BufferedReader reader = Files.newBufferedReader(file, StandardCharsets.UTF_8)) {
+            String line;
+            int number = 0;
+            while ((line = reader.readLine()) != null) {
+                number++;
+                Matcher matcher = FIELD.matcher(line);
+                Map<String, String> values = new HashMap<>();
+                while (matcher.find()) {
+                    values.put(matcher.group(1), unescape(matcher.group(2)));
+                }
+                if (!values.containsKey("sentence") || !values.containsKey("label_desc")) {
+                    throw new IllegalArgumentException("JSONL缺少字段，行号：" + number);
+                }
+                records.add(
+                        new NewsRecord(values.get("label_desc"), values.get("sentence"), number));
+            }
+        } catch (IOException e) {
+            throw new UncheckedIOException("读取新闻失败：" + file, e);
+        }
+        return records;
+    }
+    public static String normalizedKey(String title) {
+        return Normalizer.normalize(title, Normalizer.Form.NFKC)
+                .replaceAll("[\\s\\p{Z}]+", "")
+                .toLowerCase(Locale.ROOT);
+    }
+    public static List<NewsRecord> readBalanced(Path file, List<String> categories, int limit) {
+        if (limit < 1) {
+            throw new IllegalArgumentException("每类样本数必须为正数");
+        }
+        Map<String, NewsRecord> unique = new LinkedHashMap<>();
+        Set<String> conflicts = new HashSet<>();
+        for (NewsRecord record : readAll(file)) {
+            String key = normalizedKey(record.title);
+            NewsRecord old = unique.get(key);
+            if (old != null && !old.label.equals(record.label)) {
+                conflicts.add(key);
+            }
+            if (old == null && !key.isEmpty()) {
+                unique.put(key, record);
+            }
+        }
+        Map<String, Integer> counts = new LinkedHashMap<>();
+        for (String category : categories) {
+            counts.put(category, 0);
+        }
+        List<NewsRecord> result = new ArrayList<>();
+        for (Map.Entry<String, NewsRecord> item : unique.entrySet()) {
+            NewsRecord record = item.getValue();
+            Integer count = counts.get(record.label);
+            if (!conflicts.contains(item.getKey()) && count != null && count < limit) {
+                result.add(record);
+                counts.put(record.label, count + 1);
+            }
+        }
+        for (String category : categories) {
+            if (counts.get(category) != limit) {
+                throw new IllegalStateException("样本不足：" + category);
+            }
+        }
+        return result;
+    }
+    public static List<NewsRecord> readCuratedSample(Path file, int perCategory) {
+        if (perCategory < 1 || perCategory > 3) {
+            throw new IllegalArgumentException("每类选择1至3条");
+        }
+        int[] lines = {208, 1241, 1431, 625, 676, 824, 274, 308, 566};
+        List<NewsRecord> all = readAll(file);
+        List<NewsRecord> result = new ArrayList<>();
+        for (int group = 0; group < 3; group++) {
+            for (int j = 0; j < perCategory; j++) {
+                result.add(all.get(lines[group * 3 + j] - 1));
+            }
+        }
+        return result;
+    }
+    public static List<String> titles(List<NewsRecord> records) {
+        List<String> titles = new ArrayList<>();
+        for (NewsRecord record : records) {
+            titles.add(record.title);
+        }
+        return titles;
+    }
+    private static String unescape(String text) {
+        StringBuilder result = new StringBuilder();
+        for (int i = 0; i < text.length(); i++) {
+            char c = text.charAt(i);
+            if (c != '\\') {
+                result.append(c);
+                continue;
+            }
+            if (++i >= text.length()) {
+                throw new IllegalArgumentException("JSON转义不完整");
+            }
+            c = text.charAt(i);
+            switch (c) {
+                case 'u':
+                    result.append((char) Integer.parseInt(text.substring(i + 1, i + 5), 16));
+                    i += 4;
+                    break;
+                case 'n':
+                    result.append('\n');
+                    break;
+                case 'r':
+                    result.append('\r');
+                    break;
+                case 't':
+                    result.append('\t');
+                    break;
+                case 'b':
+                    result.append('\b');
+                    break;
+                case 'f':
+                    result.append('\f');
+                    break;
+                case '"':
+                case '\\':
+                case '/':
+                    result.append(c);
+                    break;
+                default:
+                    throw new IllegalArgumentException("未知JSON转义：" + c);
+            }
+        }
+        return result.toString();
+    }
+}
+</file>
+<file java TextFeatures.java>
+package cn.edu.bjut.textmining.chapter5.support;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Locale;
+import java.util.Map;
+import java.util.Set;
+import cn.edu.bjut.textmining.util.TextVectorizer;
+/** 字符N-gram TF-IDF；所有文档共用一个词表和同一组DF。 */
+public final class TextFeatures {
+    private TextFeatures() {}
+    private static final Set<String> STOP_GRAMS =
+            new HashSet<>(
+                    Arrays.asList(
+                            "什么", "怎么", "如何", "为什么", "一个", "一种", "可以", "哪些", "有没有", "是不是", "这个",
+                            "这样", "中国", "现在", "我们", "他们", "你们", "自己", "的人", "的是", "知道", "多少", "进行",
+                            "问题", "时候", "为何", "来看", "认为"));
+    public static final class Result {
+        public final double[][] vectors;
+        public final List<String> vocabulary;
+        public final int[] documentFrequencies;
+        Result(double[][] vectors, List<String> vocabulary, int[] df) {
+            this.vectors = vectors;
+            this.vocabulary = vocabulary;
+            this.documentFrequencies = df;
+        }
+    }
+    public static List<String> ngrams(String text, int minN, int maxN, boolean filter) {
+        // 标点、符号和空白划定片段边界，不把两侧字符拼成原文中不存在的组合。
+        String clean =
+                java.text.Normalizer.normalize(text, java.text.Normalizer.Form.NFKC)
+                        .toLowerCase(Locale.ROOT);
+        List<String> result = new ArrayList<>();
+        for (String segment : clean.split("[\\p{P}\\p{S}\\s]+")) {
+            int[] codePoints = segment.codePoints().toArray();
+            for (int n = minN; n <= maxN; n++) {
+                for (int i = 0; i + n <= codePoints.length; i++) {
+                    String gram = new String(codePoints, i, n);
+                    if (!filter || (!STOP_GRAMS.contains(gram) && !gram.matches("[0-9]+"))) {
+                        result.add(gram);
+                    }
+                }
+            }
+        }
+        return result;
+    }
+    public static Result fit(List<String> documents, boolean largeCorpus) {
+        if (documents.isEmpty()) {
+            throw new IllegalArgumentException("语料不能为空");
+        }
+        Map<String, Integer> frequency = new HashMap<>();
+        List<List<String>> tokenized = new ArrayList<>();
+        for (String document : documents) {
+            List<String> grams = ngrams(document, largeCorpus ? 2 : 1, largeCorpus ? 3 : 2, largeCorpus);
+            tokenized.add(grams);
+            for (String gram : new HashSet<>(grams)) {
+                frequency.put(gram, frequency.getOrDefault(gram, 0) + 1);
+            }
+        }
+        List<String> vocabulary = new ArrayList<>(frequency.keySet());
+        if (largeCorpus) {
+            vocabulary.removeIf(
+                    gram ->
+                            frequency.get(gram) < 2
+                                    || frequency.get(gram) > documents.size() * 0.60);
+            vocabulary.sort(
+                    (a, b) -> {
+                        int order = frequency.get(b).compareTo(frequency.get(a));
+                        return order != 0 ? order : a.compareTo(b);
+                    });
+            if (vocabulary.size() > 5000) {
+                vocabulary = new ArrayList<>(vocabulary.subList(0, 5000));
+            }
+        } else {
+            Collections.sort(vocabulary);
+        }
+        Map<String, Integer> index = new HashMap<>();
+        int[] df = new int[vocabulary.size()];
+        for (int j = 0; j < vocabulary.size(); j++) {
+            index.put(vocabulary.get(j), j);
+            df[j] = frequency.get(vocabulary.get(j));
+        }
+        double[][] vectors = new double[documents.size()][vocabulary.size()];
+        for (int i = 0; i < documents.size(); i++) {
+            for (String gram : tokenized.get(i)) {
+                Integer j = index.get(gram);
+                if (j != null) {
+                    vectors[i][j]++;
+                }
+            }
+            for (int j = 0; j < vocabulary.size(); j++) {
+                double idf = Math.log((documents.size() + 1.0) / (df[j] + 1.0)) + 1.0;
+                vectors[i][j] *= idf;
+            }
+            TextVectorizer.normalize(vectors[i]);
+        }
+        return new Result(vectors, vocabulary, df);
+    }
+}
+</file>
+===== 层次聚类方法 =====
+<file java 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();
+    }
+}
+</file>
+<file java 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();
+        }
+    }
+}
+</file>
+===== KMeans聚类方法 =====
+<file java 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;
+    }
+}
+</file>
+<file java 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();
+        }
+    }
+}
+</file>
+===== AP聚类方法 =====
+<file java AffinityPropagation.java>
+package cn.edu.bjut.textmining.chapter5;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+/** s(i,k)=-||x_i-x_k||²；责任度和可用度采用同步更新与阻尼。 */
+public final class AffinityPropagation {
+    private AffinityPropagation() {}
+    public static final class Result {
+        public final int[] labels;
+        public final int[] exemplars;
+        public final int iterations;
+        public final boolean converged;
+        public final double preference;
+        Result(
+                int[] labels,
+                int[] exemplars,
+                int iterations,
+                boolean converged,
+                double preference) {
+            this.labels = labels;
+            this.exemplars = exemplars;
+            this.iterations = iterations;
+            this.converged = converged;
+            this.preference = preference;
+        }
+    }
+    public static double[][] similarities(double[][] vectors) {
+        KMeansEngine.validate(vectors);
+        double[][] s = new double[vectors.length][vectors.length];
+        for (int i = 0; i < s.length; i++) {
+            for (int k = 0; k < s.length; k++) {
+                for (int j = 0; j < vectors[i].length; j++) {
+                    double delta = vectors[i][j] - vectors[k][j];
+                    s[i][k] -= delta * delta;
+                }
+            }
+        }
+        return s;
+    }
+    public static double medianPreference(double[][] s) {
+        if (s.length < 2) {
+            throw new IllegalArgumentException("AP至少需要两个样本");
+        }
+        double[] values = new double[s.length * (s.length - 1)];
+        int p = 0;
+        for (int i = 0; i < s.length; i++) {
+            for (int k = 0; k < s.length; k++) {
+                if (i != k) {
+                    values[p++] = s[i][k];
+                }
+            }
+        }
+        Arrays.sort(values);
+        return (values[(p - 1) / 2] + values[p / 2]) / 2;
+    }
+    public static Result fit(
+            double[][] vectors, double damping, int maxIterations, int stableRounds) {
+        double[][] s = similarities(vectors);
+        int n = s.length;
+        double preference = medianPreference(s);
+        if (damping < 0.5 || damping >= 1 || maxIterations < 1 || stableRounds < 1) {
+            throw new IllegalArgumentException("请检查阻尼、迭代上限和稳定轮数");
+        }
+        for (int i = 0; i < n; i++) {
+            s[i][i] = preference;
+        }
+        double[][] r = new double[n][n], a = new double[n][n];
+        boolean[] previous = new boolean[n];
+        int stable = 0, completed = 0;
+        boolean converged = false;
+        for (int iteration = 0; iteration < maxIterations; iteration++) {
+            completed++;
+            updateResponsibilities(s, r, a, damping);
+            updateAvailabilities(r, a, damping);
+            boolean[] current = new boolean[n];
+            int count = 0;
+            for (int k = 0; k < n; k++) {
+                current[k] = r[k][k] + a[k][k] > 0;
+                if (current[k]) {
+                    count++;
+                }
+            }
+            stable = Arrays.equals(previous, current) ? stable + 1 : 0;
+            previous = current;
+            if (count > 0 && stable >= stableRounds) {
+                converged = true;
+                break;
+            }
+        }
+        List<Integer> chosen = new ArrayList<>();
+        for (int k = 0; k < n; k++) {
+            if (r[k][k] + a[k][k] > 0) {
+                chosen.add(k);
+            }
+        }
+        if (chosen.isEmpty()) {
+            throw new IllegalStateException("AP尚未产生代表点，请调整偏好、阻尼或迭代上限");
+        }
+        int[] labels = new int[n], exemplars = new int[chosen.size()];
+        for (int c = 0; c < exemplars.length; c++) {
+            exemplars[c] = chosen.get(c);
+        }
+        // 以原始相似度分配给代表点；代表点归入自身簇。
+        for (int i = 0; i < n; i++) {
+            double best = -Double.MAX_VALUE;
+            for (int c = 0; c < exemplars.length; c++) {
+                if (s[i][exemplars[c]] > best) {
+                    best = s[i][exemplars[c]];
+                    labels[i] = c;
+                }
+            }
+        }
+        for (int c = 0; c < exemplars.length; c++) {
+            labels[exemplars[c]] = c;
+        }
+        return new Result(labels, exemplars, completed, converged, preference);
+    }
+    public static void updateResponsibilities(
+            double[][] s, double[][] r, double[][] a, double damping) {
+        for (int i = 0; i < s.length; i++) {
+            for (int k = 0; k < s.length; k++) {
+                double maxOther = -Double.MAX_VALUE;
+                for (int j = 0; j < s.length; j++) {
+                    if (j != k) {
+                        maxOther = Math.max(maxOther, a[i][j] + s[i][j]);
+                    }
+                }
+                double next = s[i][k] - maxOther;
+                r[i][k] = damping * r[i][k] + (1 - damping) * next;
+            }
+        }
+    }
+    public static void updateAvailabilities(double[][] r, double[][] a, double damping) {
+        for (int k = 0; k < r.length; k++) {
+            double positiveSum = 0;
+            for (int i = 0; i < r.length; i++) {
+                if (i != k) {
+                    positiveSum += Math.max(0, r[i][k]);
+                }
+            }
+            for (int i = 0; i < r.length; i++) {
+                double next =
+                        i == k
+                                ? positiveSum
+                                : Math.min(0, r[k][k] + positiveSum - Math.max(0, r[i][k]));
+                a[i][k] = damping * a[i][k] + (1 - damping) * next;
+            }
+        }
+    }
+}
+</file>
+<file java AffinityPropagationDemo.java>
+package cn.edu.bjut.textmining.chapter5;
+import cn.edu.bjut.textmining.chapter5.support.SampleNews;
+/** 在同一TF-IDF空间中传播消息并选取新闻代表。 */
+public class AffinityPropagationDemo {
+    public static void main(String[] args) {
+        try {
+            double[][] vectors = SampleNews.vectors();
+            AffinityPropagation.Result result = AffinityPropagation.fit(vectors, 0.7, 300, 20);
+            System.out.printf(
+                    "偏好值=%.9f，迭代轮数=%d，收敛=%s%n",
+                    result.preference, result.iterations, result.converged);
+            System.out.print("代表点：");
+            for (int i : result.exemplars) {
+                System.out.print("N" + (i + 1) + " ");
+            }
+            System.out.println();
+            SampleNews.printClusters(result.labels);
+        } catch (Exception e) {
+            e.printStackTrace();
+        }
+    }
+}
+</file>
+===== 上机作业 =====
+  * 完成每类（内部度量法、外部度量法和基于聚类稳定性的方法）聚类性能评价中的至少一种。
+~~DISCUSSION~~

硕风徐徐

用户工具

站点工具

差别

页面工具