k-means聚类算法
在数据集中选择(k)个对象作为初始簇中心.
对于数据集中的每个对象,计算该对象(P)和(k)个簇中心的距离,将(P)指派到与其距离最短的簇.
将每个对象都重新指派之后,计算每个簇中对象的均值,作为新簇的中心
如果簇中心不发生变化,那么结束,否则重复2,3
k-summary算法
重新定义了k-means算法中的距离
摘要信息CSI
假设有属性列(A),B,那么摘要信息格式为
某个簇的属性列(A)取值有(a_1,a_2..a_n),属性列(B)取值有(b_1,b_2..b_n),
[{a_1:(a_1的频数),…a_n:(a_n的频数);b_1:(b_1的频数),…b_n:(b_n的频数);}
]
差异程度
(p,q)为样本,(C,D)为簇
[对于数值型属性:dif(p_i,q_i)=|p_i-q_i|\
dif(p_i,C)=|p_i,C_i|\
dif(C,D)=|C_i,D_i|\
对于非数值型属性:dif(p_i,q_i)=[p_i!=q_i]\
dif(p,C)=1-(p_i在C中的频率)\
dif(C,D)=1-sum_{每一个属性列}frac{sum相同取值的样本数相乘}{样本数相乘}\
]
距离
[d = sum每一个属性列的差异程度
]
一趟聚类算法
使用k-summary的距离定义.
读取第一条记录作为簇(C_1)的中心
读取后面的记录(X),找到与当前记录(X)距离最小的簇(C_x)
如果距离小于阈值,那么(X)指派到(C_x),否则建立一个新簇
更新簇的中心
直到读完所有记录
CH指标
[traceB=sum_{j=1}^{k}n_j*||z_j-z||^2(每个簇中心到整个数据集中心的距离*簇的大小的和)\
traceW=sum_{j=1}^{k}sum_{x_iin z_j}||x_i-z_j||^2(每个簇中的每个元素到簇中心的距离的和)\
V_{CH}=frac{traceB/(k-1)}{traceW/(N-k)}
]
越大越好