Это краткое содержание статьи FastEmbed [python] [pyspark]
SVD / PCA - это широко используемый метод встраивания для низкоразмерных наборов данных. Вопрос, на который мы здесь отвечаем: «Как вы масштабируете SVD / PCA для многомерных наборов данных, таких как социальные сети?»
Так что же такое встраивание SVD / PCA?
Сначала мы создаем матрицу M (каждая строка является записью набора данных). Затем мы вызываем стандартную процедуру SVD, чтобы получить ее декомпозицию:
Используя это K -мерное разложение, мы получаем K -мерное вложение следующим образом:
где весовая функция сингулярного значения f (.) является гиперпараметром. Строки этой K -мерной матрицы - это вложения строк входного набора данных.
Так почему вложения SVD / PCA - хорошая идея?
Две основные причины, по которым мы используем SVD, - это уменьшение размерности и подавление шума:
Давайте посмотрим на графики по другой причине. Пусть A обозначает матрицу смежности графа, а D - диагональную матрицу со степенью каждого узла на диагонали. Тогда L = D - A называется лапласианом графа. Собственные векторы этой матрицы показывают хорошие разрезы графа (разделы графа, которые пересекают как можно меньше ребер).
Итак, что мешает нам использовать SVD / PCA для многомерных наборов данных?
Количество собственных векторов, необходимых для многомерных наборов данных, также растет: например, мы ожидаем, что в более крупном графе будет больше кластеров плотно связанных узлов:
Это проявляется в необходимости вычислять больше собственных векторов. Учитывая, что матрица данных M также растет с размером графа, это означает, что стандартные алгоритмы факторизации матрицы не могут решить проблему. Кроме того, эти алгоритмы требуют, чтобы вся матрица умещалась в одной машине (что не всегда так).
Как нам обойти эти ограничения?
Мы задаем следующий вопрос: есть ли что-нибудь, что SVD / PCA делает помимо того, что мы обсуждали до сих пор?
Ответ:
и нам не нужно это преимущество «сжатия» SVD / PCA для вывода. Вот краткое изложение типичного рабочего процесса с использованием SVD для матрицы данных M размером m на n:
Теперь, когда мы определили это, мы задаем следующий вопрос - как мы можем сохранить преимущества SVD для логических выводов, одновременно ускорив вычисление:
Алгоритм прост:
Результаты: кластеризация графиков
Распространенная задача - сгруппировать вершины графа так, чтобы связанные вершины принадлежали одному кластеру - Иллюстрация:
Показателем качества кластера является показатель модульности сети. Можно использовать вложения для преобразования вершин графа в векторы, а затем применить k -средство для кластеризации вложений. Давайте посмотрим, как FastEmbed выполняет эту задачу кластеризации графов:
Набор данных: сеть совместных закупок Amazon - ориентированный граф размером 262 111 узлов и 1 234 877 ребер (преобразован в неориентированный граф для этого анализа).
Мы берем 40-мерное вложение и кластеризуем граф с помощью k -средних с k = 100:
- Стандартное собственное разложение (PCA) с 40 измерениями модульность 0,26 (~ 45 минут)
- Node2vec (40 измерений с параметрами по умолчанию) модульность 0,83 (~ 20 минут)
- FastEmbed с f (λ) = 1, если abs (λ) ›0,98 иначе 0
на нормализованной матрице смежности модульность 0,80 (~ 1 минута)
Примечание: нормализованная матрица смежности: n (u, v) = w (u, v) / sqrt (d (u) d (v)), где d (u) = sum (v) (w (u, v))
