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)为簇
[对于数值型属性:difp_i,q_i)=|p_i-q_i|\
difp_i,C)=|p_i,C_i|\
difC,D)=|C_i,D_i|\
对于非数值型属性:difp_i,q_i)=[p_i!=q_i]\
difp,C)=1-p_i在C中的频率)\
difC,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)}
]
越大越好