社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
一,k-means算法介绍:
k-means算法接受输入量 k ;然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。 k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。
k-means算法的工作过程说明如下:首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。
二,k-means算法基本步骤:
(1) 从 n个数据对象任意选择 k 个对象作为初始聚类中心;
(2) 根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;
(3) 重新计算每个(有变化)聚类的均值(中心对象);
(4) 计算标准测度函数,当满足一定条件,如函数收敛时,则算法终止;如果条件不满足则回到步骤(2),不断重复直到标准测度函数开始收敛为止。(一般都采用均方差作为标准测度函数。)
三,k-means算法的java实现:
一共有七个类,General.java代表武将对象, Distance.java距离类计算各个武将到中心武将之间的距离, Cluster.java聚类对象包含一个中心武将和该聚类中所有武将, Kmeans.java核心的聚类算法类, Tool.java工具类用于转换武将的星级为数字等操作, TestKmeans.java测试类即入口文件, DomParser.java用于读取xml中的681个武将。
具体思路:先从general.xml文件中读取681个武将,然后随机选取初始类中心,计算各个武将到中心武将的距离,根据最小的距离进行聚类,然后重新根据平均值新的聚类的类中心,重新计算各个武将到新的中心武将的距离,直到更新后的聚类与原来的聚类包含的武将不再改变,即收敛时结束。
具体代码如下:
1,General.java
- </pre><pre name="code" class="java">
- </pre><pre name="code" class="java">package kmeans;
- public class General {
- private String name; // 姓名
- private int render; // 星级
- private int tongshai; // 统帅
- private int wuli; // 武力
- private int zhili; // 智力
- private int polic; // 政治
- private int qiangbin; // 枪兵
- private int jibin; // 戟兵
- private int nubin; // 弩兵
- private int qibin; // 骑兵
- private int binqi; // 兵器
- private int tongwu; // 统武
- private int tongzhi; // 统智
- private int tongwuzhi; // 统武智
- private int tongwuzhizheng; // 统武智政
- private int salary; // 50级工资
- public General(int render, String name, int tongshai, int wuli, int zhili,
- int polic, int qiangbin, int jibin, int nubin, int qibin,
- int binqi, int tongwu, int tongzhi, int tongwuzhi,
- int tongwuzhizheng, int salary) {
- super();
- this.name = name;
- this.render = render;
- this.tongshai = tongshai;
- this.wuli = wuli;
- this.zhili = zhili;
- this.polic = polic;
- this.qiangbin = qiangbin;
- this.jibin = jibin;
- this.nubin = nubin;
- this.qibin = qibin;
- this.binqi = binqi;
- this.tongwu = tongwu;
- this.tongzhi = tongzhi;
- this.tongwuzhi = tongwuzhi;
- this.tongwuzhizheng = tongwuzhizheng;
- this.salary = salary;
- }
- public General(int render, int tongshai, int wuli, int zhili, int polic,
- int qiangbin, int jibin, int nubin, int qibin, int binqi,
- int tongwu, int tongzhi, int tongwuzhi, int tongwuzhizheng,
- int salary) {
- super();
- this.name = "聚类中心";
- this.render = render;
- this.tongshai = tongshai;
- this.wuli = wuli;
- this.zhili = zhili;
- this.polic = polic;
- this.qiangbin = qiangbin;
- this.jibin = jibin;
- this.nubin = nubin;
- this.qibin = qibin;
- this.binqi = binqi;
- this.tongwu = tongwu;
- this.tongzhi = tongzhi;
- this.tongwuzhi = tongwuzhi;
- this.tongwuzhizheng = tongwuzhizheng;
- this.salary = salary;
- }
- public General() {
- }
- @Override
- public String toString() {
- return "武将 [name=" + name + ", render=" + Tool.dxingji(render)
- + ", tongshai=" + tongshai + ", wuli=" + wuli + ", zhili="
- + zhili + ", polic=" + polic + ", qiangbin="
- + Tool.dchange(qiangbin) + ", jibin=" + Tool.dchange(jibin)
- + ", nubin=" + Tool.dchange(nubin) + ", qibin="
- + Tool.dchange(qibin) + ", binqi=" + Tool.dchange(binqi)
- + ", tongwu=" + tongwu + ", tongzhi=" + tongzhi
- + ", tongwuzhi=" + tongwuzhi + ", tongwuzhizheng="
- + tongwuzhizheng + ", salary=" + salary + "]";
- }
- public String getName() {
- return name;
- }
- public void setName(String name) {
- this.name = name;
- }
- public int getRender() {
- return render;
- }
- public void setRender(int render) {
- this.render = render;
- }
- public int getTongshai() {
- return tongshai;
- }
- public void setTongshai(int tongshai) {
- this.tongshai = tongshai;
- }
- public int getWuli() {
- return wuli;
- }
- public void setWuli(int wuli) {
- this.wuli = wuli;
- }
- public int getZhili() {
- return zhili;
- }
- public void setZhili(int zhili) {
- this.zhili = zhili;
- }
- public int getPolic() {
- return polic;
- }
- public void setPolic(int polic) {
- this.polic = polic;
- }
- public int getQiangbin() {
- return qiangbin;
- }
- public void setQiangbin(int qiangbin) {
- this.qiangbin = qiangbin;
- }
- public int getJibin() {
- return jibin;
- }
- public void setJibin(int jibin) {
- this.jibin = jibin;
- }
- public int getNubin() {
- return nubin;
- }
- public void setNubin(int nubin) {
- this.nubin = nubin;
- }
- public int getQibin() {
- return qibin;
- }
- public void setQibin(int qibin) {
- this.qibin = qibin;
- }
- public int getBinqi() {
- return binqi;
- }
- public void setBinqi(int binqi) {
- this.binqi = binqi;
- }
- public int getTongwu() {
- return tongwu;
- }
- public void setTongwu(int tongwu) {
- this.tongwu = tongwu;
- }
- public int getTongzhi() {
- return tongzhi;
- }
- public void setTongzhi(int tongzhi) {
- this.tongzhi = tongzhi;
- }
- public int getTongwuzhi() {
- return tongwuzhi;
- }
- public void setTongwuzhi(int tongwuzhi) {
- this.tongwuzhi = tongwuzhi;
- }
- public int getTongwuzhizheng() {
- return tongwuzhizheng;
- }
- public void setTongwuzhizheng(int tongwuzhizheng) {
- this.tongwuzhizheng = tongwuzhizheng;
- }
- public int getSalary() {
- return salary;
- }
- public void setSalary(int salary) {
- this.salary = salary;
- }
- }
2,Distance.java
- </pre><pre name="code" class="java">package kmeans;
- /**
- * 这个类用于计算距离的。。
- *
- */
- public class Distance {
- int dest;// 目的
- int source;// 源
- double dist;// 欧式距离
- public int getDest() {
- return dest;
- }
- public void setDest(int dest) {
- this.dest = dest;
- }
- public int getSource() {
- return source;
- }
- public void setSource(int source) {
- this.source = source;
- }
- public double getDist() {
- return dist;
- }
- public void setDist(double dist) {
- this.dist = dist;
- }
- /**
- * 计算源和目的的距离
- * @param dest 目的武将
- * @param source 源武将
- * @param dist 两者间的距离
- */
- public Distance(int dest, int source, double dist) {
- this.dest = dest;
- this.source = source;
- this.dist = dist;
- }
- public Distance() {
- }
- }
3,Cluster.java
- </pre><pre name="code" class="java">package kmeans;
- import java.util.ArrayList;
- public class Cluster {
- private int center;// 聚类中心武将的id
- private ArrayList<General> ofCluster = new ArrayList<General>();// 属于这个聚类的武将的集合
- public int getCenter() {
- return center;
- }
- public void setCenter(int center) {
- this.center = center;
- }
- public ArrayList<General> getOfCluster() {
- return ofCluster;
- }
- public void setOfCluster(ArrayList<General> ofCluster) {
- this.ofCluster = ofCluster;
- }
- public void addGeneral(General general) {
- if (!(this.ofCluster.contains(general)))
- this.ofCluster.add(general);
- }
- }
4,Kmeans.java
- </pre><pre name="code" class="java">
- package kmeans;
- import java.util.*;
- public class Kmeans {
- public ArrayList<General> allGenerals = null;
- public int totalNumber = 0;// 得到所有的武将数目
- public int K = 0;// 假设K=10
- public Kmeans() {
- allGenerals = new DomParser().prepare();
- totalNumber = allGenerals.size();
- K = 3;
- }
- // 第一次随机选取聚类中心
- public Set<Integer> firstRandom() {
- Set<Integer> center = new HashSet<Integer>();// 聚类中心的点的id,采用set保证不会有重复id
- Random ran = new Random();
- int roll = ran.nextInt(totalNumber);
- while (center.size() < K) {
- roll = ran.nextInt(totalNumber);
- center.add(roll);
- }
- return center;
- }
- // 根据聚类中心初始化聚类信息
- public ArrayList<Cluster> init(Set<Integer> center) {
- ArrayList<Cluster> cluster = new ArrayList<Cluster>();// 聚类 的数组
- Iterator<Integer> it = center.iterator();
- while (it.hasNext()) {
- Cluster c = new Cluster();// 代表一个聚类
- c.setCenter(it.next());
- cluster.add(c);
- }
- return cluster;
- }
- /**
- * 计算各个武将到各个聚类中心的距离,重新聚类
- *
- * @param cluster
- * 聚类数组,用来聚类的,根据最近原则把武将聚类
- * @param center
- * 中心点id,用于计算各个武将到中心点的距离 return cluster 聚类后的所有聚类组成的数组
- */
- public ArrayList<Cluster> juLei(Set<Integer> center,
- ArrayList<Cluster> cluster) {
- ArrayList<Distance> distence = new ArrayList<Distance>();// 存放距离信息,表示每个点到各个中心点的距离组成的数组
- General source = null;
- General dest = null;
- int id = 0;// 目的节点id
- int id2 = 0;// 源节点id
- Object[] p = center.toArray();// p 为聚类中心点id数组
- boolean flag = false;
- // 分别计算各个点到各个中心点的距离,并将距离最小的加入到各个聚类中,进行聚类
- for (int i = 0; i < totalNumber; i++) {
- // 每个点计算完,并聚类到距离最小的聚类中就清空距离数组
- distence.clear();
- // 计算到j个类中心点的距离,便利各个中心点
- for (int j = 0; j < center.size(); j++) {
- // 如果该点不在中心点内 则计算距离
- if (!(center.contains(i))) {
- flag = true;
- // 计算距离
- source = allGenerals.get(i);// 某个点
- dest = allGenerals.get((Integer) p[j]);// 各个 中心点
- // 计算距离并存入数组
- distence.add(new Distance((Integer) p[j], i, Tool.juli(
- source, dest)));
- } else {
- flag = false;
- }
- }
- // 说明计算完某个武将到类中心的距离,开始比较
- if (flag == true) {
- // 排序比较一个点到各个中心的距离的大小,找到距离最小的武将的 目的id,和源id,
- // 目的id即类中心点id,这个就归到这个中心点所在聚类中
- double min = distence.get(0).getDist();// 默认第一个distance距离是最小的
- // 从1开始遍历distance数组
- int minid = 0;
- for (int k = 1; k < distence.size(); k++) {
- if (min > distence.get(k).getDist()) {
- min = distence.get(k).getDist();
- id = distence.get(k).getDest();// 目的,即类中心点
- id2 = distence.get(k).getSource();// 某个武将
- minid = k;
- } else {
- id = distence.get(minid).getDest();
- id2 = distence.get(minid).getSource();
- }
- }
- // 遍历cluster聚类数组,找到类中心点id与最小距离目的武将id相同的聚类
- for (int n = 0; n < cluster.size(); n++) {
- // 如果和中心点的id相同 则setError
- if (cluster.get(n).getCenter() == id) {
- cluster.get(n).addGeneral(allGenerals.get(id2));// 将与该聚类中心距离最小的武将加入该聚类
- break;
- }
- }
- }
- }
- return cluster;
- }
- // 产生新的聚类中心点数组
- public Set<Integer> updateCenter() {
- Set<Integer> center = new HashSet<Integer>();
- for (int i = 0; i < K; i++) {
- center.add(i);
- }
- return center;
- }
- // 更新聚类中心, 求平均值
- public ArrayList<Cluster> updateCluster(ArrayList<Cluster> cluster) {
- ArrayList<Cluster> result = new ArrayList<Cluster>();
- // 重新产生的新的聚类中心组成的数组
- // k个聚类进行更新聚类中心
- for (int j = 0; j < K; j++) {
- ArrayList<General> ps = cluster.get(j).getOfCluster();// 该聚类的所有 武将
- // 组成的数组
- ps.add(allGenerals.get(cluster.get(j).getCenter()));// 同时将该类中心对应的武将加入该武将数组
- int size = ps.size();// 该聚类的长度大小
- // 计算和,然后在计算平均值
- int sumrender = 0, sumtongshai = 0, sumwuli = 0, sumzhili = 0, sumjibin = 0, sumnubin = 0, sumqibin = 0, sumpolic = 0, sumqiangbin = 0, sumbinqi = 0, sumtongwu = 0, sumtongzhi = 0, sumtongwuzhi = 0, sumtongwuzhizheng = 0, sumsalary = 0;
- for (int k1 = 0; k1 < size; k1++) {
- sumrender += ps.get(k1).getRender();
- sumtongshai += ps.get(k1).getRender();
- sumwuli += ps.get(k1).getWuli();
- sumzhili += ps.get(k1).getZhili();
- sumjibin += ps.get(k1).getJibin();
- sumnubin += ps.get(k1).getNubin();
- sumqibin += ps.get(k1).getQibin();
- sumpolic += ps.get(k1).getPolic();
- sumqiangbin += ps.get(k1).getQiangbin();
- sumbinqi += ps.get(k1).getBinqi();
- sumtongwu += ps.get(k1).getTongwu();
- sumtongzhi += ps.get(k1).getTongzhi();
- sumtongwuzhi += ps.get(k1).getTongwuzhi();
- sumtongwuzhizheng += ps.get(k1).getTongwuzhizheng();
- sumsalary += ps.get(k1).getSalary();
- }
- // 产生新的聚类,然后加入到聚类数组中
- Cluster newCluster = new Cluster();
- newCluster.setCenter(j);
- // 计算平均值并构造新的武将对象
- newCluster.addGeneral(new General(sumrender / size, sumtongshai
- / size, sumwuli / size, sumzhili / size, sumjibin / size,
- sumnubin / size, sumqibin / size, sumpolic = 0,
- sumqiangbin = 0, sumbinqi / size, sumtongwu / size,
- sumtongzhi / size, sumtongwuzhi / size, sumtongwuzhizheng
- / size, sumsalary / size));
- result.add(newCluster);
- }
- return result;
- }
- /**
- * 计算各个武将到各个更新后的聚类中心的距离,重新聚类
- * @param update 更新后的聚类中心
- * @param cluster 要存储的聚类中心
- */
- public ArrayList<Cluster> updateJuLei(ArrayList<Cluster> update,
- ArrayList<Cluster> cluster) {
- ArrayList<Distance> distence = new ArrayList<Distance>();// 存放距离信息,表示每个点到各个中心点的距离组成的数组
- General source = null;
- General dest = null;
- int id = 0;// 目的节点id
- int id2 = 0;// 源节点id
- //Object[] p = center.toArray();// p 为聚类中心点id数组
- boolean flag = false;
- // 分别计算各个点到各个中心点的距离,并将距离最小的加入到各个聚类中,进行聚类
- for (int i = 0; i < totalNumber; i++) {
- // 每个点计算完,并聚类到距离最小的聚类中就清空距离数组
- distence.clear();
- // 计算到j个类中心点的距离,便利各个中心点
- //for (int j = 0; j < center.size(); j++) {
- for (int j = 0; j < update.size(); j++) {
- // 如果该点不在中心点内 则计算距离
- //if (!(center.contains(i))) {
- flag = true;
- // 计算距离
- source = allGenerals.get(i);// 某个点
- // dest = allGenerals.get((Integer) p[j]);// 各个 中心点
- dest = update.get(j).getOfCluster().get(0);// 各个 中心点
- // 计算距离并存入数组
- //distence.add(new Distance((Integer) p[j], i, Tool.juli(
- distence.add(new Distance(update.get(j).getCenter(), i, Tool.juli(
- source, dest)));
- /*} else {
- flag = false;
- }*/
- }
- // 说明计算完某个武将到类中心的距离,开始比较
- if (flag == true) {
- // 排序比较一个点到各个中心的距离的大小,找到距离最小的武将的 目的id,和源id,
- // 目的id即类中心点id,这个就归到这个中心点所在聚类中
- double min = distence.get(0).getDist();// 默认第一个distance距离是最小的
- // 从1开始遍历distance数组
- int mid = 0;
- for (int k = 1; k < distence.size(); k++) {
- if (min > distence.get(k).getDist()) {
- min = distence.get(k).getDist();
- id = distence.get(k).getDest();// 目的,即类中心点
- id2 = distence.get(k).getSource();// 某个武将
- mid = k;
- } else {
- id = distence.get(mid).getDest();
- id2 = distence.get(mid).getSource();
- }
- }
- // 遍历cluster聚类数组,找到类中心点id与最小距离目的武将id相同的聚类
- for (int n = 0; n < cluster.size(); n++) {
- // 如果和中心点的id相同 则setError
- if (cluster.get(n).getCenter() == id) {
- cluster.get(n).addGeneral(allGenerals.get(id2));// 将与该聚类中心距离最小的武将加入该聚类
- }
- }
- }
- }
- return cluster;
- }
- // 不断循环聚类直到各个聚类没有重新分配
- public ArrayList<Cluster> getResu
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!