편집
552
번
히트 클러스터링: 두 판 사이의 차이
둘러보기로 이동
검색으로 이동
편집 요약 없음
편집 요약 없음 |
편집 요약 없음 |
||
| 7번째 줄: | 7번째 줄: | ||
==== 거리 기준 ==== | ==== 거리 기준 ==== | ||
인접한 히트를 찾을 때, 어느정도로 인접한 픽셀까지 하나의 클러스터로 볼 수 있는지에 대한 이야기가 있습니다. 픽셀 검출기에서, 떨어진 거리 없이 인접해야만 하나의 클러스터로 볼 수 있도록 할 수 있지만, 검출기와 그입자, 그리고 어떤 것까지 보느냐에 따라서 어떤 거리를 활용할 지 계산할 필요가 있습니다. | |||
* <math>L^2</math> 거리 (Euclidean Distance) | |||
** <math>D_{L^2} = \sqrt{\sum_i{\left(V_i - W_i \right)^2}}</math> | |||
** 일반적인 경우로 많이 활용됩니다. | |||
** 제곱근 연산이 연산 시간을 일정 부분 차지할 수 있으므로, 거리보다는 '''거리의 제곱값으로 기준을 정하면''' 제곱근에 의한 연산을 하지 않을 수 있습니다. | |||
* <math>L^1</math> 거리 (Manhattan-Taxicab Distance) | * <math>L^1</math> 거리 (Manhattan-Taxicab Distance) | ||
** <math>D_{L^1} = \left| \sum_i{\left(V_i - W_i \right)^2} \right|</math> | ** <math>D_{L^1} = \left| \sum_i{\left(V_i - W_i \right)^2} \right|</math> | ||
** <math>D=1</math> (완전히 인접한 경우) 만 취득하고자 할 때 활용합니다. <math>L^2</math>거리의 경우 한번의 연산이 더 들어가기 때문에, 최대한 연산 횟수를 줄이려는 경우에 활용합니다. | |||
* | * Geodesics (Simple form) | ||
** <math>D_{L^2} = \ | ** <math>D_{L^2}^2 = \sum_{i,j}\eta_{ij} \left(V_i-W_j\right)^2 , \eta_{ij} = \left\lbrace \begin{align} i=j=1 :& -1 \\ i=j>1 : & ~~~1 \\ \mathrm{Otherwise} : & ~~~0 \end{align} \right.</math> | ||
** 측정이 연속적으로 일어나고, 시간창(Time Window)에 비해 신호가 사라지는 속도가 비교적 빠르지 않은 경우 이전 시간창에 있던 신호의 꼬리가 다음 시간창에 측정될 수 있습니다. 이 경우, 다음 시간창에 있는 히트도 이전 시간창과 함께 클러스터링 해야하는데, 이 때 geodesic 의해 시간거리를 고려하여 활용할 수 있습니다. | |||
==== 알고리즘 ==== | ==== 알고리즘 ==== | ||
| 21번째 줄: | 24번째 줄: | ||
* Naive: <math>O\left( n^2 \right)</math> | * Naive: <math>O\left( n^2 \right)</math> | ||
** 모든 픽셀에 대해 서로간의 거리를 측정하여 일정 거리 이하의 픽셀만 취하여 클러스터로 취급합니다. | |||
* Barnes Hut (Quad-Tree): <math>O\left( n \log n \right)</math> | * Barnes Hut (Quad-Tree): <math>O\left( n \log n \right)</math> | ||
** 전체 맵을 quadratic tree 로 구성하여서 인접한 픽셀을 바로 찾을 수 있는 트리로 구성한 후 계산 | |||
=== 위치 추정 === | === 위치 추정 === | ||
<math>n</math>개의 검출 지점 <math>X_{i}</math> 위치의 좌표로부터 하나의 값 <math display="inline">V</math>를 구하기 위해 다음 공식을 따르며, 이는 일반적으로 말하는 가중평균(무게중심법)과 같습니다.<math display="block">V = \frac{\sum_{i=1}^{n}W_{i}X_{i}}{\sum_{i=0}^{n}W_{i}}</math> | <math>n</math>개의 검출 지점 <math>X_{i}</math> 위치의 좌표로부터 하나의 값 <math display="inline">V</math>를 구하기 위해 다음 공식을 따르며, 이는 일반적으로 말하는 가중평균(무게중심법)과 같습니다.<math display="block">V = \frac{\sum_{i=1}^{n}W_{i}X_{i}}{\sum_{i=0}^{n}W_{i}}</math> | ||
가중값 <math>W_i</math>는 바이너리 픽셀 (ADC 값이 존재하지 않는 경우나, 신호 세기를 구별할 수 없는 경우) 1로 일괄 적용합니다. ADC 값이 있는 경우 그 값을 그대로 <math>W_i</math>로 적용하기도 하나, 신호 세기에 대한 반응 함수를 한번 적용한 값을 활용하기도 합니다. 이는 telescope 실험을 통해 검출기와 그 세팅별로 최적화되는 값 함수를 찾아야 합니다. | 가중값 <math>W_i</math>는 바이너리 픽셀 (ADC 값이 존재하지 않는 경우나, 신호 세기를 구별할 수 없는 경우) 1로 일괄 적용합니다. ADC 값이 있는 경우 그 값을 그대로 <math>W_i</math>로 적용하기도 하나, 신호 세기에 대한 반응 함수를 한번 적용한 값을 활용하기도 합니다. 이는 telescope 실험을 통해 검출기와 그 세팅별로 최적화되는 값 함수를 찾아야 합니다. | ||
| 38번째 줄: | 42번째 줄: | ||
* 이진검출기(on-off 만 존재하여 <math>W_i=1</math>로 고정)이거나, <math>W_i</math>의 단계가 충분히 많지 않으면서, | * 이진검출기(on-off 만 존재하여 <math>W_i=1</math>로 고정)이거나, <math>W_i</math>의 단계가 충분히 많지 않으면서, | ||
* 검출 지점의 갯수 <math>n </math>이 비교적 적은 경우 | * 검출 지점의 갯수 <math>n </math>이 비교적 적은 경우 | ||
=== 핫 픽셀 === | === 핫 픽셀 === | ||
핫 픽셀이 있는 경우, 해당 픽셀과 함께 묶인 클러스터는 '''해당 핫 픽셀을 포함해야할 수도 있고, 아닐 수도 있습니다.''' | |||
== 전산 모사 == | == 전산 모사 == | ||