A. 数据挖掘题目，K—均值算法应用
第一轮
A1(2,10)
B1（5,8），A3（8,4）， B2（7,5），B3（6,4），C2（4，9）
C1（1,2），A2（2,5）
对应中心分别是（2,10)，（6,6）,(1.5, 3.5)
最后结果：
｛A1(2,10)，B1（5,8），C2（4，9）｝
｛A3（8,4）， B2（7,5），B3（6,4）｝
｛C1（1,2），A2（2,5）｝
B. 八：聚类算法K-means（20191223-29)
学习内容：无监督聚类算法K-Means
k-means：模型原理、收敛过程、超参数的选择
聚类分析是在数据中发现数据对象之间的关系，将数据进行分组，组内的相似性越大，组间的差别越大，则聚类效果越好。
不同的簇类型： 聚类旨在发现有用的对象簇，在现实中我们用到很多的簇的类型，使用不同的簇类型划分数据的结果是不同的。
基于原型的： 簇是对象的集合，其中每个对象到定义该簇的 原型 的距离比其他簇的原型距离更近，如(b)所示的原型即为中心点，在一个簇中的数据到其中心点比到另一个簇的中心点更近。这是一种常见的 基于中心的簇 ，最常用的K-Means就是这样的一种簇类型。 这样的簇趋向于球形。
基于密度的 ：簇是对象的密度区域，(d)所示的是基于密度的簇，当簇不规则或相互盘绕，并且有早上和离群点事，常常使用基于密度的簇定义。
关于更多的簇介绍参考《数据挖掘导论》。
基本的聚类分析算法
1. K均值： 基于原型的、划分的距离技术，它试图发现用户指定个数(K)的簇。
2. 凝聚的层次距离： 思想是开始时，每个点都作为一个单点簇，然后，重复的合并两个最靠近的簇，直到尝试单个、包含所有点的簇。
3. DBSCAN: 一种基于密度的划分距离的算法，簇的个数有算法自动的确定，低密度中的点被视为噪声而忽略，因此其不产生完全聚类。
不同的距离量度会对距离的结果产生影响，常见的距离量度如下所示：
优点：易于实现
缺点：可能收敛于局部最小值，在大规模数据收敛慢
算法思想：
选择K个点作为初始质心
repeat
将每个点指派到最近的质心，形成K个簇
重新计算每个簇的质心
until 簇不发生变化或达到最大迭代次数
这里的“重新计算每个簇的质心”，是根据目标函数来计算的，因此在开始时要考虑 距离度量和目标函数。
考虑欧几里得距离的数据，使用 误差平方和（Sum of the Squared Error,SSE） 作为聚类的目标函数，两次运行K均值产生的两个不同的簇集，使用SSE最小的那个。
k表示k个聚类中心，ci表示第几个中心，dist表示的是欧几里得距离。
这里有一个问题就是为什么，我们更新质心是让所有的点的平均值，这里就是SSE所决定的。
k均值算法非常简单且使用广泛，但是其有主要的两个缺陷：
1. K值需要预先给定 ，属于预先知识，很多情况下K值的估计是非常困难的，对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行。对于可以确定K值不会太大但不明确精确的K值的场景，可以进行迭代运算，然后找出Cost Function最小时所对应的K值，这个值往往能较好的描述有多少个簇类。
2. K-Means算法对初始选取的聚类中心点是敏感的 ，不同的随机种子点得到的聚类结果完全不同
3. K均值算法并不是很所有的数据类型。 它不能处理非球形簇、不同尺寸和不同密度的簇，银冠指定足够大的簇的个数是他通常可以发现纯子簇。
4. 对离群点的数据进行聚类时，K均值也有问题 ，这种情况下，离群点检测和删除有很大的帮助。
下面对初始质心的选择进行讨论：
当初始质心是随机的进行初始化的时候，K均值的每次运行将会产生不同的SSE,而且随机的选择初始质心结果可能很糟糕，可能只能得到局部的最优解，而无法得到全局的最优解。
多次运行，每次使用一组不同的随机初始质心，然后选择一个具有最小的SSE的簇集。该策略非常的简单，但是效果可能不是很好，这取决于数据集合寻找的簇的个数。
关于更多，参考《数据挖掘导论》
为了克服K-Means算法收敛于局部最小值的问题，提出了一种 二分K-均值(bisecting K-means)
将所有的点看成是一个簇
当簇小于数目k时
对于每一个簇
计算总误差
在给定的簇上进行K-均值聚类,k值为2 计算将该簇划分成两个簇后总误差
选择是的误差最小的那个簇进行划分
在原始的K-means算法中，每一次的划分所有的样本都要参与运算，如果数据量非常大的话，这个时间是非常高的，因此有了一种分批处理的改进算法。
使用Mini Batch（分批处理）的方法对数据点之间的距离进行计算。
Mini Batch的好处：不必使用所有的数据样本，而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。n 由于计算样本量少，所以会相应的减少运行时间n 但另一方面抽样也必然会带来准确度的下降。
聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集成为一个“簇”。通过这样的划分，每个簇可能对应于一些潜在的概念（也就是类别）；需说明的是，这些概念对聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇对应的概念语义由使用者来把握和命名。
聚类是无监督的学习算法，分类是有监督的学习算法。所谓有监督就是有已知标签的训练集（也就是说提前知道训练集里的数据属于哪个类别），机器学习算法在训练集上学习到相应的参数，构建模型，然后应用到测试集上。而聚类算法是没有标签的，聚类的时候，需要实现的目标只是把相似的东西聚到一起。
聚类的目的是把相似的样本聚到一起，而将不相似的样本分开，类似于“物以类聚”，很直观的想法是同一个簇中的相似度要尽可能高，而簇与簇之间的相似度要尽可能的低。
性能度量大概可分为两类： 一是外部指标， 二是内部指标 。
外部指标：将聚类结果和某个“参考模型”进行比较。
内部指标：不利用任何参考模型，直接考察聚类结果。
对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大
初学者会很容易就把K-Means和KNN搞混，其实两者的差别还是很大的。
K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。
当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。
优点：
简单， 易于理解和实现 ；收敛快，一般仅需5-10次迭代即可，高效
缺点：
1，对K值得选取把握不同对结果有很大的不同
2，对于初始点的选取敏感，不同的随机初始点得到的聚类结果可能完全不同
3，对于不是凸的数据集比较难收敛
4，对噪点过于敏感，因为算法是根据基于均值的
5，结果不一定是全局最优，只能保证局部最优
6，对球形簇的分组效果较好，对非球型簇、不同尺寸、不同密度的簇分组效果不好。
K-means算法简单理解，易于实现（局部最优），却会有对初始点、噪声点敏感等问题；还容易和监督学习的分类算法KNN混淆。
参考阅读：
1.《 深入理解K-Means聚类算法 》
2.《 K-Means 》
C. 直线k中值算法
不好意思忘了输出到文件，不知道你指的运行不了是不是这个意思，还有我没有自己找数据测试过，实在不能保证结果的正确性，下面是输出到文件的程序
#include <stdio.h>
struct res
{
int x,w,c;
};
FILE* fp;
int n,k;
int ans=2100000000;
struct res r[10];
void dfs(int depth,int prev,int cur)
{
int i,j;
if(depth==k)return;
for(i=prev+1;i<n;i++)
{
int temp=0,tempcur=cur;
tempcur+=r[i].c;
for(j=prev+1;j<i;j++)
{
if(depth==0||(depth!=0&&r[i].x+r[prev].x<r[j].x*2))tempcur+=(r[i].x-r[j].x)*r[j].w;
else
tempcur+=(r[j].x-r[prev].x)*r[j].w;
}
for(j=i+1;j<n;j++)
{
temp+=(r[j].x-r[i].x)*r[j].w;
}
if(tempcur+temp<ans)ans=tempcur+temp;
dfs(depth+1,i,tempcur);
}
}
int main()
{
int i;
fp=fopen("kml0.in","r");
fscanf(fp,"%d%d",&n,&k);
for(i=0;i<n;i++)fscanf(fp,"%d%d%d",&r[i].x,&r[i].w,&r[i].c);
fclose(fp);
dfs(0,-1,0);
fp=fopen("output0.out","w");
fprintf(fp,"%d",ans);
fclose(fp);
return(0);
}