I came across a clustering algorithm, which uses the set builder notation to specify the clusters (or elements in the cluster). The algorithm is here.
The following is copied directly from the source, where the optimization function is this:
$$\mathit{E}(\mathbf{Z}) = \sum_{j=1}^k \frac{\mathbf{z}^⊤_j \mathbf{Az}_j}{f_j(\mathbf{Z})}$$
where:
$\mathbf{A} \in \mathbb{R}^{n×n}$ is the affinity matrix of n data points
$\mathbf{Z} = [\mathbf{z_1},···,\mathbf{z_k}] \in \mathcal{Z}, \mathcal{Z} = \{\mathbf{Z} \in \{0, 1\}^{n×k} | \mathbf{Z1} = \mathbf{1}\}$ is an assignment matrix, in which k is the number of clusters and 1 is the all-one vector
The optimization function and the affinity matrix $\mathbf{A}$ are logical, however, when you come to the notation of the clusters Z is where the problem lies. I'm not sure what the following notations mean:
- The equation for $\mathcal{Z}$ is based on the predicate $\mathbf{Z1} = \mathbf{1}$, what does that mean? And why do the clusters $\mathbf{Z}$ belong to $\mathcal{Z}$ while $\mathcal{Z}$ is constructed by $\mathbf{Z}$ that belong to the $\{0, 1\}^{n×k}$ set?
- The "all-one" vector is what? Presumably a row or column vectors of all 1s?
Thank you.
Best Answer
$\mathbf{Z}$ is an $n \times k$ matrix, and the first $\mathbf{1}$ is a $k \times 1$ matrix (column vector) of 1s (often written as $\mathbf{e}$). The second $\mathbf{1}$ is an $n \times 1$ matrix (column vector) of 1s, and $\mathbf{Z 1} = \mathbf{1}$ means $$\sum_{j=1}^k Z_{i,j} = 1$$ for $i \in \{1,\dots,n\}$. Because $Z_{i,j} \in \{0,1\}$, this implies that each row $i$ contains exactly one 1 and exactly $k-1$ 0s.