大規模データのクラスター分析Faiss

1. Faissの概要

1.1 Faissとは

FaissはFacebook Resarchが提供する高密度ベクトルの効率的な類似性検索とクラスタリングするライブラリです。近傍探索問題は、データ量に応じて計算量が急激に増大する古典的な問題があって、RAMが足らないや計算時間がかかるといった問題あります。ライブラリーFaissは、Python / Numpyの完全なラッパーを使用してC ++で記述されて、学習時間が高速であると言われています。

1.2 Faissのライブラリ

ライブラリーFaissは、ベクトルのセットを格納するインデックスタイプを中心に構築されており、L2および/またはドット積ベクトルの比較でそれらを検索する機能を提供します。利用可能なインデックス構造のほとんどに対応しています。以下の点で優れていると言われています。

・検索時間

・検索品質

・インデックスベクトルごとに使用されるメモリ

・トレーニングの時間

・教師なしトレーニングのための外部データの必要性

資料：https://github.com/facebookresearch/faiss

2. 実験

データセット：大量データを生成します。（1,000,000件）

モデル：FaissのkmeansとScikit-learnのkmeans

モデル評価：実行時間、Rand score(クラスタリング間の類似度)

Rand scoreの詳細：　RAND Scoreの記事

ライブラリのインストール

conda install faiss-cpu -c pytorch # Faiss

pip install -U scikit-learn # Sklearn

環境確認

import sys

import sklearn

import faiss

print(‘Python environment : ‘ + str(sys.version))

print(‘faiss version : ‘ + str(faiss.__version__))

print(‘sklearn version : ‘ + str(sklearn.__version__))

Python environment : 3.7.11

faiss version : 1.7.1

sklearn version : 0.24.2

2.1 サンプルデータ生成

８クラスター、30カラム、1,000,000行のデータを生成します。

from sklearn.datasets import make_blobs

X, y = make_blobs(n_samples=1000000, centers=8, n_features=30,

random_state=42)

faiss関数を作成します。

import faiss

import numpy as np

class FaissKMeans:

def __init__(self, n_clusters=4, n_init=1000, max_iter=300, random_state=42):

self.n_clusters = n_clusters

self.n_init = n_init

self.max_iter = max_iter

self.seed = random_state

self.kmeans = None

self.cluster_centers_ = None

self.inertia_ = None

def fit(self, X):

self.kmeans = faiss.Kmeans(d=X.shape[1],

k=self.n_clusters,

niter=self.max_iter,

nredo=self.n_init,

seed=self.seed)

self.kmeans.train(X.astype(np.float32))

self.cluster_centers_ = self.kmeans.centroids

self.inertia_ = self.kmeans.obj[-1]

self.labels_ = self.kmeans.index.search(X.astype(np.float32), 1)[1].reshape(-1,)

def predict(self, X):

return self.kmeans.index.search(X.astype(np.float32), 1)[1]

2.2 Faissのkmeans

Faissのモデルを学習しました。一分以内にモデルを学習しました。

%%time

ff = FaissKMeans()

ff.fit(X)

Wall time: 58.2 s

Rand score

クラスタリング間の類似度のRand Indexを計算します。

from sklearn.metrics import adjusted_rand_score

print(“Adjusted Rand Score: {0:.3f}”.format(adjusted_rand_score(y, ff.labels_)))

print(“Inertia: {0:.1f}”.format(ff.inertia_))

from sklearn.cluster import KMeans

2.3 Scikit-learnのkmeans

Scikit-learnのkmeansの実行は12分くらいです。

%%time

km = KMeans(random_state=42, n_clusters=4, n_init=1000, max_iter=300)

km.fit(X)

Wall time: 12min 13s

Scikit-learnのRand Scoreを計算しました。

print(“Adjusted Rand Score: {0:.3f}”.format(adjusted_rand_score(y, km.labels_)))

print(“Inertia: {0:.1f}”.format(km.inertia_))

Adjusted Rand Score: -1.004

Inertia: 449244177.4

2.4 まとめ

30カラム、1,000,000行のデータでScikit-learnのkmeans とFaissのkmeansを学習しました。Faissのkmeansは12.6倍速くになりました。ただ普通のKmeanとは大きく異なる結果のようです。

	Faissのkmeans	Scikit-learnのkmeans
Wall time	58	733
Rand Score	-1.004	-1.004

担当者：HM

香川県高松市出身　データ分析にて、博士（理学）を取得後、自動車メーカー会社にてデータ分析に関わる。その後コンサルティングファームでデータ分析プロジェクトを歴任後独立　気が付けばデータ分析プロジェクトだけで５０以上担当

理化学研究所にて研究員を拝命中　応用数理学会所属

目次