差别

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

--- zh:courses:textmining2026:ch05 [2026/10/12 15:11]
pzczxs [支持类]
+++ zh:courses:textmining2026:ch05 [2026/10/20 07:27] (当前版本)
pzczxs [AP聚类方法]
@@ 行 1: / 行 1: @@
 ====== 第五章：文本聚类 ======
 ===== 课件 =====
-下载：文本聚类
+下载：{{ :zh:courses:textmining2026:ch05.pptx |文本聚类}}
 ===== 数据集 =====
-下载：
+下载：{{ :zh:courses:textmining2026:chapter5.zip |}}
 ===== 工具类 =====
@@ 行 565: / 行 565: @@
         }
         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);
     }
 }
@@ 行 865: / 行 978: @@
 }
 </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~~

硕风徐徐

用户工具

站点工具

差别

页面工具