在聚类过程中，当考虑样本\(\vec x_i\)时，计算它与其它各样本间的近邻函数值，如果
\[
\alpha_{ik} = min_j \lfloor \alpha_{ij} \rfloor
\]
则把\(\vec x_i\)和\(\vec x_k\)连接起来，并有连接损失\(\alpha_{ik}\)
若把\(\vec x_i\)与\(\vec x_j\)不实际连接，则不存在连接损失，即
\[
\alpha_{ij} \triangleq 0
\]
近邻聚类准则函数
在定义了两样本间的连接损失之后，还要区分出类内连接损失和类间连接损失。
设共有c类：\(w(p = 1,2,...,c)\)，总的类内连接损失定义为:
\[
L_w = \sum^c_{p=1} \sum_{\vec x_i \in w_p \ \\ \vec x_j \in w_p} \lfloor \alpha_{ij} \rfloor
\]
记\(w_j\)类的类内最大近邻函数值：
\[
\alpha_{p max} = max_{\vec x_i \in w_p \ \\ \vec x_j \in w_p} \lfloor \alpha_{ij} \rfloor
\]
设聚类\(w_p\)和\(w_q (p,q=1,2,3,....,c;p \neq q)\)的样本之间的最小近邻函数值为\(\gamma_{pq}\)，即
\[
\gamma_{pq} = min_{\vec x_i \in w_p \ \\ \vec x_j \in w_q} \lfloor a_{ij} \rfloor
\]
设\(\gamma_{pk}\)为聚类\(w_p\)与其它各聚类\(w_q\)的最小近邻函数值的最小值，即
\[
\gamma_{pk} = min_{q \ \\ q \neq p} \lfloor \gamma_{pq} \rfloor
\]
上式表明，除\(w_p\)类内样本外，只有\(w_k\)中的某一个样本与\(w_p\)中某一个样本最近邻，近邻函数值为\(\gamma_{pk}\)
\(w_p\)类与\(w_k\)类的类间最小连接损失有如下四种情况
\(\Beta_p = (\alpha_{p\ max} - \gamma_{pk}) + (\alpha_{k \ max} - \gamma_{pk})\), 若$\gamma_{pk} > \alpha_{p max} and \gamma_{pk} > \alpha_{k max} $
该情况：类内最大近邻函数值小于类间最小近邻值，说明聚类是合理的，这种情况不应付出代价，\(\Beta_p\) 可赋予负值，即损失函数为负数
\(\Beta_p = \alpha_{p\ max} - \gamma_{pk}\)，若\(\gamma_{pk} \leq \alpha_{p\ max} \ and\ \alpha_{pk} > \alpha_{k\ max}\)
该情况下：\(w_p\)类的类内最大近邻函数值大于类间最小近邻值，说明这两类合并应付出代价，\(\Beta_p\)赋予一个正值，即损失为\(\alpha_{p\ max} - \gamma_{pk}\)
\(\Beta_p = \alpha_{k\ max} - \gamma_{pk}\)，若\(\gamma_{pk} > \alpha_{p\ max} \ and\ \alpha_{pk} \leq \alpha_{k\ max}\)
该情况下：\(w_p\)类的类内最大近邻函数值大于类间最小近邻值，说明这两类合并也应付出代价，\(\Beta_p\)赋予一个正值，即损失为\(\alpha_{k\ max} - \gamma_{pk}\)
\(\Beta_p = \alpha_{p\ max} + (\alpha_{k \ max} - \gamma_{pk})\), 若$\gamma_{pk} \leq \alpha_{p max} and \gamma_{pk} \leq \alpha_{k max} $
该情况：\(w_p\)和\(w_k\)类内的类内最大近邻函数值都大于类间最小近邻值，说明这两类合并应付出的代价更大，\(\Beta_p\)赋予连接损失为\(\alpha_{p\ max} + (\alpha_{k \ max} - \gamma_{pk})\)
然后，我们可以定义总的类间损失：\(L_B = \sum_{p=I}^c \Beta_p\)。
聚类的目标是使各\(\gamma_{pk}\)尽可能地大，使各\(\alpha_{p\ max}\)尽可能地小，因而构造聚类的准则函数为
\[
J_L = L_W + L_B \Rightarrow min
\]
近邻函数法算法步骤
(1) 对于给定的待分类样集$x = \({\)\vec x_1, \vec x_2, ..., \vec x_N\(}，计算距离矩阵D，D的阵元为：\)D_{ij} = d(\vec x_i, \vec x_j) (i,j=1,2,...,N)\(，\)d(\vec x_i, \vec x_j)\(表示样本\)\vec x_i\(和\)\vec x_j\(间的距离。 (2) 利用矩阵D，计算近邻矩阵M，其元素\)M_{ij}\(为样本\)\vec x_i\(对\)\vec x_j\(的近邻系数 (3) 生成近邻函数矩阵L,其阵元为\)L_{ij}=M_{ij}+M_{ji}-2\(，置矩阵L的主对角线上阵元\)L_{ii}=2N\(，如果\)\vec x_i\(和\)\vec x_j\(有连接，则\)L_{ij}\(给出它们非零近邻函数值，即连接损失 (4) 搜索矩阵L，将每个点与和它有最小近邻函数值的点连接起来，形成初始聚类 (5) 对于(4)所形成的聚类，计算\)\gamma_{pk},\alpha_{pw},\alpha_{kw}\(。若\)\gamma_{pk}\(小于或等于\)\alpha_{pw}\(或\)\alpha_{kw}\(，则合并\)w_k\(和\)w_p$，它们的样本间建立连接关系，转至(5)，否则结束
上述迭代过程，最终将使准则函数\(J_L\)达到极小值。
注：对于链状的模式分布，合并后的类内最大连接损失不应重新计算，而是取\(\alpha_1\ max, \alpha_2\ max, \gamma_{12}\)的最大值