学步园

最近做聚类实验，实现了几个简单的聚类算法，其中基于最大最小的顺序聚类算法MBSAS就不贴了，受异常点影响很大，其实这个也很好理解，因为选最大距离进行分类(MBSAS先确定类，再根据类里的向量将剩下的样本分到某个类中)的时候，很容易就将异常点作为一个类分出去，那样在分2类的过程中，很明显会出现某个类占95%+，另一个类只有5%以下样本的情况，后者显然就是个异常点，这对我们的聚类是非常不利的，当然用来找异常点还是很有效的。

在实现K-mean算法的时候，也需要找初始点，如果采用最大最小的话还是会遇到这个问题，那么怎么解决这个问题呢？

我的想法是多次分类：如果某个初始点找到之后，第一次分类的结果有一个类的元素的数目特别小，那么就假定这个类的元素是噪声集的一部分，注意噪声集不等于噪声点，但是噪声点一定在噪声集中，而且最重要的是噪声集中的点都不适合作为初始点。然后第二次找初始点，再分类，再判断是否需要重新找，直到找到的所有按照初始点的第一次划分的集合的数目都不是特别小。

执行流程如下：

1. 按照最大最小进行分类得到需要的n个初始点(噪声集的点不能被选作初始点)
2. 按照这n个初始点对所有的元素进行分类，得到n个类，每个类有一些元素
3. 如果这n个类中的某个类，假设为nk的元素的数目小于t，那么将nk中的元素都加到噪集当中
4. 重复1 直到所有的类的元素的数目都大于等于t

那么这里又有一个问题：t是多少？

从直观的角度来想，t应该和样本数目N有关，样本数目越大，t越大，一个1000的样本的某个类有100个元素可能不是噪声，但是一个100000的样本的某个有100个元素的类则可能是噪声。同样，t还要和分类的数目C有关，C越大，t应该越小，1000个元素分为2个类，则一个含有50个元素的类就可能是噪声，但是如果把1000个元素分为10个类，则含有50个元素的类则不太可呢个是噪声，所以综合这两个因素，我设计了一个阈值函数：

t = N / C ^ 2

也就是说当N = 1000，C = 4 的时候， t = 1000/16 = 62，如果某个类小于62个元素，就认为是噪声集，关于这个函数，可以有很多种，比如t = N / (C * 4)，这里面有什么倾向，读者可以自己思考，但是最终结果还是和数据相关。

补：

昨天老师公布了实验结果，我们组的成绩不错，尤其是分两类的情况，基本达到的最优值，但是八类的情况就不是那么好了，我想了想，是阈值函数的问题，因为上交的结果中使用的阈值函数是t = N / C ^ 3，C=8的时候，阈值失去了意义，所以一定程度上会受到噪声点的影响。

今天又想了想，觉得应该使用一个如下的函数：

t = N/(C * asym)   asym = 2,4,8....

这个函数中asym系数是不对乘系数，反应的是最小（数目）的类和最大的类的不对称比例，asym最小也应该为2，如果为1，那么就是均分，不现实，当为2的时候，1000个样本分两类，最小的类是250，如果觉得这个比例还是不够悬殊，可以另asym = 4，也就是最小的类为125，这个看上去就比较合适了，当然如果你比较极端，可以选择更大的不对称系数，但是注意，这里影响的只是对噪声点的判定，和最后的聚类结果的大小没有关系，也就是说如果asym = 8， N =1000，C = 2，那么以一个初始点M为中心的第一次划分的类的数目只要大于 1000/2/8 = 62，就不认为这个点是噪声，显然这看起来有些不合理，一般来说asym=4应该是一个比较好的情况。

完整的代码如下(阈值函数没有引入不对乘系数，读者请自己修改)：

package cn.edu.pku.ss.dm.cluster;<br /> import java.io.BufferedReader;<br /> import java.io.BufferedWriter;<br /> import java.io.FileNotFoundException;<br /> import java.io.FileReader;<br /> import java.io.FileWriter;<br /> import java.io.IOException;<br /> import java.util.ArrayList;<br /> /**<br /> * K-means算法实现<br /> *<br /> * @author eagle<br /> *<br /> */<br /> public class KMeans {<br /> //聚类的数目<br /> final static int ClassCount = 2;<br /> //样本数目(测试集)<br /> final static int InstanseNumber = 1000;<br /> //样本属性数目(测试)<br /> final static int FieldCount = 57;</p> <p> //设置异常点阈值参数(每一类初始的最小数目为InstanseNumber/ClassCount^t)<br /> final static double t = 2.0;<br /> //存放数据的矩阵<br /> private float[][] data;</p> <p> //每个类的均值中心<br /> private float[][] classData;</p> <p> //噪声集合索引<br /> private ArrayList<Integer> noises;</p> <p> //存放每次变换结果的矩阵<br /> private ArrayList<ArrayList<Integer>> result;</p> <p> /**<br /> * 构造函数，初始化<br /> */<br /> public KMeans()<br /> {<br /> //最后一位用来储存结果<br /> data = new float[InstanseNumber][FieldCount + 1];<br /> classData = new float[ClassCount][FieldCount];<br /> result = new ArrayList<ArrayList<Integer>>(ClassCount);<br /> noises = new ArrayList<Integer>();<br /> }</p> <p> /**<br /> * 主函数入口<br /> * 测试集的文件名称为"测试集.data"，其中又1000*57大小的数据<br /> * 每一行为一个样本，有57个属性<br /> * 主要分为两个步骤<br /> * 1.读取数据<br /> * 2.进行聚类<br /> * 最后统计了运行的时间和消耗的内存<br /> * @param args<br /> */<br /> public static void main(String[] args) {<br /> long startTime = System.currentTimeMillis();<br /> KMeans cluster = new KMeans();<br /> //读取数据<br /> cluster.readData("测试集.data");<br /> //聚类过程<br /> cluster.cluster();<br /> //输出结果<br /> cluster.printResult("clusterResult.data");<br /> long endTime = System.currentTimeMillis();<br /> System.out.println("Total Time： " + (endTime - startTime)/1000 + " s");<br /> System.out.println("Memory Consuming: " + (float)(Runtime.getRuntime().totalMemory() -<br /> Runtime.getRuntime().freeMemory())/1000000 + " MB");<br /> }<br /> /**<br /> * 读取测试集的数据<br /> *<br /> * @param trainingFileName 测试集文件名<br /> */<br /> public void readData(String trainingFileName){<br /> try {<br /> FileReader fr = new FileReader(trainingFileName);<br /> BufferedReader br = new BufferedReader(fr);<br /> //存放数据的临时变量<br /> String lineData = null;<br /> String[] splitData = null;<br /> int line = 0;<br /> //按行读取<br /> while(br.ready())<br /> {<br /> //得到原始的字符串<br /> lineData = br.readLine();<br /> splitData = lineData.split(",");<br /> //转化为数据<br /> for(int i = 0;i<splitData.length;i++)<br /> data[line][i] = Float.parseFloat(splitData[i]);<br /> line++;<br /> }<br /> } catch (FileNotFoundException e) {<br /> e.printStackTrace();<br /> } catch (IOException e) {<br /> e.printStackTrace();<br /> }</p> <p> }</p> <p> /**<br /> * 聚类过程，主要分为两步<br /> * 1.循环找初始点<br /> * 2.不断调整直到分类不再发生变化<br /> */<br /> public void cluster()<br /> {<br /> //数据归一化<br /> normalize();<br /> //标记是否需要重新找初始点<br /> boolean needUpdataInitials = true;</p> <p> //找初始点的迭代次数<br /> int times = 1;<br /> //找初始点<br /> while(needUpdataInitials)<br /> {<br /> needUpdataInitials = false;<br /> result.clear();<br /> System.out.println("Find Initials Iteration " + (times++) + " time(s) ");</p> <p> //一次找初始点的尝试和根据初始点的分类<br /> findInitials();<br /> firstClassify();</p> <p> //如果某个分类的数目小于特定的阈值、则认为这个分类中的所有样本都是噪声点<br /> //需要重新找初始点<br /> for(int i = 0; i < result.size();i++){<br /> if(result.get(i).size() < InstanseNumber / Math.pow(ClassCount, t)){<br /> needUpdataInitials = true;<br /> noises.addAll(result.get(i));<br /> }<br /> }<br /> }</p> <p> //找到合适的初始点后<br /> //不断的调整均值中心和分类、直到不再发生任何变化<br /> Adjust();<br /> }</p> <p> /**<br /> * 对数据进行归一化<br /> * 1.找每一个属性的最大值<br /> * 2.对某个样本的每个属性除以其最大值<br /> */<br /> public void normalize(){</p> <p> //找最大值<br /> float[] max = new float[FieldCount];<br /> for(int i = 0;i<InstanseNumber;i++){<br /> for(int j = 0;j < FieldCount ;j++){<br /> if(data[i][j] > max[j])<br /> max[j] = data[i][j];<br /> }<br /> }</p> <p> //归一化<br /> for(int i = 0;i<InstanseNumber;i++){<br /> for(int j = 0;j < FieldCount ;j++){<br /> data[i][j] = data[i][j]/max[j];<br /> }<br /> }<br /> }</p> <p> /**<br /> * 关于初始向量的一次找寻尝试<br /> */<br /> public void findInitials(){</p> <p> //a,b为标志距离最远的两个向量的索引<br /> int i,j,a,b;<br /> i = j = a = b = 0;</p> <p> //最远距离<br /> float maxDis = 0;</p> <p> //已经找到的初始点个数<br /> int alreadyCls = 2;</p> <p> //存放已经标记为初始点的向量索引<br /> ArrayList<Integer> initials = new ArrayList<Integer>();</p> <p> //从两个开始<br /> for(;i < InstanseNumber;i++)<br /> {<br /> //噪声点<br /> if(noises.contains(i))<br /> continue;<br /> //long startTime = System.currentTimeMillis();<br /> j = i + 1;<br /> for(; j < InstanseNumber;j++)<br /> {<br /> //噪声点<br /> if(noises.contains(j))<br /> continue;<br /> //找到最大的距离并记录下来<br /> float newDis = calDis(data[i], data[j]);<br /> if( maxDis < newDis)<br /> {<br /> a = i;<br /> b = j;<br /> maxDis = newDis;<br /> }<br /> }<br /> //long endTime = System.currentTimeMillis();<br /> //System.out.println(i + " Vector Caculation Time:" + (endTime - startTime) + " ms");<br /> }</p> <p> //将前两个初始点记录下来<br /> initials.add(a);<br /> initials.add(b);<br /> classData[0] = data[a];<br /> classData[1] = data[b];</p> <p> //在结果中新建存放某类样本索引的对象，并把初始点添加进去<br /> ArrayList<Integer> resultOne = new ArrayList<Integer>();<br /> ArrayList<Integer> resultTwo = new ArrayList<Integer>();<br /> resultOne.add(a);<br /> resultTwo.add(b);<br /> result.add(resultOne);<br /> result.add(resultTwo);</p> <p> //找到剩余的几个初始点<br /> while( alreadyCls < ClassCount){<br /> i = j = 0;<br /> float maxMin = 0;<br /> int newClass = -1;</p> <p> //找最小值中的最大值<br /> for(;i < InstanseNumber;i++){<br /> float min = 0;<br /> float newMin = 0;<br /> //找和已有类的最小值<br /> if(initials.contains(i))<br /> continue;<br /> //噪声点去除<br /> if(noises.contains(i))<br /> continue;<br /> for(j = 0;j < alreadyCls;j++){<br /> newMin = calDis(data[i], classData[j]);<br /> if(min == 0 || newMin < min)<br /> min = newMin;<br /> }</p> <p> //新最小距离较大<br /> if(min > maxMin)<br /> {<br /> maxMin = min;<br /> newClass = i;<br /> }</p> <p> }<br /> //添加到均值集合和结果集合中<br /> //System.out.println("NewClass " + newClass);<br /> initials.add(newClass);<br /> classData[alreadyCls++] = data[newClass];<br /> ArrayList<Integer> rslt = new ArrayList<Integer>();<br /> rslt.add(newClass);<br /> result.add(rslt);<br /> }</p> <p> }</p> <p> /**<br /> * 第一次分类<br /> */<br /> public void firstClassify()<br /> {<br /> //根据初始向量分类<br /> for(int i = 0;i < InstanseNumber;i++)<br /> {<br /> float min = 0f;<br /> int clsId = -1;<br /> for(int j = 0;j < classData.length;j++){<br /> //欧式距离<br /> float newMin = calDis(classData[j], data[i]);<br /> if(clsId == -1 || newMin < min){<br /> clsId = j;<br /> min = newMin;</p> <p> }<br /> }<br /> //本身不再添加<br /> if(!result.get(clsId).contains(i))<br /> {<br /> result.get(clsId).add(i);<br /> }<br /> }</p> <p> }</p> <p> /**<br /> * 迭代分类、直到各个类的数据不再变化<br /> */<br /> public void Adjust()<br /> {<br /> //记录是否发生变化<br /> boolean change = true;</p> <p> //循环的次数<br /> int times = 1;<br /> while(change){<br /> //复位<br /> change = false;<br /> System.out.println("Adjust Iteration " + (times++) + " time(s) ");</p> <p> //重新计算每个类的均值<br /> for(int i = 0;i < ClassCount; i++){<br /> //原有的数据<br /> ArrayList<Integer> cls = result.get(i);</p> <p> //新的均值<br /> float[] newMean = new float[FieldCount ];</p> <p> //计算均值<br /> for(Integer index:cls){<br /> for(int j = 0;j < FieldCount ;j++)<br /> newMean[j] += data[index][j];<br /> }<br /> for(int j = 0;j < FieldCount ;j++)<br /> newMean[j] /= cls.size();<br /> if(!compareMean(newMean, classData[i])){<br /> classData[i] = newMean;<br /> change = true;<br /> }<br /> }<br /> //清空之前的数据<br /> for(ArrayList<Integer> cls:result)<br /> cls.clear();</p> <p> //重新分配<br /> for(int i = 0;i < InstanseNumber;i++)<br /> {<br /> float min = 0f;<br /> int clsId = -1;<br /> for(int j = 0;j < classData.length;j++){<br /> float newMin = calDis(classData[j], data[i]);<br /> if(clsId == -1 || newMin < min){<br /> clsId = j;<br /> min = newMin;<br /> }<br /> }<br /> data[i][FieldCount] = clsId;<br /> result.get(clsId).add(i);<br /> }</p> <p> //测试聚类效果(训练集)<br /> // for(int i = 0;i < ClassCount;i++){<br /> // int positives = 0;<br /> // int negatives = 0;<br /> // ArrayList<Integer> cls = result.get(i);<br /> // for(Integer instance:cls)<br /> // if (data[instance][FieldCount - 1] == 1f)<br /> // positives ++;<br /> // else<br /> // negatives ++;<br /> // System.out.println(" " + i + " Positive: " + positives + " Negatives: " + negatives);<br /> // }<br /> // System.out.println();<br /> }</p> <p> }</p> <p> /**<br /> * 计算a样本和b样本的欧式距离作为不相似度<br /> *<br /> * @param a 样本a<br /> * @param b 样本b<br /> * @return 欧式距离长度<br /> */<br /> private float calDis(float[] aVector,float[] bVector)<br /> {<br /> double dis = 0;<br /> int i = 0;</p> <p> //最后一个数据在训练集中为结果，所以不考虑<br /> for(;i < aVector.length;i++)<br /> dis += Math.pow(bVector[i] - aVector[i],2);<br /> dis = Math.pow(dis, 0.5);<br /> return (float)dis;<br /> }</p> <p> /**<br /> * 判断两个均值向量是否相等<br /> *<br /> * @param a 向量a<br /> * @param b 向量b<br /> * @return<br /> */<br /> private boolean compareMean(float[] a,float[] b)<br /> {<br /> if(a.length != b.length)<br /> return false;<br /> for(int i =0;i < a.length;i++){<br /> if(a[i] > 0 &&b[i] > 0&& a[i] != b[i]){<br /> return false;<br /> }<br /> }<br /> return true;<br /> }</p> <p> /**<br /> * 将结果输出到一个文件中<br /> *<br /> * @param fileName<br /> */<br /> public void printResult(String fileName)<br /> {<br /> FileWriter fw = null;<br /> BufferedWriter bw = null;<br /> try {<br /> fw = new FileWriter(fileName);<br /> bw = new BufferedWriter(fw);<br /> //写入文件<br /> for(int i = 0;i < InstanseNumber;i++)<br /> {<br /> bw.write(String.valueOf(data[i][FieldCount]).substring(0, 1));<br /> bw.newLine();<br /> }</p> <p> //统计每类的数目，打印到控制台<br /> for(int i = 0;i < ClassCount;i++)<br /> {<br /> System.out.println("第" + (i+1) + "类数目: " + result.get(i).size());<br /> }<br /> } catch (IOException e) {<br /> e.printStackTrace();<br /> } finally{</p> <p> //关闭资源<br /> if(bw != null)<br /> try {<br /> bw.close();<br /> } catch (IOException e) {<br /> e.printStackTrace();<br /> }<br /> if(fw != null)<br /> try {<br /> fw.close();<br /> } catch (IOException e) {<br /> e.printStackTrace();<br /> }<br /> }</p> <p> }<br /> }<br />