下载：文本聚类

下载：

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;
    }
}

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();
        }
    }
}