大数据挖掘实践——K-Means聚类算法
发布时间
阅读量：
阅读量
大数据挖掘实践
K-Means聚类算法
引言：
我们有n个数据集D={X₁,X₂,…,Xₙ} ，我们的目标是将这些数据划分为K个类别 。确定合适的分类数量是一个关键问题；此外，在选择初始点时也面临一定的挑战 。为此 ，我们引入了距离概念 （以欧氏距离为例） 。我们的目标是寻找K个中心点 ，这些中心点能够帮助我们将数据合理地分类 。具体来说 ，每个样本将被归类到与其最近的中心点所属的类别中 。同时 ，这种划分方式的好处是可以使所有样本到各个中心点的距离总和最小化 。
算法介绍：
L-Means也被称为K均值算法，在基于已知类别数量进行数据划分方面具有显著优势。作为一种典型的基于距离的空间聚类方法，在计算过程中主要依据样本间的距离来度量相似性程度。其中K代表数据中被划分为不同簇的数量；其输入主要为待处理的数据集以及预设的类别数目；通过迭代运算将原始数据集划分为若干个具有较高相似度的数据簇；该过程最终输出的结果即为将数据划分为K个簇后的分类结果；与之类似的还有K-Nearest Neighbors（KNN）算法，在两者之间主要区别在于利用的距离计算方式不同
算法框架：
（1）初始化参数k值，并从n个初始数据样本中随机选择k个样本作为聚类中心。
（2）对于每一个数据样本x_i（i=1,2,…,n），计算其与所有聚类中心c_j（j=1,2,…,k）之间的距离。
（3）对于每一个分类好的类别中的所有样本x_i（i=1,2,…,n），计算其均值向量μ_m作为新的聚类中心m的坐标位置。
（4）重复上述步骤直至最终的聚类中心稳定不再变化。
（流程图）
数据描述：
训练用例集合
生成一个名为input.txt的文本文件，并随机生成若干组测试样本作为输入。
将这些测试样本导入到该文本文件中进行处理。
实践过程
代码实现：
创建主实现类：
package KMeans;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Collections;
/** * k均值算法工具类
* * @author wxy
* */
public class KMeansTool {
// 输入数据文件地址
private String filePath;
// 分类类别个数
private int classNum;
// 类名称
private ArrayList<String> classNames;
// 聚类坐标点
private ArrayList<Point> classPoints;
// 所有的数据左边点
private ArrayList<Point> totalPoints;
public KMeansTool(String filePath, int classNum) {
this.filePath = filePath;
this.classNum = classNum;
readDataFile();
}
/** * 从文件中读取数据
*/
private void readDataFile() {
File file = new File(filePath);
ArrayList<String[]> dataArray = new ArrayList<String[]>();
try {
BufferedReader in = new BufferedReader(new FileReader(file));
String str;
String[] tempArray;
while ((str = in.readLine()) != null) {
tempArray = str.split(" ");
dataArray.add(tempArray);
}
in.close();
} catch (IOException e) {
e.getStackTrace();
}
classPoints = new ArrayList<>();
totalPoints = new ArrayList<>();
classNames = new ArrayList<>();
for (int i = 0, j = 1; i < dataArray.size(); i++) {
if (j <= classNum) {
classPoints.add(new Point(dataArray.get(i)[0],
dataArray.get(i)[1], j + ""));
classNames.add(i + "");
j++;
}
totalPoints
.add(new Point(dataArray.get(i)[0], dataArray.get(i)[1]));
}
}
/** * K均值聚类算法实现
*/
public void kMeansClustering() {
double tempX = 0;
double tempY = 0;
int count = 0;
double error = Integer.MAX_VALUE;
Point temp;
while (error > 0.01 * classNum) {
for (Point p1 : totalPoints) {
// 将所有的测试坐标点就近分类
for (Point p2 : classPoints) {
p2.computerDistance(p1);
}
Collections.sort(classPoints);
// 取出p1离类坐标点最近的那个点
p1.setClassName(classPoints.get(0).getClassName());
}
error = 0;
// 按照均值重新划分聚类中心点
for (Point p1 : classPoints) {
count = 0;
tempX = 0;
tempY = 0;
for (Point p : totalPoints) {
if (p.getClassName().equals(p1.getClassName())) {
count++;
tempX += p.getX();
tempY += p.getY();
}
}
tempX /= count;
tempY /= count;
error += Math.abs((tempX - p1.getX()));
error += Math.abs((tempY - p1.getY()));
// 计算均值
p1.setX(tempX);
p1.setY(tempY);
}
for (int i = 0; i < classPoints.size(); i++) {
temp = classPoints.get(i);
System.out.println(MessageFormat.format("聚类中心点{0}，x={1},y={2}",
(i + 1), temp.getX(), temp.getY()));
}
System.out.println("----------");
}
System.out.println("结果值收敛");
for (int i = 0; i < classPoints.size(); i++) {
temp = classPoints.get(i);
System.out.println(MessageFormat.format("聚类中心点{0}，x={1},y={2}",
(i + 1), temp.getX(), temp.getY()));
}
}
}坐标点类：
package KMeans;
/** * 坐标点类
* * @author wxy
* */
public class Point implements Comparable<Point>{
// 坐标点横坐标
private double x;
// 坐标点纵坐标
private double y;
//以此点作为聚类中心的类的类名称
private String className;
// 坐标点之间的欧式距离
private Double distance;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
public Point(String x, String y) {
this.x = Double.parseDouble(x);
this.y = Double.parseDouble(y);
}
public Point(String x, String y, String className) {
this.x = Double.parseDouble(x);
this.y = Double.parseDouble(y);
this.className = className;
}
public void computerDistance(Point p) {
if (p == null) {
return;
}
this.distance = (this.x - p.x) * (this.x - p.x) + (this.y - p.y)
* (this.y - p.y);
}
public double getX() {
return x;
}
public void setX(double x) {
this.x = x;
}
public double getY() {
return y;
}
public void setY(double y) {
this.y = y;
}
public String getClassName() {
return className;
}
public void setClassName(String className) {
this.className = className;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
@Override
public int compareTo(Point o) {
// TODO Auto-generated method stub
return this.distance.compareTo(o.distance);
}
}调用类：
package KMeans;
public class Client {
public static void main(String[] args){
String filePath = "D:\ dashuju\ src\ KMeans\ input.txt";
int classNum = 3;
KMeansTool tool = new KMeansTool(filePath, classNum);
tool.kMeansClustering();
}
}测试结果：
在本次实现K-Means聚类算法的实验中,我对该算法的理解更加深入.首先K-Means算法的主要优势在于其简单易懂的特点,并未涉及复杂的数据结构.然而尽管如此,在应用过程中仍需注意其缺点:参数k的选择具有一定的难度,并且由于计算过程是迭代性的,在处理大数据量时会占用较多的内存资源和时间.即使这只是一小部分内容,在完成本次实验并学习大数据课程后发现该领域非常有趣,并进一步充实了自己的知识储备.
全部评论 (0)
还没有任何评论哟~