Graph-based clustering

cut problem

N-cut问题（Normalized Cut，归一化割）和R-cut问题（Ratio Cut，比例割）是图论中的两种常用划分方法，常用于图像分割、聚类、社交网络分析等任务。它们的目标是通过切割图中的边，将图划分成两个或多个子集。

1. N-cut问题（归一化割）

N-cut问题是一种图割问题，它考虑了割边的权重和每个子集的权重，并通过归一化的方式优化割的结果。归一化割的定义如下：

给定一个无向加权图 $G=(V,E)$，其中 $V$ 是顶点集合，$E$ 是边集合。我们希望将图分割成两个子集 $A$ 和 $B$ ，最小化以下归一化的割代价：

$$\text{N-cut}(A,B)=\frac{\text{cut}(A,B)}{\text{assoc}(A,V)}+\frac{\text{cut}(A,B)}{\text{assoc}(B,V)}$$

• $\text{cut}(A,B)$ 表示割掉的边的总权重，即从集合 $A$ 到集合 $B$ 的边的权重之和。
• $\text{assoc}(A,V)$ 表示集合 $A$ 与整个图的所有顶点之间的连接强度，即与 $A$ 相关的边的权重总和。

归一化割的目标是最小化这个函数，使得两个子集内部的连接尽量强，而两个子集之间的连接尽量弱。

N-cut的优势在于，它通过归一化避免了不平衡的划分问题。例如，简单的最小割算法倾向于将较小的子集分离出来，而N-cut通过考虑子集的关联性避免这种情况。

2. R-cut问题（比例割）

R-cut（Ratio Cut，比例割）也是一种图割方法，其目标是最小化割边与子集顶点数量的比例。比例割的定义如下：

$$\text{R-cut}(A,B)=\frac{\text{cut}(A,B)}{|A|}+\frac{\text{cut}(A,B)}{|B|}$$

• $\text{cut}(A,B)$ 同样表示割边的总权重。
• $|A|$ 和 $|B|$ 是子集 $A$ 和 $B$ 中顶点的数量。

R-cut的目标是最小化割边与子集大小的比值，避免过度割分或不均匀分割。

区别

• N-cut 归一化了每个子集的关联强度，使得分割的子集在结构上具有更均匀的内部关联性。
• R-cut 则关注割边和子集大小的比例，适合处理一些相对简单的图划分任务。

在图像分割、聚类和社交网络分析等应用中，N-cut因其处理不平衡划分问题的能力，通常更常用。