0
$\begingroup$

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:

  1. 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?
  2. The "all-one" vector is what? Presumably a row or column vectors of all 1s?

Thank you.

$\endgroup$

1 Answer 1

2
$\begingroup$

$\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.

$\endgroup$
2
  • $\begingroup$ Hmm I see, if $\mathbf{Z}$ is a $n \times k$ matrix, then are all components of $\mathbf{Z}$ i.e. $\mathbf{z_1},···,\mathbf{z_k}$ $n \times 1$ matrices? So $\mathbf{z_1}$ is $n \times 1$? $\endgroup$
    – simplename
    Commented Nov 27, 2020 at 5:33
  • $\begingroup$ Yes, those are $n\times 1$. $\endgroup$
    – RobPratt
    Commented Nov 27, 2020 at 14:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .