<p>You can use essentially any centroid-based clustering algorithm to define a notion of "coherence" or "purity" of a cluster. Let's say you've chosen some particular metric <span class="math-container">$||\cdot||$</span> on <span class="math-container">$\mathbb{R}^n$</span> (I'm using norm notation but any metric will do). Using your notation, <span class="math-container">$S_i$</span> is the <span class="math-container">$i$</span>th "cluster". For each <span class="math-container">$S_i$</span>, find the* point <span class="math-container">$c_i\in\mathbb{R}^n$</span> that minimizes
<span class="math-container">$$ F(c):=\sum_{x\in S_i}||x-c||\qquad(*)$$</span>
over all <span class="math-container">$c\in\mathbb{R}^n$</span>. Let <span class="math-container">$F(c_i)$</span> be the purity score of <span class="math-container">$S_i$</span>; it might actually be better to consider the normalized version <span class="math-container">$F(c_i)/|S_i|$</span>. Smaller values means more homogeneity or "purity".</p>

<p>*How to do this computationally? Try (sub)gradient descent. If the minimum is not unique then break ties arbitrarily.</p>

CC BY-SA 4.0
2019-10-22T20:09:42.820Z
Thanks for your answer! If I chose the euclidean metric, c_i would just be the centroid of the set, right? And the normalized version would be the average distance of every point to this centroid. Although this certainly makes sense, I was looking for sth more sophisticated that is (more) independent of absolute distance and more about the overall structure of the point cloud.
moi
CC BY-SA 4.0
2019-10-22T20:16:36.237Z
For a true centroid you'd need to write $||x-c||^2$ in (*); as stated it's more like a generalized median.
Aryeh
CC BY-SA 4.0
2019-10-23T09:07:29.803Z
I see. Is there a reason why would I approximate this "generalized median" using gradient descend if I could also used the centroid that I can calculate in closed form?
moi
CC BY-SA 4.0
2019-10-23T09:49:38.533Z
Not at all -- feel free to use the centroid *IF* you believe that the Euclidean metric is the appropriate one for your problem.
Aryeh
CC BY-SA 4.0
2019-10-22T19:11:30.700Z
2019-10-22T19:11:30.700Z
Aryeh
<p><strong>Background:</strong> I have multiple point clouds (sets of objects) <span class="math-container">$\{S_i\}_{i\in\mathbb{N}}$</span> of variable size and "purity" (meaning that some sets contain very similar objects, some show a high diversity; some sets are large, some are small). Each object is characterized by a <span class="math-container">$n$</span>-dimensional continuous feature vector <span class="math-container">$v_j \in \mathbb{R}^n$</span>, each set can therefore be seen as a matrix <span class="math-container">$M_i \in \mathbb{R}^{|S_i| \times n}$</span>.</p>

<p>I want to classify these point clouds using a binary classifier into "pure" and "diverse".</p>

<p><strong>Idea:</strong> I was thinking about covariance. This way every point cloud is represented by its <span class="math-container">$n \times n$</span> covariance matrix.</p>

<p><strong>Question:</strong> What other features can I use to characterize the individual point clouds? How else can I transform these matrices of different shape to representations of fixed length representations that can be passed on to a classifier?</p>

CC BY-SA 4.0
2019-10-22T19:02:16.507Z
Not sure why this is getting downvoted -- looks like a valid question to me.
Aryeh
<machine-learning>
Characterize a point cloud
moi
# Characterize a point cloud

(Asked by: username_0 on 2019-10-22)

**Background:** I have multiple point clouds (sets of objects) $\{S\_i\}\_{i\in\mathbb{N}}$ of variable size and "purity" (meaning that some sets contain very similar objects, some show a high diversity; some sets are large, some are small). Each object is characterized by a $n$-dimensional continuous feature vector $v\_j \in \mathbb{R}^n$, each set can therefore be seen as a matrix $M\_i \in \mathbb{R}^{|S\_i| \times n}$.

I want to classify these point clouds using a binary classifier into "pure" and "diverse".

**Idea:** I was thinking about covariance. This way every point cloud is represented by its $n \times n$ covariance matrix.

**Question:** What other features can I use to characterize the individual point clouds? How else can I transform these matrices of different shape to representations of fixed length representations that can be passed on to a classifier?

**Tags:** machine-learning

> **Comments:**
> **username_1**: Not sure why this is getting downvoted -- looks like a valid question to me.  

---

## 1 answers

### Answer by username_1 on 2019-10-22. Score: 1

You can use essentially any centroid-based clustering algorithm to define a notion of "coherence" or "purity" of a cluster. Let's say you've chosen some particular metric $||\cdot||$ on $\mathbb{R}^n$ (I'm using norm notation but any metric will do). Using your notation, $S\_i$ is the $i$th "cluster". For each $S\_i$, find the\* point $c\_i\in\mathbb{R}^n$ that minimizes
$$ F(c):=\sum\_{x\in S\_i}||x-c||\qquad(\*)$$
over all $c\in\mathbb{R}^n$. Let $F(c\_i)$ be the purity score of $S\_i$; it might actually be better to consider the normalized version $F(c\_i)/|S\_i|$. Smaller values means more homogeneity or "purity".

\*How to do this computationally? Try (sub)gradient descent. If the minimum is not unique then break ties arbitrarily.

> **Comments:**
> **username_0**: Thanks for your answer! If I chose the euclidean metric, c_i would just be the centroid of the set, right? And the normalized version would be the average distance of every point to this centroid. Although this certainly makes sense, I was looking for sth more sophisticated that is (more) independent of absolute distance and more about the overall structure of the point cloud.  
> **username_1**: For a true centroid you'd need to write $||x-c||^2$ in (*); as stated it's more like a generalized median.  
> **username_0**: I see. Is there a reason why would I approximate this "generalized median" using gradient descend if I could also used the centroid that I can calculate in closed form?  
> **username_1**: Not at all -- feel free to use the centroid *IF* you believe that the Euclidean metric is the appropriate one for your problem.  

---

