Как правильно использовать СВД в Accord.net

SVD расшифровывается как Singular Value Decomposition и считается популярным методом сокращения признаков при классификации текста. Я знаю этот принцип как эту ссылку.

Я использовал С#, использовал библиотеку Accord.Net и уже имел зубчатый массив double[][] из расчета TF-IDF.

Я уже знаю, что в моих документах есть 4 темы. Я хочу протестировать метод Kmean с количеством кластеров k = 4. Прежде чем использовать Kmean, я хочу использовать SVD для уменьшения количества признаков. Когда появляются результаты, почти 90% документов группируются в 1 группу, остальные группируются в 3 других кластера. Это очень плохой результат. Я пытался повторить несколько раз, но результаты не сильно меняются. Если я использую PCA вместо SDV, все будет хорошо, как и ожидалось.

Итак, где я не прав. Любой, кто знает это, может указать мне пример кода. Большое спасибо.

Примечание: в моем оригинальном TF-IDF есть строки, представляющие документы, и столбцы, представляющие термины.

Вот мой код:

        //to matrix because the function SVD requiring input of matrix, not jagged array
        //transpose because the TF-IDF used for SVD has rows representing terms, columns representing documents; 
        var svd = new SingularValueDecomposition(tfidf.ToMatrix().Transpose());
        double[,] U = svd.LeftSingularVectors;
        double[,] S = svd.DiagonalMatrix;
        double[,] V = svd.RightSingularVectors;

        //find the optimal cutoff y so that we retain enough singular values to make up 90% of the energy in S
        //http://infolab.stanford.edu/~ullman/mmds/ch11.pdf, page 18-20
        double energy = 0;
        for (int i = 0; i < S.GetLength(0); i++)
        {
            energy += Math.Pow(S[i, i], 2);
        }

        double percent;
        int y = S.GetLength(0);
        do
        {
            y--;
            double test = 0;
            for (int i = 0; i < y; i++)
            {
                test += Math.Pow(S[i, i], 2);
            }

            percent = test / energy;
        } while (percent >= 0.9);
        y = y + 1;

        //Uk gets all rows, y first columns of U; Sk get y first rows, y first columns of S; Vk get y first rows, all columns of V
        double[,] Uk = U.Submatrix(0, U.GetLength(0) - 1, 0, y - 1);
        double[,] Sk = S.Submatrix(0, y - 1, 0, y - 1);
        double[,] Vk = V.Submatrix(0, y - 1, 0, V.GetLength(1) - 1);

        //reduce dimension according to http://stats.stackexchange.com/questions/107533/how-to-use-svd-for-dimensionality-reduction-to-reduce-the-number-of-columns-fea
        //we tranpose again to have the rows being document, columns being term as original TF-IDF
        //ToArray because the Kmean below acquiring input of jagged array
        tfidf = Uk.Multiply(Sk).Transpose().ToArray();
        // if tfidf = Uk.Multiply(Sk).Multiply(Vk).Transpose().ToArray()
        // result still bad

        // Create a K-Means algorithm using given k and a square Euclidean distance as distance metric.
        var kmeans = new KMeans(4, Distance.SquareEuclidean) { Tolerance = 0.05 };
        int[] labels = kmeans.Compute(tfidf);

После этого мы делаем несколько шагов, чтобы узнать, какие документы относятся к каким группам в соответствии с метками.


c# accord.net svd
person user3819222    schedule 12.01.2016    source источник

Ответы (1)


arrow_upward
5
arrow_downward

PCA в Accord.NET уже рассчитывается с использованием SVD. Пример того, как выполнить SVD вручную, без помощи класса PCA, вы всегда можете посмотреть на странице Исходный код PrincipalComponentAnalysis.cs.

Первый шаг — вычесть среднее значение ваших данных (хранящихся в переменной x):

 int NumberOfInputs = x.Columns();
 this.Means = x.Mean(dimension: 0);
 z = x.Subtract(Means, dimension: 0);

Теперь вы можете дополнительно разделить свои данные на их стандартные отклонения, эффективно преобразовав ваши данные в z-значения. Этот шаг является необязательным, но может иметь смысл, когда ваши данные представляют переменные, собранные в единицах, сильно различающихся по порядку величины (например, один столбец представляет высоту в километрах, другой — в сантиметрах).

this.StandardDeviations = x.StandardDeviation(Means);
z = z.Divide(StandardDeviations, dimension: 0);

Теперь главные компоненты 'x' являются собственными векторами Cov(x). Таким образом, если мы вычислим SVD для 'z' (которое стандартизировано по x), столбцы матрицы V (правая часть SVD) будут основными компонентами x. Теперь нам нужно выполнить разложение по сингулярным значениям (SVD) матрицы z:

var svd = new JaggedSingularValueDecomposition(matrix,
    computeLeftSingularVectors: false,
    computeRightSingularVectors: true,
    autoTranspose: true);

var singularValues = svd.Diagonal;
var eigenvalues = SingularValues.Pow(2);
var eigenvalues.Divide(x.Rows() - 1);
var componentVectors = svd.RightSingularVectors.Transpose();

Если вы хотите выполнить отбеливание, вы также можете разделить свои векторы на единичные значения:

componentVectors = componentVectors.Divide(singularValues, dimension: 1);

Теперь, если вы хотите спроецировать свои данные до 90% дисперсии, вычислите кумулятивную сумму собственных значений аналогично тому, как вы это сделали:

// Calculate proportions
var componentProportions = eigenvalues.Abs().Divide(eigenValues.Abs().Sum());

// Calculate cumulative proportions
var componentCumulative = componentProportions.CumulativeSum();

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

int numberOfVectors = // number of vectors that you need

for (int i = 0; i < rows; i++)
    for (int j = 0; j < numberOfVectors; j++)
        for (int k = 0; k < componentVectors[j].Length; k++)
            result[i][j] += z[i][k] * componentVectors[j][k];

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

Наконец, имейте в виду, что делать все вышеперечисленное вручную совершенно необязательно. Вы действительно должны использовать класс PrincipalComponentAnalysis, чтобы сделать всю эту тяжелую работу за вас бесплатно!

person Cesar    schedule 14.09.2016