MurmurHash3와 같은 해시 함수를 적용하여 범주형 특징을 고정 크기 버킷으로 변환함으로써, 카디널리티가 높은 변수에 대한 원핫 인코딩의 메모리 폭발 문제를 방지합니다.
여러 값이 동일한 버킷에 매핑되는 해시 충돌을 허용하여, 스트리밍 및 대규모 학습 환경에서 정확도를 다소 희생하는 대신 메모리 및 계산 효율성을 크게 향상시킵니다.
스팸 필터링, 추천 시스템, 클릭률(CTR) 예측 등 특징 공간에 수백만 개의 고유값이 존재하여 기존 인코딩 방식이 불가능한 경우에 주로 사용됩니다.
해시 버킷이란?
컴퓨팅에서 해시 테이블 [해시 맵]은 키 [고유한 문자열이나 정수]를 기반으로 개체에 사실상 직접적인 액세스를 제공하는 데이터 구조를 말합니다. 해시 테이블은 해시 함수를 사용해 인덱스를 버킷이나 슬롯 어레이로 연산하는데, 여기에서 원하는 값을 찾을 수 있습니다. 여기에 사용되는 키의 주된 특징을 소개합니다.
사용되는 키는 SSN, 전화번호, 계좌 번호 등 무엇이든 가능
반드시 고유한 키가 있어야 함
각각의 키가 값과 연결됨(즉 값에 매핑됨)
해시 버킷은 정렬이나 검색 용도로 데이터 항목을 배분하는 데 쓰입니다. 이 작업의 목표는 서로 연결된 목록을 약화하여 특정 항목의 검색 결과에 짧은 기간 내에 액세스할 수 있게 하는 것입니다. 버킷을 사용하는 해시 테이블은 사실상 어레이 하나와 연결된 목록 하나의 조합이라고 할 수 있습니다. 어레이의 각 요소 [해시 테이블]가 연결된 목록의 헤더가 됩니다. 같은 위치로 해시되는 모든 요소가 해당 목록에 저장됩니다. 해시 함수가 각각의 레코드를 버킷 중 하나에 속한 첫 슬롯에 할당합니다. 슬롯에 이미 자리가 찬 경우, 버킷 슬롯을 차례로 검색하여 열린 슬롯을 찾아냅니다. 버킷이 완전히 꽉 찬 경우, 해당 레코드는 테이블 끝에 있는 무한 용량 오버플로 버킷에 저장됩니다. 모든 버킷이 같은 오버플로 버킷을 공유합니다. 다만 잘 된 구현이라면 레코드를 여러 버킷에 골고루 분배하는 해시 함수를 써서 오버플로 버킷에 들어가는 레코드를 가능한 한 적게 합니다.
버킷을 사용하는 해시 테이블은 사실상 어레이 하나와 연결된 목록 하나의 조합이라고 할 수 있습니다. 어레이의 각 요소 [해시 테이블]가 연결된 목록의 헤더가 됩니다. 같은 위치로 해시되는 모든 요소가 해당 목록에 저장됩니다. 해시 함수가 각각의 레코드를 버킷 중 하나에 속한 첫 슬롯에 할당합니다. 슬롯에 이미 자리가 찬 경우, 버킷 슬롯을 차례로 검색하여 열린 슬롯을 찾아냅니다. 버킷이 완전히 꽉 찬 경우, 해당 레코드는 테이블 끝에 있는 무한 용량 오버플로 버킷에 저장됩니다. 모든 버킷이 같은 오버플로 버킷을 공유합니다. 다만 잘 된 구현이라면 레코드를 여러 버킷에 골고루 분배하는 해시 함수를 써서 오버플로 버킷에 들어가는 레코드를 가능한 한 적게 합니다.