聚类分析(数据库)

时间：2022-12-31 06:30:01 | 来源：信息时代

时间：2022-12-31 06:30:01 来源：信息时代

    聚类分析 : 根据最大化类内的相似性、最小化类间的相似性的原则将数据对象分组,所形成的每个分组称为簇,是一个数据对象类,用显式或隐式的方法描述它们。
给定一个数据集D,D={X₁,X₂,…,X_i,…,X_n},其中,X_i(1≤i≤n)是D中的一个数据对象,由d个属性值组成。X_i＝(x_i1,x_i2,…,x_ij,…,x_id),其中x_ij表示对象X_i中的属性,d是属性个数(或对象空间的维数)。
簇(cluster):数据集D分成k个簇{C₁,C₂,…,C_i,…,C_k}(1<=i<=k),每个簇C_i是相似对象的集合。相似对象在同一簇中,相异对象在不同簇中。C_i是D的子集,要求满足如下条件:
C₁∪C₂∪…∪C_k＝D, 且C_i∩C_j＝ф(i≠j)。
当有重叠聚类时, 允许C_i∩C_j≠ф(i≠j)。
簇C_i的特征由簇的质心和半径描述:
(1)簇的质心(centroid):是簇的中间值(middle),即对象的平均值,但并不一定是簇中的实际点。
令n_i表示簇C_i中对象的数量,m_i表示对应对象的均值,则簇C_i的质心centroid由下式计算得出:

(2)簇的半径(radius): 是簇中任意一点到质心之间距离的均方差的平方根(average mean squared distance),如下式:

聚类(clustering): 根据数据对象间的相似程度将数据集D划分成k簇: {C₁,C₂,…,C_k},使得每个簇中的数据对象之间尽可能的相似,而与其他簇中的数据对象尽可能的不相似(即相似对象在同一簇中,相异对象在不同簇中)的过程称为聚类。当无重叠聚类时,要求满足条件∪_i=1^kC_i＝D且C_i∩C_j=ф(i≠j); 当有重叠聚类时, 允许C_i∩C_j≠ф(i≠j)。
同一个簇中的对象比来自不同簇的对象更为相似的判断问题主要涉及以下两个子问题:
1. 如何度量对象之间的相似性
相似度(或相异度): 衡量两个对象之间的相似(或差异)程度。它是定义一个簇的基础,影响聚类分析过程的质量。对象间的相似度(或相异度)的量化由相似性函数或距离函数来实现。两个对象间依据距离函数计算出的值越大,则表示它们之间的相似性越小(差别越大),而相似性函数则相反。相似性函数和距离函数之间可以相互转换。设f是一个距离函数,值域在[0,1]之间,0表示两个对象相等,而1表示两个对象完全不同,其他数值则表示介于中间。它对应的相似性函数可以是: 1-f(·)或者1/(1+f(·))。在很多应用中需要f是一个度量(metric),满足以下性质:
非负性:对数据集D中的对象X_i和X_j,有f(X_i,X_j)≥0,当且仅当X_i和X_j的d个属性值对应相等时,f(X_i,X_j)＝0。
对称性:对数据集D中的对象X_i和X_j,有f(X_i,X_j)＝f(X_j,X_i)。
三角不等式: 即对数据集D中的对象X_i,X_j,X_k,有f(X_i,X_j)≤f(X_i,X_k)+f(X_k,X_j)。
一个函数满足三角不等式的优点是能够提高搜索效率。例如设有对象X₁,X₂,X₃,和满足三角不等式的距离函数f,如果已经知道f(X₁,X₂₎+f(X₂,X₃₎小于等于某个数值k,则有f(X₁,X₃₎≤f(X₁,X₂₎+f(X₂,X₃₎≤k,故可以在不计算X₁,X₃之间距离值的情况下直接推断f(X₁,X₃₎小于k。因为f(S₂,S₃₎可以预先计算好,所以搜索算法可依赖中间节点X₂缩小搜索的空间。
对于相似度对称性和非负性通常成立,但通常没有与三角不等式对应的一般性质。有时相似度也可以容易地将变换成一种度量距离,如Jaccard系数。
2. 如何衡量对数据集聚类的好坏
评价聚类过程质量的另一个标准是簇间距离度量标准。常用于簇C_i和C_j间的距离度量标准是:
(1)最小距离: D_min(C_i,C_j)＝min|X_i-X_j|,其中X_i∈C_i和X_j∈C_j。
(2)最大距离:D_max(C_i,C_j)＝max|X_i-X_j|,其中X_i∈C_i和X_j∈C_j。
(3)中间距离:D_mean(C_i,C_j)＝max|m_i-m_j|,其中m_i和m_j是C_i和C_j的质心。
(4)平均距离:D_avg(C_i,C_j)＝1/(n_in_j)∑∑|X_i-X_j|,
其中X_i∈C_i和X_j∈C_j,且n_i和n_j分别是簇C_i和C_j的对象数目。
聚类分析过程包括以下几个步骤:
步骤1: 收集数据对象。
步骤2: 属性选择从原始属性中选取用于聚类的更有效的属性子集,属性抽取利用对输入属性的一次或多次转换产生新的更显著的属性。
步骤3: 计算相似度。
步骤4: 确定目标划分的簇的数目或聚类划分的某个终止条件。由聚类算法实现。
步骤5: 实施聚类分析,产生结果。
主要的聚类算法有基于划分的方法(partitioning method)、基于层次的方法(hierarchical method)、基于密度的方法(density-based method)、基于网格的方法(grid-based method)以及基于模型的方法(model-based method)等。
评价聚类算法的聚类分析能力的标准有: ①能够适用于大数据量; ②能够处理不同类型数据; ③能够发现任意形状的簇; ④能够处理高维数据; ⑤具有处理噪声的能力: ⑥聚类结果具有可解释性、可使用性等。