Flame 클러스터링

이 기사의 주요 기고자는 그 주제와 밀접한 관련이 있는 것으로 보인다.위키피디아의 콘텐츠 정책, 특히 중립적인 관점을 준수하기 위해 정리가 필요할 수 있다.자세한 내용은 대화 페이지에서 논의하십시오. (2010년 8월)(이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

FLAME(Fuzzy clustering by Local Ansimation of MEmberships)는 데이터 클러스터링 알고리즘으로, 데이터 집합의 밀도 부분에 있는 클러스터를 정의하고 개체 간의 근린 관계를 기반으로만 클러스터 할당을 수행한다.이 알고리즘의 주요 특징은 피쳐스페이스에 있는 인접 오브젝트들 사이의 근린관계를 퍼지 멤버쉽 공간에서 인접 오브젝트의 멤버십을 구속하는데 사용한다는 것이다.

FLAME 알고리즘 설명

FLAME 알고리즘은 주로 세 단계로 나뉜다.

1. 데이터 집합에서 구조물 정보 추출:
   1. KNN(Korean Neighborhood Neighbors)에 각 개체를 연결하는 인접 그래프를 생성하십시오.
   2. KNN에 대한 각 물체의 대용량을 바탕으로 각 물체의 밀도를 추정한다.
   3. 객체는 3가지 유형으로 분류된다.
      1. CSO(Cluster Supporting Object): 모든 인접 항목보다 밀도가 높은 개체
      2. 군집 특이치: 모든 인접 항목보다 밀도가 낮고 사전 정의된 임계값보다 낮은 개체
      3. 나머지
2. 퍼지 멤버십의 로컬/근접 근사치:
   1. 퍼지 구성원 자격 초기화:
      1. 각 CSO는 하나의 클러스터를 나타내기 위해 고정 및 전체 멤버십을 자신에게 할당한다.
      2. 모든 특이치에는 특이치 그룹에 고정 및 전체 멤버십이 할당된다.
      3. 나머지는 모든 클러스터와 특이치 그룹에 동일한 멤버십으로 할당된다.
   2. 그런 다음 모든 타입 3 객체의 퍼지 멤버십은 가장 가까운 이웃의 퍼지 멤버십의 선형 조합에 의해 업데이트되는 퍼지 멤버십의 로컬/근접적인 근사치라는 수렴 반복 절차에 의해 업데이트된다.
3. 퍼지 멤버십에서 클러스터 구성(가능한 두 가지 방법):
   1. 가장 높은 구성원을 가진 클러스터에 각 개체를 할당하기 위한 일대일 개체 클러스터 할당
   2. 임계값보다 높은 구성원 자격을 가진 클러스터에 각 개체를 할당하는 일대다 개체-클러스터 할당.

Flame의 최적화 문제

퍼지 멤버십의 로컬/근접 근사치는 다음과 같이 정의된 로컬/근접 근사 오차(LAE/NAE)를 최소화하기 위한 절차다.

${\displaystyle E(\{{\boldsymbol {p}}\})=\sum _{{\boldsymbol {x}}\in {\boldsymbol {X}}}{\bigg \ }{\boldsymbol {p(x)}}-\sum _{\boldsymbol {y\in {\mathcal {N}}(x)}}w_{\boldsymbol {xy}}{\boldsymbol {p(y)}}{\bigg \ }^{2}}$

where ${\displaystyle {\boldsymbol {X}}}$ is the set of all type 3 objects, ${\displaystyle {\boldsymbol {p(x)}}}$ is the fuzzy membership vector of object ${\displaystyle {\boldsymbol {x}}}$, ${\displaystyle {\mathcal {N}}(x)}$ is the set of nearest neighbors of ${\displaystyle {\bolds$$ymbol {x}}}$, and ${\displaystyle w_{\boldsymbol {xy}}}$ with ${\displaystyle \sum _{\boldsymbol {y\in {\mathcal {N}}(x)}}w_{\boldsymbol {xy}}=1}$ are the coefficients reflecting the relative proximities of the nearest neighbors.

NEE는 값이 0인 NE의 고유한 글로벌 최소치인 고유한 솔루션으로 다음과 같은 선형 방정식을 해결함으로써 최소화할 수 있다.

${\displaystyle p_{k}({\boldsymbol {x}})-\sum _{\boldsymbol {y\in {\mathcal {N}}(x)}}w_{\boldsymbol {xy}}p_{k}({\boldsymbol {y}})=0,\quad \forall {{\boldsymbol {x}}\in {\boldsymbol {X}}},\quad k=1,...,M}$

여기서 $M{\displaystyle }$ ${\displaystyle M}$은 CSO 수에 1을 더한 수입니다(특이치 그룹의 경우).다음과 같은 반복적 절차를 사용하여 이러한 선형 방정식을 해결할 수 있다.

${\displaystyle {{\boldsymbol {p}}^{t+1}({\boldsymbol {x}})}=\sum _{\boldsymbol {y\in {\mathcal {N}}(x)}}w_{\boldsymbol {xy}}{{\boldsymbol {p}}^{t}({\boldsymbol {y}})}}$

2차원 테스트 데이터 세트에 대한 간단한 그림

참고 항목

• 데이터 클러스터링
• 퍼지 군집화

외부 링크

• BMC 생물정보학(2007):FLAME, DNA 마이크로어레이 데이터 분석을 위한 새로운 퍼지 클러스터링 방법
• GoogleCode의 FreeBSD 유사 라이센스에 따라 릴리스된 C의 Flame 소스 코드