[8주차] 격자

[ella-yschoi]

격자에 대해 알아보아요!

[ainochi-kor]

정리

격자를 전산화 시키는 과정이 신기했고, 다양한 수학 공식이 나왔지만 그걸 코드로 풀어내는 걸 보면서 신기했고,
갑자기 나온 확장 탐색을 보면서 코드로 예시 돌려보면서 만들어보면 어떨까 생각이 들었습니다.

[ella-yschoi]

정리

• 수학적인 개념이 나와 당황스럽고 어려웠지만.. 어찌저찌 읽어씃ㅂ니다.
• 여행 잘 다녀오겠습니다! 🇨🇦 모두 즐거운 설 연휴 보내세요 :)

[hanana1253]

요약

1. 최근접 이웃 탐색 소개

• 주어진 탐색 목표와 가장 가까운 데이터 점을 찾기
• 가장 가까운 항목을 찾기만 하면 된다.
  • c.f. 이진 탐색은 데이터 집합 안에서 정확히 일치하는 점을 찾지만, 있을 수도 있고 없을 수도 있다.
• 다차원 데이터를 다룰 때 유용
• 선형 스캔을 이용한 최근접 이웃 탐색: 수직선상에서 각 데이터 점을 순회하며 최소 거리와 비교
• 공간 데이터 탐색: 2차원 점을 튜플이나 배열, 복합 자료 구조 등으로 표현하고 유클리드 거리의 선형 스캔 알고리즘 계산
• 1차원 공간의 최근접 이웃은 2차원 공간의 최근접 이웃과 같지 않다.
  • 1차원 데이터의 경험을 적용하는 동시에 더 높은 차원에 내재된 구조를 활용하는 새로운 접근 방식 필요

2. 격자

• grid는 2차원 데이터를 저장하기 위한 자료 구조
• x축과 y축의 차원 안에서 상자는 그 상자의 범위에 속하는 모든 데이터 점의 리스트를 저장
• 데이터 점의 좌표를 사용해 각 저장소를 결정하며, 탐색을 제한
• 격자를 표현하는 최상위 자료구조에는 관리를 위한 추가 정보가 포함
• 각 차원에 따른 공간 경계 추적: x, y축의 최솟값과 최댓값 표시
• 생성: 빈 격자 자료 구조를 할당 후 데이터들을 for문을 통해 점으로 추가. 각 좌표를 LinkedList로 구현 가능
• 제거: 제거할 점을 결정(중복 데이터가 있을 수 있으므로)하고 리스트에서 제거

3. 격자에 대한 탐색

• 상자 가지치기: 너무 멀리 떨어져 있는 격자 셀을 제외하여 검사할 점의 개수를 제한
• 현재의 최소 거리보다 가까운 점이 해당 상자에 있는지 확인해서, 없으면 무시
• 선형 스캔 알고리즘: 모든 상자를 선형 스캔하면서, 잠재적으로 최근접 이웃이 포함될 수 있는 상자만 검사
  • 상자 안 모든 점에 대한 최소 거리가 지금까지 본 최선의 점까지의 거리보다 크면 해당 상자를 가지치기
  • 목표점에서 멀리 떨어진 상자를 검사하면서 상당한 계산 비용을 낭비
• 확장 탐색: 목표점에서 가장 가까운 상자를 먼저 선택하고, 나머지 상자에 대한 탐색을 중단
  • 최초 상자가 비어있는 경우에는 외부로 탐색을 확장
  • 목표점과 같은 상자 뿐 아니라 인접한 칸을 모두 확인해야 한다.
  • 알고리즘이 복잡하다는 단점

4. 격자 크기의 중요성

• 격자 상자 크기는 탐색 효율에 큰 영향을 끼친다.
  • 상자가 클수록 더 많은 점에 대해 선형 스캔 필요
  • 격자를 잘게 분할하면 메모리가 더 많이 필요하고 빈 상자의 수도 늘어난다.

5. 2차원을 넘어

• 다차원 문제에 격자를 적용하는 것은 이상적이지 않다 -> k-d 트리 소개!

6. 공간 데이터를 넘어

• 공간 데이터 이외 분야에도 적용 가능한 격자
• 비슷한 커피를 찾으려면 커피 강도나 산미와 같은 속성의 거리를 계산할 수 있는 방법 필요

7. 격자가 중요한 이유

• 탐색 기준이 달라짐: 정확한 목표 탐색 (X) -> 목표와의 거리를 기반으로 탐색 (O)
• 한 상자에 여러 값을 저장하는 기술을 사용함으로써 상자의 크기라는 새로운 트레이드오프 관계 생성

느낀점

• 책이 초심을 잃어서 읽다가 중간에 포기. 내일 다시 이어서 해보겠습니다. (라고 해놓고 2주 뒤에 함)
• 위치 뿐 아니라 특성에 대해서도 목표치와 비슷한 대상을 찾을 수 있다는 것은 놀라운 일이다.

[thgr8ganzi]

정리

• 저와 비슷하게 생각하신분들이 많아서 놀랐습니다.
• 유클리드 거리 기억해야겠습니다.
• 자료구조는 알고리즘과 떼어낼수없고 상당히 어렵네요, 한주 푹쉬고 다음장은 진심으로 공부 해봐야겠습니다.
• 새해 복 많이 받으세요

[yunseorim1116]

까먹을뻔 했네요.. 정리링크
이번에 쫌 어려워서 몇회독 해보려고 해요
한 번으로는 안되겠더라구요 하하하

[ddongule]

요약을 하다가.. ^^ 급히 나가봐야할일이 생겨서 급하기 마무리했는데 갔다와서 정리하겠습니다~~~~!!! (ㅎㅎㅎ;;)

[chloe-codes1]

내용정리

최근접 이웃탐색 소개

• 최근접 이웃 탐색
  • 주어진 목표와 가장 가까운 데이터 점을 찾는 과정
  • 이진 탐색과 비슷하지만, 탐색 성공 기준이 다르다
  • 가장 가까운 항목을 찾는 것이 목표
• 선형 스캔을 이용한 최근접 이웃 탐색
  • 대부분의 프로그래밍 언어에서 루프를 사용하여 쉽게 구현 가능!
  • 다른 거리 함수와 다차원에도 쉽게 지원된다

격자

• 특징
  • 격자는 2차원 데이터를 저장하는 자료 구조로, 배열처럼 고정된 셀로 구성됨
  • 배열과 달리 각 셀에 여러 값을 저장 가능
  • 데이터 점의 좌표를 바탕으로 각 셀을 결정하고, 탐색 제한 가능
• 구조
  • 격자 구조는 관리용 추가 정보를 포함한다
  • 격자 생성 시, 데이터 점에 대해 for 루프를 수행하면 된다
• 점 제거하기
  • 격자에서 점을 제거할 때, 올바른 셀을 찾아야 함
  • 연결 리스트를 순회해 해당 점을 찾아 제거한다

격자에 대한 탐색

• 상자 가지치기
  • 목표점과 주어진 거리 내에 점이 존재하는지 확인한다
  • 차원을 독립적으로 고려하여 점과 격자 상자의 경계 거리 계산이 가능하다
• 확장 탐색
  • 목표점이 포함된 상자에서 탐색 범위를 확장하여 최근접 이웃을 찾는다
  • 이상적인 확장 탐색 방법을 사용하여 상자 내 점을 찾는다

느낀점

새해 복 많이 받으세요~!

[sa02045]

느낀점

• 좀 더 실제 세계의 문제를 풀 수 있는 자료구조, 알고리즘인 것 같아 재밌었습니다~

8.1 최근접 이웃 탐색 소개(nearest-neighbor search)

• 탐색 목표와 가장 가까운 데이터 점을 찾는 방법
• “현재 위치에서 가장 가까운 커피숍을 찾는 방법은?”
• 이진 탐색은 탐색하고자 하는 점이 있을 수도, 없을 수도 있음
• 최근점 탐색은 가장 가까운 점만 찾으면 됨
• 다차원 데이터는 배열, 튜플, 복합 자료구조에 담을 수 있음
• 선형 스캔 방법
  • 브루트 포스 방식
  • 좀 더 효율적으로 탐색하려면? 새로운 접근 방식이 필요
  • 의미 있는 차원의 정보를 활용해 가지를 쳐내야함
  • 1차원 데이터의 경험을 적용하는 동시에 더 높은 차원에 내제된 구조를 활용해야함

8.2 격자

• 2차원 데이터를 저장하기 위한 격자 자료구조를 도입

8.3 격자 탐색

• 격자 구조를 활용하면 효율적으로 탐색할 수 있음
• 유클리드 거리를 활용하여 주어진 상자와 목표점의 최단 거리를 구할 수 있음
• 이제 격자 내의 상자들을 선형탐색하면서 가지치기를 수행
  • 상자와 목표점의 최단 거리 계산 → 현재 가장가까운 거리보다 가까운가? → 상자 내부의 점들을 탐색
• 선형 탐색의 한계 → 모든 공간의 정보를 활용하지는 않음. 좀 더 효율적인 방법이 없을까?!
• 확장 탐색을 하자
  • 목표점에서 가장 가까운 상자를 먼저 선택하고 멀리 떨어진 나머지 상자에 대한 탐색은 중단하자
  • 목표점에서 최근접 이웃 후보가 포함된 다른 상자를 찾을 때 까지 외부로 확장해가면서 점진적으로 진행
  • 최초의 최근접 이웃후보를 얻었다고 끝나는 것이 아님
  • 최근접 이웃후보가 포함될 수 있는지 확인할 필요가 있는 칸이 남이 있지 않을 때까지 탐색
• 맨해튼 거리
  • 상자(격자 셀) 사이 차이의 합계를 활용하여 초기 상자라부터 거리를 증가해나가면서 상자를 선택하기 편함
  • 상자안에서 목표점에 이르는 거리가 임곗값보다 작은 점중에서 목표점과 가장 가까운 점을 찾기
• 현재 상자 탐색**:** 먼저 지정된 상자에서 가장 가까운 점을 확인하고, 없다면 주변 상자로 탐색을 확장
• 주변 상자 확장**:** 탐색 범위를 한 단계씩 넓혀가며, 상하좌우 및 대각선의 상자를 확인
• 거리 비교**:** 발견된 점들과 주어진 좌표 사이의 거리를 계산하여 최단 거리를 갱신
• 탐색 종료**:** 더 이상 가까운 점이 발견되지 않으면, 가장 가까운 점을 반환하며 탐색 종료

[iborymagic]

8.1 최근접 이웃 탐색 소개

• 주어진 탐색 목표와 가장 가까운 데이터 점을 찾음
• 이진 탐색 = 데이터 집합 안에서 정확히 일치하는 점이 있을 수도, 없을 수도 있음
• 최근접 이웃 탐색 = 단지 가장 가까운 항목을 찾으면 됨

8.2 격자

• 2차원 데이터를 저장하기 위한 자료구조. 고정된 일련의 상자 or 셀로 구현
• 배열과 달리 각 상자에 값을 하나만 담게 제한 X

8.3 격자에 대한 탐색

• 요 부분은 조금 어려워서 한 번 더 읽어보고 정리하겠읍니다..

---

• 어우 내용이 꽤 어렵습니다..
• 다들 열심히 읽으신 것 같아서 대충 후루룩 읽은 것이 반성되는군요
• 한 번 더 읽고 빡세게 정리해보겠읍니다..

[sunhpark42]

• 핵심적인 차이는 탐색에 성공하는 기준이다. 이진 탐색은 데이터 집합 안에서 정확히 일치하는 점을 찾는데 일치하는 점이 있을 수도 있고 없을 수도 있다. 반면, 최근접 이웃 탐색은 단지 가장 가까운 항목을 찾기만 하면 된다. 탐색 목표와 다른 값 사이의 거리를 정의할 수만 있으면 항상 최근접 이웃을 찾을 수 있다.

• 데이터 점이 있는 2차원 공간에서 모든 데이터 점을 확인해볼 필요는 없다. 일부 데이터 점은 너무 멀리 있어서 문제가 되지 않을 수 있다.

• 여러분의 공간 자료 구조에 들어 있지 않는 범위에 속하는 데이터 점이 발생하는 경우 어떻게 할지고려해야 한다. 어떤 경우든 사용자에게 이 함수의 동작을 명백히 문서화해야 한다.

• 격자 상자 크기는 탐색 효율에 아주 큰 영향을 끼친다. 상자가 클수록 더 많은 점에 대해 선형 스캔해야 한다. 그러나 격자를 더 잘게 분할하면 선형 스캔해야 할 점의 수는 줄지만 메모리가 더 많이 필요하고 빈 상자의 수도 늘어난다는 트레이드오프 관계가 있다. 격자 상자 크기를 줄이면 최초로 최근접 이웃 후보를 찾기 전에 더 많은 상자를 탐색해야 하기 때문에 상자 검사 비용이 늘어난다. 최적의 격자 크기는 점의 수나 분포 등 여러 요소에 따라 결정된다.

-알라딘 eBook <읽고 나면 진짜 쉬워지는 자료 구조 > (제레미 쿠비카 지음, 오현석 옮김) 중에서

다음장 읽기가 무서워졌어요. 인공지능 할때 knn이 생각나네요.. 비공간데이터에 더 많이 사용될수 있는 자료구조라는 생각이 듭니다. 역시나 이번에도 내가 다룰 데이터 특성을 이해하는 것이 중요하다는 것을 느꼈읍니다.. 이래서 도메인 도메인 하는걸까요 🤔