Product Quantization

在前面一節講解了向量數據庫索引相關的內容，那么本節將會講解其中壓縮方法的量化手段：乘積量化器。

簡單來說將向量的所有維度劃分為多個子空間，每個子空間一部分維度，然后每個子空間獨立去找最近距離。例如一個128維度的向量，劃分為16個子空間，每個子空間有該向量的8個維度，第一個子空間：1-8，第二個子空間9-16，第十六個子空間121:128。下面詳細講解Product quantization的訓練與查詢：

注：本篇文章已更新至星球。

1.訓練

將n個數據集的d個維度按照m個子空間進行劃分，每個子空間的維度為d/m，子空間的維度不一定要相等。對n個數據集中的所有子空間的向量采用k-means算法進行聚類，找出每個子空間的k個質心。質心也稱為再現值(reproduction value)。質心集稱為碼本(codebook)。

例如：有1000個向量，每個向量都是128維度，需要拆分8個子空間，k-means的聚類k = 256，那么每個子空間的維度是128/8=16維，每個子空間的向量是16 * 32bits，下圖展示了每個子空間聚類256個中心點，每個中心點的維度是16，總共有子空間數量(8)個中心集合，codebook的維度就是8 * 256 * 16。