6.6. Случайный Проекции

6.6.1. Лемма Джонсона-Линденбаума

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

В математике лемма Джонсона-Линденбаума — это результат, касающийся вложений с малой искажением точек из многомерного пространства в низкоразмерное евклидово пространство. Лемма утверждает, что небольшое множество точек в многомерном пространстве может быть вложено в пространство значительно меньшей размерности таким образом, что расстояния между точками почти сохраняются. Отображение, используемое для вложения, по крайней мере липшицево, и даже может быть взято в качестве ортогональной проекции.

Зная только количество выборок, 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])

Примеры

• См. Граница Джонсона-Линденбаума для вложения с помощью случайных проекций для теоретического объяснения леммы Джонсона-Линденбаума и эмпирической проверки с использованием разреженных случайных матриц.

Ссылки

• Санжой Дасгупта и Анупам Гупта, 1999. Простой вывод леммы Джонсона-Линденбаума.

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, элементы случайной матрицы выбираются из

где \(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)

Ссылки

• Д. Ахлиоптас. 2003. Дружественные базам данных случайные проекции: Джонсон-Линденбаум с бинарными монетами. Журнал вычислительной техники и системных наук 66 (2003) 671-687.
• Пинг Ли, Тревор Дж. Гасти и Кеннет В. Черч. 2006. Очень разреженные случайные проекции. В Трудах 12-й международной конференции ACM SIGKDD по открытию знаний и обработке данных (KDD ‘06). ACM, Нью-Йорк, Нью-Йорк, США, 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