[논문 리뷰] Clustering problem with 0-1 Quadratic programming

aliceshard·2023년 3월 2일

Intro

K-means, ISODATA, SVM, SOM, 베이지안 방법 등 다양한 클러스터링 방법론이 존재하지만, 대부분 선제 조건으로 클러스터 개수 $k$ 를 요구한다.
이러한 $k$ 를 정하는 것은 클러스터링에서 자주 발생하는 문제.
대신 여기서는 linear constraints를 갖는 bivalent quadratic optimization problem으로 클러스터링 문제를 대치시켜 해결법을 제시한다.
다음 세 가지 기준을 사용하는 모델이 될 것이다.

Number of centers
Density data
Dispersion of the chosen centers

성능을 위해서, 이 문제를 해결하는데는 Genetic Algorithm이 사용될 것이다.
Genetic algorithm의 고전적인 mutation, crossover 연산이 제시가 될 것이며, selection function은 objective function 그 자체이다.

The 0-1 mathematical programming model for the unsupervised classification problem

데이터셋을 $D=\{d_{1},...,d_{n}\}\subset\mathbb{R}^{m}$ 이라 할 때, 이 알고리즘은 데이터의 적절한 중심점들의 집합 $S$ 를 찾는 것을 목표로 한다.

The sample density

각 데이터 포인트 $d_i$ 의 sample density는 다음과 같이 정의된다.
$\alpha_i = |A_i|/n$
집합 $A_i$ 는 데이터 포인트 하나 $d_i$ 를 고정한 상태로, 그 외의 모든 점들 $d_j$ 를 훑으면서 다음과 같은 조건을 만족하는지 계산해 저장하는 집합이다.

$A_i = \{{d_j} / \|d_i-d_j\| \leq \sigma\}$
- 요컨대, 만약 데이터 포인트 $d_i$ 가 혼자 동떨어진 점이라면, 매우 작은 sample density를 가질 것이다.
- 추측컨데, 여기서 $|\cdot|$ 은 hamming weight와 비슷한 방식으로 작동한다.
문제로 돌아와서, 우리가 지금 풀고 있는 UCP(Unsupervised classification problem)은 각 데이터 군집의 중심점들의 집합 $S$ 를 찾는 알고리즘이라고 볼 수도 있다.
- $S$ 는 매우 큰 분산을 갖고 있어야 한다.
  (군집끼리는 가능한 한 멀어져야 한다)
- $|density(S)-density(D)|$ 는 최소화 되어야 한다.
  (같은 군집 내에 속한 원소들의 밀도는 중심점의 밀도와 비교했을 때 최소화 되어야 한다)
- 중심 집합 $S$ 의 크기는 가급적이면 작아야 한다.

The Decision Variable

binary variable $x_i$ 를 정의할 것이다. $x_i$ 는 데이터 포인트 $d_i$ 가 집합 $S$ 에 포함된다면 $x_i=1$ 이 될 것이고, 그렇지 않다면 0이 될 것이다.
또한 binary vector $x$ 는 다음과 같이 정의된다. $x=(x_1, ... , x_n)^t$

The Decision Dispersion

다음과 같이 $\beta$ 를 두 지점 사이의 거리라고 정의하자. $\beta_{ij} = \|d_i - d_j\|$
따라서 단순히 모든 점들에 대해서 거리를 고려한다면, 다음과 같이 deviation이 완성될 것이다. $x_i \sum^n_{j=1} \beta_{ij} x_j$
여기서 영감을 얻어, 어떤 임의의 vector decision $x$ 에 대해서 다음과 같이 dispersion을 정의할 수 있을 것이다. $f_1(x) = \sum^n_{i,j=1} x_i\beta_{ij}x_j$

사실 여기서 여기서 dispersion을 나타내는 metric은 반드시 $f_1(x)$ 만 있는 것이 아니다. Interquartile range나 standard deviation 같은 다른 것도 사용이 가능하다. 하지만 여기서는 위와 같은 dispersion을 사용했는데, 다음의 이유에서이다.

Outlier 데이터에 대해서 덜 민감하게 변화한다.

모든 데이터를 세세하게 다 나타낼 수 있다 (?)
(원문: Represent fiddly all data)

구현이 쉽다.

The Decision Density

정해진 데이터 중심점들에 대해서 총 밀도(Total density)를 표현하는 방법으로써 다음과 같이 쓰인다. $f_2(x) = \sum_{i=1}^n \alpha_i x_i$
$\alpha_i$ 는 데이터 포인트 $d_i$ 의 sample density이다.

The Centers set size

단순히 집합 $S$ 에서 포함된 중심점들에 대해서 벡터 $x$ 를 산출해냈을 때, 원소가 1인 값이 몇개나 있는가? 로 산출된다.
$f_3(x)=\sum^n_{i=1} x_i %%$
이상 위에서 정의된 모든 term들을 종합해서, 다음과 같이 최적화 문제가 완성된다.
$Maximize \sum_{i,j=1}^n x_i \beta_{ij} x_j - \lambda \sum_{i=1}^n x_i$ $s.t.$ $\sum_{i=1}^n \alpha_i x_i \geq td$ $x_i \in \{0,1\}, \quad i=1,...,n$

$\lambda$ 는 패널티항으로, dispersion과 number of centers term을 서로 벌충시키기 위해 필요하다.

Genetic algorithm for Solving the Proposed Model

주어진 문제가 NP-complete에 속하므로, genetic algorithm을 최적화 도구로 사용할 예정이다. 따라서 Coding, fitness function, selection mechanisms, crossover, mutation을 새롭게 정의하고 적용할 것이다.

Coding

앞서 정의한 binary vector $x$ 를 그대로 코딩 스킴으로 사용한다.

Fitness function

'얼마나 목표한 값에 잘 맞나?' 를 나타내기 위한 함수이다. 다름 아닌 목표 함수를 그대로 들고와서 설정해도 크게 문제가 없다. $f(x) = \sum^n_{i=1} \sum^n_{j=1} x_i \beta_{ij} x_j - \lambda \sum^n_{i=1} x_i$