使用主成分分析进行匹配（和分析）

• 下载源代码 - 29.6 KB

引言

PCA 匹配算法分析来自 n 维的数据坐标，并返回一个表示数据主要偏差的正交坐标。

数据主要偏差的坐标表示给定坐标密度的方向。 此信息可用于最大限度地减少维度数量，同时尽可能减少数据损失，用于有损压缩。

另一种用途是排列在参数上有所不同的两组数据，例如对齐的、向后旋转/缩放/放置的形状。

背景

基于主成分分析（又名 PCA 算法）的匹配是“形状匹配框架”的一部分，该框架旨在在使用 .NET 构建绘图相似性/差异软件时提供核心支持。

该项目仅使用并依赖于“形状匹配框架”解决方案提供的矩阵库实现。 我们可以轻松地分离这两个项目/DLL，以仅获得此算法的功能。

对于此库有两种使用方法：一种是使用“普通”PCA 算法来提取绘图的坐标属性。 另一种是使用提供的匹配算法将目标绘图优化得更接近源。

使用代码

在 PCA 项目中，有一个 PCAtransform 实现，它是一个纯粹的、按部就班的实现。 这为我们提供了一组特征值和一组对应的特征向量，它们作为 DoubleMatrix 返回。 从这两个参数中，我们可以推断出两个计算输入的相对角度和相对密度。

在下面的示例中，我们将发现，使用两个 PCA 变换，可以将两组旋转的坐标识别为旋转的。

我们还将看到，两个输入的密度（与缩放相同）因子是相同的，这将指向这样一个事实：为了整合这两个输入，不应该对它们进行缩放。

请注意，如果需要缩放，请使用 PCA 变换找到的缩放因子的平方根。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;
using LiniarAlgebra;
using Adaption;
using System.Drawing;
using System.Reflection;
using PCA;

namespace New_Project
{
    static class Program
    {
        [STAThread]
        static void Main()
        {
            //Preparing rotation matrix 30 deg. counterclockwise
            double angle = Math.PI/180 * 30; //~= 0.52...
            DoubleMatrix rotationMatrix = PrepareRotationMatrix(angle);
            //rotationMatrix seems like:
            //  cos(30) -sin(30)
            //  sin(30)  cos(30)

            //This will create 2x3 matrix of zeroes
            DoubleMatrix matrix1 = new DoubleMatrix(2, 3);
            //Lets fill some data here too
            matrix1[0, 0] = 1;
            matrix1[0, 1] = 2;
            matrix1[0, 2] = 3;
            matrix1[1, 0] = 4;
            matrix1[1, 1] = 5;
            matrix1[1, 2] = 6;
            //matrix1 looks like this:
            //         1 2 3
            //         4 5 6

            //Creating a copy of the 1st matrix , this copy will be rotated
            DoubleMatrix matrix2 = new DoubleMatrix((Matrix<double>)matrix1.Clone()); 
            //now rotating it
            matrix2 = rotationMatrix * matrix2;
            //matrix2 looks like this: (same form but rotated 30 deg. c.clockwise
            //       4.10   5.24   6.39
            //      -0.37  -1.20  -2.03

            //Now we'll see that the data of both matrices has same PCA properties
            
            //Creating PCA transform instances for both martices
            PCAtransform transform1 = new PCAtransform(matrix1);
            PCAtransform transform2 = new PCAtransform(matrix2);
            //The result from calculate is a MxM dims eigenVectors matrix
            DoubleMatrix eigenVects1 = transform1.Calculate();
            DoubleMatrix eigenVects2 = transform2.Calculate();

            //It is enough for us to get the absolute 
            //angle of the first vector (the first column)
            double absAngle1 = Math.Atan(eigenVects1[1, 0] / eigenVects1[0, 0]);
            double absAngle2 = Math.Atan(eigenVects2[1, 0] / eigenVects2[0, 0]);

            //Lets see that the relative angle is the same 
            //as the rotation angle from the beginning
            double relativeAngle = absAngle2 - absAngle1; //~=0.52...
            // = -0.00000000000000011102230246251565 ~= 0 
            double anglesDiff = relativeAngle - angle;
            //Not exactly because of precision pervertion, 
            //but this is enought to get convinced

            //Another aspect of similarity is by eigenvalues 
            //(they represen the squares of the scaling factors):
            double[] eigenVals1 = transform1.EigenValues;
            //This array looks like this: 0,2
            double[] eigenVals2 = transform2.EigenValues;
            //This array looks like this: 0,2            
        }

        private static DoubleMatrix PrepareRotationMatrix(double angle)
        {
            DoubleMatrix rotationMatrix = new DoubleMatrix(2);
            rotationMatrix[0, 0] = Math.Cos(angle);
            rotationMatrix[0, 1] = -1 * Math.Sin(angle);
            rotationMatrix[1, 0] = Math.Sin(angle);
            rotationMatrix[1, 1] = Math.Cos(angle);
            return rotationMatrix;
        }
    }
}

PCA 变换也适用于数据分析和有损压缩。 由于这不是我工作的目的，这里将不作解释。 更多关于此类使用的信息可以在互联网上找到。 假设我们只想将绘图或坐标集与给定的源集进行匹配； 使用 PCA 匹配更容易完成。 我们将使用来自前一个示例的数据。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;
using LiniarAlgebra;
using System.Drawing;
using System.Reflection;
using PCA;

namespace New_Project
{
    static class Program
    {
        [STAThread]
        static void Main()
        {
            //Preparing rotation matrix 30 deg. counterclockwise
            double angle = Math.PI / 180 * 30; //~= 0.52...
            DoubleMatrix rotationMatrix = PrepareRotationMatrix(angle);
            //rotationMatrix seems like:
            //  cos(30) -sin(30)
            //  sin(30)  cos(30)

            //This will create 2x3 matrix of zeroes
            DoubleMatrix matrix1 = new DoubleMatrix(2, 3);
            //Lets fill some data here too
            matrix1[0, 0] = 1;
            matrix1[0, 1] = 2;
            matrix1[0, 2] = 3;
            matrix1[1, 0] = 4;
            matrix1[1, 1] = 5;
            matrix1[1, 2] = 6;
            //matrix1 looks like this:
            //         1 2 3
            //         4 5 6


            //Creating a copy of the 1st matrix , this copy will be rotated
            DoubleMatrix matrix2 = new DoubleMatrix((Matrix<double>)matrix1.Clone());
            //now rotating it
            matrix2 = rotationMatrix * matrix2;
            //matrix2 looks like this: (same form but rotated 30 deg. c.clockwise
            //       4.10   5.24   6.39
            //      -0.37  -1.20  -2.03

            //Preparing and calculating the matching object
            PCAMatching matching = new PCAMatching(matrix1, matrix2);
            matching.Calculate();

            //Getting the transformed data of matrix2 
            //as much as possible closer to matrix1
            DoubleMatrix result = matching.Result;
            //The result is:
            //      1   2   3
            //      4   5   6

            double calculatedAngle = matching.AngleFromSource;
            //calculatedAngle = -0.5235987755982987 the opposite to the original rotation
        }
    }
}

关注点

这个算法在某些方面开阔了我的视野。 在开始编码之前，我没有想到会有一个匹配算法能以如此大的复杂度（O(n)）来完成这项工作。 当然，它有自己的缺点，但这是一个良好的开端。

本文及所包含的项目是形状匹配框架的一部分，该框架可以在 http://sites.google.com/site/smfmproject/ 找到。 如您所见，通过一些额外的工作，它甚至可以更好地匹配形状