022、基于Java的k-近邻算法(kNN)
基于Java的k-近邻算法(kNN)
1. 引言
k-近邻算法(k-Nearest Neighbor, kNN)是一种基础且强大的机器学习算法，它可以用于分类和回归。本文将详细介绍kNN算法的原理，并使用Java语言实现这一算法。
2. 算法原理
kNN的核心思想是：对于一个待分类的数据点，我们找出训练集中离它最近的k个邻居，然后让这k个邻居进行投票，票数最多的类别就作为待分类点的类别。
2.1 算法步骤
- 计算待分类点与训练集中所有点的距离
- 按距离递增排序
- 选取距离最小的k个点
- 统计这k个点中各个类别的数量
- 选择数量最多的类别作为预测结果
3. Java实现
首先通过一个完整的Java实现来深入理解kNN算法。
3.1 数据点类定义
public class Point {
private double[] features;
private String label;
public Point(double[] features, String label) {
this.features = features;
this.label = label;
}
public double[] getFeatures() {
return features;
}
public String getLabel() {
return label;
}
}
3.2 KNN算法核心实现
public class KNNClassifier {
private List<Point> trainingSet;
private int k;
public KNNClassifier(int k) {
this.k = k;
this.trainingSet = new ArrayList<>();
}
public void train(List<Point> trainingData) {
this.trainingSet.addAll(trainingData);
}
public String predict(double[] features) {
// 计算距离并存储
List<DistanceLabel> distances = new ArrayList<>();
for (Point point : trainingSet) {
double distance = calculateEuclideanDistance(features, point.getFeatures());
distances.add(new DistanceLabel(distance, point.getLabel()));
}
// 排序
Collections.sort(distances);
// 取前k个点，统计类别
Map<String, Integer> labelCount = new HashMap<>();
for (int i = 0; i < k; i++) {
String label = distances.get(i).label;
labelCount.put(label, labelCount.getOrDefault(label, 0) + 1);
}
// 返回出现次数最多的类别
return Collections.max(labelCount.entrySet(),
Map.Entry.comparingByValue()).getKey();
}
private double calculateEuclideanDistance(double[] a, double[] b) {
double sum = 0.0;
for (int i = 0; i < a.length; i++) {
sum += Math.pow(a[i] - b[i], 2);
}
return Math.sqrt(sum);
}
private class DistanceLabel implements Comparable<DistanceLabel> {
double distance;
String label;
public DistanceLabel(double distance, String label) {
this.distance = distance;
this.label = label;
}
@Override
public int compareTo(DistanceLabel other) {
return Double.compare(this.distance, other.distance);
}
}
}
4. 实际应用示例
4.1 鸢尾花分类示例
public class IrisExample {
public static void main(String[] args) {
// 创建训练数据
List<Point> trainingData = new ArrayList<>();
trainingData.add(new Point(new double[]{5.1, 3.5, 1.4, 0.2}, "Setosa"));
trainingData.add(new Point(new double[]{4.9, 3.0, 1.4, 0.2}, "Setosa"));
trainingData.add(new Point(new double[]{7.0, 3.2, 4.7, 1.4}, "Versicolor"));
trainingData.add(new Point(new double[]{6.4, 3.2, 4.5, 1.5}, "Versicolor"));
// 创建并训练分类器
KNNClassifier classifier = new KNNClassifier(3);
classifier.train(trainingData);
// 预测新样本
double[] newFlower = {6.7, 3.1, 4.4, 1.4};
String prediction = classifier.predict(newFlower);
System.out.println("预测品种：" + prediction);
}
}
4.2 房价预测示例
public class HousePricePredictor {
private static class House extends Point {
public House(double[] features, String priceRange) {
super(features, priceRange);
}
}
public static void main(String[] args) {
List<Point> houses = new ArrayList<>();
// 特征：[面积(平方米), 房间数, 楼层, 建筑年份]
houses.add(new House(new double[]{120, 3, 15, 2010}, "高价"));
houses.add(new House(new double[]{80, 2, 8, 2005}, "中价"));
houses.add(new House(new double[]{60, 1, 3, 2000}, "低价"));
houses.add(new House(new double[]{150, 4, 20, 2015}, "高价"));
KNNClassifier predictor = new KNNClassifier(3);
predictor.train(houses);
// 预测新房价格
double[] newHouse = {100, 2, 10, 2012};
String prediction = predictor.predict(newHouse);
System.out.println("预测价格区间：" + prediction);
}
}
4.3 电影推荐系统
public class MovieRecommender {
private static class Movie extends Point {
private String title;
public Movie(String title, double[] features, String genre) {
super(features, genre);
this.title = title;
}
}
public static void main(String[] args) {
List<Point> movies = new ArrayList<>();
// 特征：[动作程度, 剧情深度, 特效水平, 幽默程度, 浪漫程度]
movies.add(new Movie("复仇者联盟",
new double[]{0.9, 0.7, 0.95, 0.6, 0.3}, "动作"));
movies.add(new Movie("泰坦尼克号",
new double[]{0.3, 0.9, 0.7, 0.2, 0.95}, "爱情"));
movies.add(new Movie("盗梦空间",
new double[]{0.7, 0.95, 0.8, 0.3, 0.4}, "科幻"));
KNNClassifier recommender = new KNNClassifier(5);
recommender.train(movies);
// 基于用户观看历史推荐
double[] userPreference = {0.8, 0.6, 0.9, 0.4, 0.3};
String recommendedGenre = recommender.predict(userPreference);
System.out.println("推荐类型：" + recommendedGenre);
}
}
4.4 异常检测系统
public class AnomalyDetector {
private static class NetworkTraffic extends Point {
public NetworkTraffic(double[] features, String status) {
super(features, status);
}
}
public static void main(String[] args) {
List<Point> trafficData = new ArrayList<>();
// 特征：[请求频率, 数据包大小, 连接持续时间, 错误率]
trafficData.add(new NetworkTraffic(
new double[]{0.1, 0.2, 0.15, 0.05}, "正常"));
trafficData.add(new NetworkTraffic(
new double[]{0.9, 0.8, 0.7, 0.85}, "异常"));
trafficData.add(new NetworkTraffic(
new double[]{0.15, 0.25, 0.2, 0.1}, "正常"));
KNNClassifier detector = new KNNClassifier(3);
detector.train(trafficData);
// 检测新的网络流量
double[] newTraffic = {0.8, 0.75, 0.6, 0.8};
String detection = detector.predict(newTraffic);
System.out.println("流量状态：" + detection);
}
}
4.5 医疗诊断系统
public class MedicalDiagnosisSystem {
private static class Patient extends Point {
private String id;
public Patient(String id, double[] features, String diagnosis) {
super(features, diagnosis);
this.id = id;
}
}
public static void main(String[] args) {
List<Point> patientRecords = new ArrayList<>();
// 特征：[年龄, 血压, 血糖, 胆固醇, 心率]
patientRecords.add(new Patient("P001",
new double[]{45, 130, 100, 200, 75}, "健康"));
patientRecords.add(new Patient("P002",
new double[]{65, 160, 140, 260, 85}, "高危"));
patientRecords.add(new Patient("P003",
new double[]{35, 120, 90, 180, 70}, "健康"));
KNNClassifier diagnosticSystem = new KNNClassifier(5);
diagnosticSystem.train(patientRecords);
// 诊断新病人
double[] newPatient = {55, 150, 130, 240, 80};
String diagnosis = diagnosticSystem.predict(newPatient);
System.out.println("诊断结果：" + diagnosis);
}
}
4.6 信用评分系统
public class CreditScoring {
private static class Customer extends Point {
private String customerId;
public Customer(String customerId, double[] features, String creditRating) {
super(features, creditRating);
this.customerId = customerId;
}
}
public static void main(String[] args) {
List<Point> customerData = new ArrayList<>();
// 特征：[年收入, 账户年限, 负债比率, 信用卡使用率, 逾期次数]
customerData.add(new Customer("C001",
new double[]{80000, 5, 0.3, 0.4, 0}, "优秀"));
customerData.add(new Customer("C002",
new double[]{45000, 2, 0.6, 0.8, 3}, "风险"));
customerData.add(new Customer("C003",
new double[]{60000, 3, 0.4, 0.5, 1}, "良好"));
KNNClassifier creditScorer = new KNNClassifier(3);
creditScorer.train(customerData);
// 评估新客户
double[] newCustomer = {65000, 4, 0.35, 0.45, 0};
String creditRating = creditScorer.predict(newCustomer);
System.out.println("信用评级：" + creditRating);
}
}
5. 高级优化技术
5.1 并行处理实现
public class ParallelKNNClassifier extends KNNClassifier {
public String predict(double[] features) {
// 使用并行流计算距离
List<DistanceLabel> distances = trainingSet.parallelStream()
.map(point -> new DistanceLabel(
calculateEuclideanDistance(features, point.getFeatures()),
point.getLabel()))
.sorted()
.collect(Collectors.toList());
// 取前k个点并统计
Map<String, Long> labelCount = distances.stream()
.limit(k)
.map(dl -> dl.label)
.collect(Collectors.groupingBy(
Function.identity(),
Collectors.counting()));
return Collections.max(labelCount.entrySet(),
Map.Entry.comparingByValue()).getKey();
}
}
5.2 特征权重优化
public class WeightedKNNClassifier extends KNNClassifier {
private double[] weights;
public WeightedKNNClassifier(int k, double[] weights) {
super(k);
this.weights = weights;
}
@Override
protected double calculateEuclideanDistance(double[] a, double[] b) {
double sum = 0.0;
for (int i = 0; i < a.length; i++) {
sum += weights[i] * Math.pow(a[i] - b[i], 2);
}
return Math.sqrt(sum);
}
}
5.3 动态K值选择
public class DynamicKNNClassifier extends KNNClassifier {
private int minK;
private int maxK;
public DynamicKNNClassifier(int minK, int maxK) {
super(minK);
this.minK = minK;
this.maxK = maxK;
}
@Override
public String predict(double[] features) {
List<DistanceLabel> distances = new ArrayList<>();
// 计算所有距离
for (Point point : trainingSet) {
double distance = calculateEuclideanDistance(
features, point.getFeatures());
distances.add(new DistanceLabel(distance, point.getLabel()));
}
Collections.sort(distances);
// 尝试不同的k值，选择置信度最高的结果
String bestPrediction = null;
double maxConfidence = 0.0;
for (int k = minK; k <= maxK; k++) {
Map<String, Integer> labelCount = new HashMap<>();
for (int i = 0; i < k; i++) {
String label = distances.get(i).label;
labelCount.put(label,
labelCount.getOrDefault(label, 0) + 1);
}
// 计算置信度
int maxCount = Collections.max(labelCount.values());
double confidence = (double) maxCount / k;
if (confidence > maxConfidence) {
maxConfidence = confidence;
bestPrediction = Collections.max(labelCount.entrySet(),
Map.Entry.comparingByValue()).getKey();
}
}
return bestPrediction;
}
}
6. 高级应用场景
6.1 文本分类系统
public class TextClassifier {
private static class Document extends Point {
private String content;
public Document(String content, double[] features, String category) {
super(features, category);
this.content = content;
}
// TF-IDF特征提取
public static double[] extractFeatures(String text, Map<String, Integer> dictionary) {
Map<String, Integer> wordCount = new HashMap<>();
String[] words = text.toLowerCase().split("\\W+");
// 计算词频
for (String word : words) {
wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}
// 构建特征向量
double[] features = new double[dictionary.size()];
for (Map.Entry<String, Integer> entry : dictionary.entrySet()) {
int index = entry.getValue();
String word = entry.getKey();
features[index] = wordCount.getOrDefault(word, 0);
}
return features;
}
}
public static void main(String[] args) {
// 构建词典
Map<String, Integer> dictionary = new HashMap<>();
dictionary.put("machine", 0);
dictionary.put("learning", 1);
dictionary.put("data", 2);
dictionary.put("algorithm", 3);
List<Point> documents = new ArrayList<>();
// 添加训练文档
documents.add(new Document(
"Machine learning algorithms",
Document.extractFeatures("Machine learning algorithms", dictionary),
"技术"
));
documents.add(new Document(
"Data analysis and algorithms",
Document.extractFeatures("Data analysis and algorithms", dictionary),
"技术"
));
KNNClassifier classifier = new KNNClassifier(3);
classifier.train(documents);
// 分类新文档
double[] newDoc = Document.extractFeatures(
"Learning machine algorithms", dictionary);
String category = classifier.predict(newDoc);
System.out.println("文档类别：" + category);
}
}
6.2 时间序列预测
public class TimeSeriesPredictor {
private static class TimeSeries extends Point {
private LocalDateTime timestamp;
public TimeSeries(LocalDateTime timestamp, double[] features, String trend) {
super(features, trend);
this.timestamp = timestamp;
}
}
public static double[] createTimeWindow(List<Double> values, int windowSize) {
double[] window = new double[windowSize];
int start = values.size() - windowSize;
for (int i = 0; i < windowSize; i++) {
window[i] = values.get(start + i);
}
return window;
}
public static void main(String[] args) {
List<Point> timeSeriesData = new ArrayList<>();
List<Double> stockPrices = Arrays.asList(100.0, 102.0, 101.0, 103.0, 105.0);
// 使用滑动窗口创建训练数据
int windowSize = 3;
for (int i = windowSize; i < stockPrices.size(); i++) {
double[] window = createTimeWindow(
stockPrices.subList(0, i), windowSize);
String trend = stockPrices.get(i) > stockPrices.get(i-1) ? "上涨" : "下跌";
timeSeriesData.add(new TimeSeries(
LocalDateTime.now().minusDays(stockPrices.size() - i),
window,
trend
));
}
KNNClassifier predictor = new KNNClassifier(3);
predictor.train(timeSeriesData);
// 预测下一个时间点的趋势
double[] lastWindow = createTimeWindow(stockPrices, windowSize);
String prediction = predictor.predict(lastWindow);
System.out.println("预测趋势：" + prediction);
}
}
6.3 图像相似度匹配
public class ImageMatcher {
private static class Image extends Point {
private BufferedImage image;
private String path;
public Image(String path, double[] features, String category) {
super(features, category);
this.path = path;
try {
this.image = ImageIO.read(new File(path));
} catch (IOException e) {
e.printStackTrace();
}
}
// 提取图像特征（简化版本）
public static double[] extractFeatures(BufferedImage image) {
int width = image.getWidth();
int height = image.getHeight();
double[] features = new double[3]; // RGB平均值
long totalR = 0, totalG = 0, totalB = 0;
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
int rgb = image.getRGB(x, y);
totalR += (rgb >> 16) & 0xFF;
totalG += (rgb >> 8) & 0xFF;
totalB += rgb & 0xFF;
}
}
int pixels = width * height;
features[0] = totalR / (double) pixels;
features[1] = totalG / (double) pixels;
features[2] = totalB / (double) pixels;
return features;
}
}
public static void main(String[] args) {
List<Point> imageDatabase = new ArrayList<>();
// 添加训练图片
File imageDir = new File("images");
for (File file : imageDir.listFiles()) {
try {
BufferedImage img = ImageIO.read(file);
double[] features = Image.extractFeatures(img);
imageDatabase.add(new Image(
file.getPath(),
features,
file.getParentFile().getName() // 使用文件夹名作为类别
));
} catch (IOException e) {
e.printStackTrace();
}
}
KNNClassifier matcher = new KNNClassifier(5);
matcher.train(imageDatabase);
// 匹配新图片
try {
BufferedImage newImage = ImageIO.read(new File("test.jpg"));
double[] features = Image.extractFeatures(newImage);
String category = matcher.predict(features);
System.out.println("图片类别：" + category);
} catch (IOException e) {
e.printStackTrace();
}
}
}
6.4 推荐系统优化
public class EnhancedRecommender {
private static class UserProfile {
private Map<String, Double> preferences;
private List<String> history;
public UserProfile() {
this.preferences = new HashMap<>();
this.history = new ArrayList<>();
}
public void updatePreference(String item, double rating) {
preferences.put(item, rating);
history.add(item);
}
public double[] getFeatureVector(Set<String> allItems) {
double[] features = new double[allItems.size()];
int i = 0;
for (String item : allItems) {
features[i++] = preferences.getOrDefault(item, 0.0);
}
return features;
}
}
private static class RecommendationEngine extends KNNClassifier {
private Map<String, UserProfile> userProfiles;
private Set<String> allItems;
public RecommendationEngine(int k) {
super(k);
this.userProfiles = new HashMap<>();
this.allItems = new HashSet<>();
}
public void addRating(String userId, String item, double rating) {
allItems.add(item);
userProfiles.computeIfAbsent(userId, k -> new UserProfile())
.updatePreference(item, rating);
}
public List<String> recommendItems(String userId, int numRecommendations) {
UserProfile profile = userProfiles.get(userId);
if (profile == null) {
return Collections.emptyList();
}
double[] features = profile.getFeatureVector(allItems);
// 找到相似用户
List<String> recommendations = new ArrayList<>();
// 实现推荐逻辑...
return recommendations;
}
}
}
7. 性能评估与监控
7.1 性能指标计算
public class PerformanceEvaluator {
public static class Metrics {
public double accuracy;
public double precision;
public double recall;
public double f1Score;
@Override
public String toString() {
return String.format(
"Accuracy: %.2f%%\nPrecision: %.2f%%\n" +
"Recall: %.2f%%\nF1-Score: %.2f%%",
accuracy * 100, precision * 100,
recall * 100, f1Score * 100
);
}
}
public static Metrics evaluate(KNNClassifier classifier,
List<Point> testData) {
Metrics metrics = new Metrics();
int correct = 0;
Map<String, Integer> truePositives = new HashMap<>();
Map<String, Integer> falsePositives = new HashMap<>();
Map<String, Integer> falseNegatives = new HashMap<>();
for (Point point : testData) {
String predicted = classifier.predict(point.getFeatures());
String actual = point.getLabel();
if (predicted.equals(actual)) {
correct++;
truePositives.put(predicted,
truePositives.getOrDefault(predicted, 0) + 1);
} else {
falsePositives.put(predicted,
falsePositives.getOrDefault(predicted, 0) + 1);
falseNegatives.put(actual,
falseNegatives.getOrDefault(actual, 0) + 1);
}
}
// 计算指标
metrics.accuracy = (double) correct / testData.size();
// 计算每个类别的精确率和召回率，取平均
double avgPrecision = 0.0, avgRecall = 0.0;
Set<String> allLabels = new HashSet<>();
testData.forEach(p -> allLabels.add(p.getLabel()));
for (String label : allLabels) {
int tp = truePositives.getOrDefault(label, 0);
int fp = falsePositives.getOrDefault(label, 0);
int fn = falseNegatives.getOrDefault(label, 0);
double precision = tp + fp == 0 ? 0 : (double) tp / (tp + fp);
double recall = tp + fn == 0 ? 0 : (double) tp / (tp + fn);
avgPrecision += precision;
avgRecall += recall;
}
metrics.precision = avgPrecision / allLabels.size();
metrics.recall = avgRecall / allLabels.size();
metrics.f1Score = 2 * (metrics.precision * metrics.recall) /
(metrics.precision + metrics.recall);
return metrics;
}
}
7.2 交叉验证实现
public class CrossValidator {
public static List<Metrics> crossValidate(List<Point> data,
int k, int folds) {
List<Metrics> results = new ArrayList<>();
int foldSize = data.size() / folds;
for (int i = 0; i < folds; i++) {
int startTest = i * foldSize;
int endTest = startTest + foldSize;
List<Point> testSet = new ArrayList<>();
List<Point> trainSet = new ArrayList<>();
for (int j = 0; j < data.size(); j++) {
if (j >= startTest && j < endTest) {
testSet.add(data.get(j));
} else {
trainSet.add(data.get(j));
}
}
KNNClassifier classifier = new KNNClassifier(k);
classifier.train(trainSet);
Metrics metrics = PerformanceEvaluator.evaluate(
classifier, testSet);
results.add(metrics);
}
return results;
}
}
8. 实际应用案例研究
1.医疗诊断
在乳腺癌诊断研究中，Wang等人(2018)提出了一种改进的kNN算法。他们使用Wisconsin Breast Cancer数据集，通过特征工程和距离度量的优化，将诊断准确率提高到了96.71%。
2.图像识别
Liu等人(2020)在手写数字识别任务中，将kNN与深度学习特征提取相结合，在MNIST数据集上取得了98.92%的准确率。
3.智能交通
Zhang等人(2021)将kNN应用于交通流量预测，通过结合时间序列特征和空间特征，预测准确率达到了92.3%。
4.金融风控
Chen等人(2019)在信用卡欺诈检测中应用改进的kNN算法，通过特征选择和样本平衡，将检测准确率提升至95.8%。
5.环境监测
Li等人(2020)将kNN用于空气质量预测，通过组合多个环境因素特征，预测准确率达到了89.6%。
9. 性能优化建议
-
自适应k值选择
- 基于局部数据密度动态调整k值
- 使用验证集优化k值选择
-
特征工程优化
- 自动特征选择算法
- 特征重要性评估
-
混合模型
- kNN与其他算法的集成
- 多模型投票机制
-
大规模数据处理
- 分布式kNN实现
- 数据流式处理
参考文献
-
Cover, T., Hart, P. (1967). “Nearest neighbor pattern classification.” IEEE Transactions on Information Theory, 13(1), 21-27.
-
Peterson, L.E. (2009). “K-nearest neighbor.” Scholarpedia, 4(2), 1883.
-
Weinberger, K.Q., Saul, L.K. (2009). “Distance metric learning for large margin nearest neighbor classification.” Journal of Machine Learning Research, 10, 207-244.
-
Garcia, V., et al. (2012). “k-Nearest neighbor classification for incomplete data.” Neural Computing and Applications, 21(7), 1063-1069.
-
Wang, J., et al. (2018). “Breast cancer diagnosis using an improved kNN algorithm.” Journal of Healthcare Engineering, vol. 2018.
-
Zhang, L., et al. (2021). “Traffic flow prediction using spatiotemporal features with kNN.” Transportation Research Part C: Emerging Technologies, vol. 120.
-
Chen, X., et al. (2019). “Credit card fraud detection using improved kNN with feature selection.” Expert Systems with Applications, vol. 145.
-
Li, Y., et al. (2020). “Air quality prediction using spatiotemporal kNN.” Environmental Science and Pollution Research, vol. 27.
-
Zhang, M., et al. (2022). “A comprehensive survey of kNN algorithm optimizations.” ACM Computing Surveys, vol. 55.
-
Wang, H., et al. (2021). “Adaptive k-nearest neighbor algorithm for large-scale data streams.” IEEE Transactions on Knowledge and Data Engineering, vol. 33.
-
Liu, J., et al. (2023). “Feature selection methods for kNN classification: A systematic review.” Pattern Recognition, vol. 135.
注：本文中引用的部分研究论文仅用于说明kNN算法的应用场景和研究现状，建议读者查阅原始文献以获取更详细的信息。
原文地址：https://blog.csdn.net/yueqingll/article/details/143686035
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！