6.6. Случайная проекция

Модуль sklearn.random_projection реализует простой и эффективный в вычислительном отношении способ снижения размерности данных путем обмена контролируемой точности (в качестве дополнительной дисперсии) на более быстрое время обработки и меньшие размеры модели. Этот модуль реализует два типа неструктурированной случайной матрицы: Гауссова случайная матрица и разреженная случайная матрица.

Размеры и распределение матриц случайных проекций контролируются таким образом, чтобы сохранить попарные расстояния между любыми двумя выборками набора данных. Таким образом, случайная проекция является подходящим методом аппроксимации для метода, основанного на расстоянии.

Ссылки:

• Sanjoy Dasgupta. 2000. Experiments with random projection. In Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence (UAI’00), Craig Boutilier and Moisés Goldszmidt (Eds.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 143-151.

• Ella Bingham and Heikki Mannila. 2001. Random projection in dimensionality reduction: applications to image and text data. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (KDD ‘01). ACM, New York, NY, USA, 245-250.

6.6.1. Лемма Джонсона-Линденштрауса

Основным теоретическим результатом эффективности случайного проецирования является лемма Джонсона-Линденштрауса (цитата из Википедии):

Лемма о малом искажении (также известна как лемма Джонсона — Линденштрауса) утверждает, что множество из n точек многомерного пространства можно отобразить в пространство размерности гораздо меньше n таким образом, что расстояния между точками останутся почти без изменений. При этом такое отображение можно найти среди ортогональных проекций. Лемма позволяет сжимать данные, представленные точками многомерного пространства, и, что более важно, сократить размерность данных без существенной потери информации. Лемма была доказана Вильямом Джонсоном и Йорамом Линденштраусом

Зная только количество выборок, функция johnson_lindenstrauss_min_dim консервативно оценивает минимальный размер случайного подпространства, чтобы гарантировать ограниченное искажение, вносимое случайной проекцией:

>>> from sklearn.random_projection import johnson_lindenstrauss_min_dim
>>> johnson_lindenstrauss_min_dim(n_samples=1e6, eps=0.5)
663
>>> johnson_lindenstrauss_min_dim(n_samples=1e6, eps=[0.5, 0.1, 0.01])
array([    663,   11841, 1112658])
>>> johnson_lindenstrauss_min_dim(n_samples=[1e4, 1e5, 1e6], eps=0.1)
array([ 7894,  9868, 11841])

Example:

• См. The Johnson-Lindenstrauss bound for embedding with random projections для теоретического объяснения леммы Джонсона-Линденштрауса и эмпирической проверки с использованием разреженных случайных матриц.

Ссылки:

• Sanjoy Dasgupta and Anupam Gupta, 1999. An elementary proof of the Johnson-Lindenstrauss Lemma.

6.6.2. Гауссова случайная проекция

GaussianRandomProjection снижает размерность, проецируя исходное входное пространство на случайно сгенерированную матрицу, где компоненты взяты из следующего распределения \(N(0, \frac{1}{n_{components}})\).

Вот небольшой отрывок, иллюстрирующий, как использовать гауссовский преобразователь случайной проекции:

>>> import numpy as np
>>> from sklearn import random_projection
>>> X = np.random.rand(100, 10000)
>>> transformer = random_projection.GaussianRandomProjection()
>>> X_new = transformer.fit_transform(X)
>>> X_new.shape
(100, 3947)

6.6.3. Разреженная случайная проекция

SparseRandomProjection снижает размерность, проецируя исходное входное пространство с использованием разреженной случайной матрицы.

Разреженные случайные матрицы являются альтернативой плотной гауссовой случайной матрице проекции, которая гарантирует аналогичное качество внедрения, но при этом гораздо более эффективно использует память и позволяет быстрее вычислять проецируемые данные.

Если мы определим s = 1 / density, элементы случайной матрицы берутся из

\[\begin{split}\left\{ \begin{array}{c c l} -\sqrt{\frac{s}{n_{\text{components}}}} & & 1 / 2s\\ 0 &\text{with probability} & 1 - 1 / s \\ +\sqrt{\frac{s}{n_{\text{components}}}} & & 1 / 2s\\ \end{array} \right.\end{split}\]

где \(n_{\text{components}}\) - размер проецируемого подпространства. По умолчанию плотность ненулевых элементов установлена ​​на минимальную плотность, рекомендованную Пингом Ли и др.: \(1 / \sqrt{n_{\text{features}}}\).

Вот небольшой отрывок, иллюстрирующий, как использовать преобразователь разреженной случайной проекции:

>>> import numpy as np
>>> from sklearn import random_projection
>>> X = np.random.rand(100, 10000)
>>> transformer = random_projection.SparseRandomProjection()
>>> X_new = transformer.fit_transform(X)
>>> X_new.shape
(100, 3947)

Ссылки:

• D. Achlioptas. 2003. Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Journal of Computer and System Sciences 66 (2003) 671–687

• Ping Li, Trevor J. Hastie, and Kenneth W. Church. 2006. Very sparse random projections. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD ‘06). ACM, New York, NY, USA, 287-296.

6.6.4. Обратное преобразование

Преобразователи случайных проекций имеют параметр compute_inverse_components. Если установлено значение True, после создания случайной матрицы components_ во время обучения преобразователь вычисляет псевдообратную эту матрицу и сохраняет ее как inverse_components_. Матрица inverse_components_ имеет форму \(n_{features} \times n_{components}\), и это всегда плотная матрица, независимо от того, является ли матрица компонентов разреженной или плотной. Таким образом, в зависимости от количества функций и компонентов он может использовать много памяти.

Когда вызывается метод inverse_transform, он вычисляет произведение входного значения X и транспонирование обратных компонентов. Если обратные компоненты были вычислены во время обучения, они повторно используются при каждом вызове inverse_transform. В противном случае они каждый раз пересчитываются, что может оказаться дорогостоящим. Результат всегда плотный, даже если X разрежен.

Вот небольшой пример кода, который иллюстрирует, как использовать функцию обратного преобразования:

>>> import numpy as np
>>> from sklearn.random_projection import SparseRandomProjection
>>> X = np.random.rand(100, 10000)
>>> transformer = SparseRandomProjection(
...   compute_inverse_components=True
... )
...
>>> X_new = transformer.fit_transform(X)
>>> X_new.shape
(100, 3947)
>>> X_new_inversed = transformer.inverse_transform(X_new)
>>> X_new_inversed.shape
(100, 10000)
>>> X_new_again = transformer.transform(X_new_inversed)
>>> np.allclose(X_new, X_new_again)
True