模糊聚类问题的方法与算法

# 模糊聚类问题的方法与算法 ## 1. 确定隶属函数和中心 ### 1.1 隶属函数 在模糊聚类中，隶属函数的确定是关键步骤之一。首先，通过公式计算 $\lambda_r$： $\lambda_r = \sqrt[q]{\sum_{j = 1}^{k} \left(\frac{1}{d(c_j, a_r)}\right)^{\frac{1}{q - 1}}}^{q - 1}$ 将其代入相应公式可得到隶属函数 $u_{rs}(c)$： $u_{rs}(c) = \frac{1}{\sum_{j = 1}^{k} \left(\frac{d(c_s, a_r)}{d(c_j, a_r)}\right)^{\frac{1}{q - 1}}}, a_r \neq c_s$ 需要注意的是，当某些数据 $a_i$ 与中心 $c_j$ 重合时，上述函数未定义。此时，隶属函数 $u_{ij}$ 应定义为： $u_{ij}(c) = \begin{cases} \frac{1}{\sum_{s = 1}^{k} \left(\frac{d(c_j, a_i)}{d(c_s, a_i)}\right)^{\frac{1}{q - 1}}}, & \text{如果 } I_i = \varnothing \\ \frac{1}{|I_i|}, & \text{如果 } I_i \neq \varnothing \text{ 且 } j \in I_i \\ 0, & \text{如果 } I_i \neq \varnothing \text{ 且 } j \notin I_i \end{cases}$ 其中 $I_i = \{s : c_s = a_i\} \subseteq \{1, \ldots, k\}$。 ### 1.2 中心 为了找到中心 $c_1, \ldots, c_k$，需要使函数在满足一定条件下达到最小值。通过将拉格朗日函数的偏导数等于 0 来求解中心： $\frac{\partial J(c, U, \lambda)}{\partial c_j} = \sum_{i = 1}^{m} u_{ij}^q \frac{\partial d(c_j, a_i)}{\partial c_j} = 0$ 对于不同的距离函数，中心的计算方式不同： - **LS 距离函数**：当 $d(c_j, a_i) := \|c_j - a_i\|^2$ 时，可得 $c_j$ 的计算公式为： $c_j = \left(\sum_{i = 1}^{m} u_{ij}^q\right)^{-1} \sum_{i = 1}^{m} u_{ij}^q a_i, j = 1, \ldots, k$ - **$\ell_1$ 度量函数**：当 $d(x, a_i) := \|x - a_i\|_1$ 时，中心 $c_1, \ldots, c_k$ 是数据 $a_1, \ldots, a_m \in R^n$ 的加权中位数，权重为 $u_{ij}^q$： $c_j = \text{med}_{i = 1, \ldots, m}(u_{ij}^q, a_i), j = 1, \ldots, k$ 此外，搜索模糊化因子 $q$ 的最优值是一个复杂的过程，在应用研究中，最常用的 $q$ 值范围是 $[1.5, 2.5]$，后续示例和应用中使用 $q = 2$。 ## 2. 搜索具有球形簇的最优模糊划分 ### 2.1 模糊 c - 均值算法 模糊 c - 均值算法是搜索模糊局部最优划分最常用的算法，使用 LS 距离函数并生成球形簇。该算法可分为两个交替步骤： - **步骤 A**：给定有限子集 $A \subset R^n$ 和 $k$ 个不同点 $z_1, \ldots, z_k \in R^n$，根据上述隶属函数公式确定隶属矩阵 $U \in [0, 1]^{m \times k}$。 - **步骤 B**：给定隶属矩阵 $U \in [0, 1]^{m \times k}$，根据中心计算公式确定相应的簇中心 $c_1, \ldots, c_k \in R^n$，并计算目标函数值。然后更新 $z_j := c_j, j = 1, \ldots, k$。 该算法产生目标函数值的单调递减序列，迭代过程在满足以下条件之一时停止： - $\frac{\Phi_{j - 1} - \Phi_j}{\Phi_j} < \epsilon_{fcm}$ - $\|U^{(j)} - U^{(j - 1)}\| < \epsilon_{fcm}$ 以下是一个示例，选择 $k = 5$ 个点 $C_1 = (2, 2), C_2 = (3, 5), C_3 = (6, 7), C_4 = (7, 3), C_5 = (8, 8)$，在每个点附近生成 100 个随机点，使用模糊 c - 均值算法得到新的中心： $c_1^* = (1.76, 2.16), c_2^* = (3.06, 4.8), c_3^* = (6.08, 7.06), c_4^* = (7.05, 2.85), c_5^* = (8.31, 7.99)$ 算法使用的 CPU 时间为 6.39 s。同时计算了相关的统计量，如 $\sigma_j^{*2}$，并给出了混淆矩阵及其百分比结构，如下表所示： | Cluster | $\pi_1^*$ | $\pi_2^*$ | $\pi_3^*$ | $\pi_4^*$ | $\pi_5^*$ | $\sum$ | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | $\pi_1$ | 65.0 (67.1%) | 16.9 (17.5%) | 4.6 (4.8%) | 7.5 (7.7%) | 2.8 (2.9%) | 96.8 (100%) | | $\pi_2$ | 16.5 (15.6%) | 64.3 (60.8%) | 11.2 (10.6%) | 8.6 (8.1%) | 5.1 (4.9%) | 105.6 (100%) | | $\pi_3$ | 4.8 (4.8%) | 11.4 (11.3%) | 56.6 (56.2%) | 9.3 (9.2%) | 18.6 (18.4%) | 100.7 (100%) | | $\pi_4$ | 7.1 (7.4%) | 9.5 (9.9%) | 9.7 (10.2%) | 62.3 (65.1%) | 7.1 (7.4%) | 95.6 (100%) | | $\pi_5$ | 2.9 (2.9%) | 5.4 (5.3%) | 23.2 (22.9%) | 6.8 (6.7%) | 62.9 (62.1%) | 101.2 (100%) | | $\sum$ | 96.2 (97.7%) | 107.4 (104.9%) | 105.3 (104.7%) | 94.5 (97.0%) | 96.5 (95.8%) | 500 (100%) | ### 2.2 模糊增量聚类算法（FInc） 当最合适的簇数量事先未知时，可使用模糊增量聚类算法。该算法基于特定方法构建，通过一系列步骤搜索具有 2, 3, ... 个簇的最优划分，并使用不同的有效性指标来确定最合适的划分。 - **初始步骤**：选择初始中心 $\hat{c}_1 \in R^n$，例如数据集 $A$ 的均值。 - **后续