工作负载表征中的主成分分析高效应用-SECS 2014会议研究

0AASRI Procedia  8 ( 2014 )  68 – 740可在线获取www.sciencedirect.com02212-6716 © 2014年作者。由Elsevier B. V.出版。本是根据CCBY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。同行评议由美国应用科学研究所科学委员会负责。doi: 10.1016/j.aasri.2014.08.0120ScienceDirect02014年AASRI体育工程和计算机科学会议（SECS 2014）0主成分分析在工作负载表征中的高效应用-研究0Jyotirmoy Sarkar a , Snehanshu Saha b , Surbhi Agrawal b *0a BITS PILANI & TechMahindra,,Bangalore,560100,India0b CBIMMC & Dept. of Computer Science and Engineering,PESIT-BSC,Bangalore,560100,India0摘要0PCA是一种有用的统计技术，已在面部识别、图像压缩、维度约简、计算机系统性能分析等领域找到应用。这是一种在高维数据中寻找模式的常见技术。在本文中，我们提出主成分分析的基本思想，作为一种推广到各种流行数据分析技术的一般方法。我们阐述PCA背后的数学理论，并侧重于使用PCA算法监测系统性能。接下来，详细阐述了特征值-特征向量动态，旨在降低实验的计算成本。探讨并验证了数学理论。为了说明的目的，我们提供了算法实现细节和在实时和合成数据集上的数值示例。0关键词：PCA；特征值；特征向量；工作负载表征。0*通讯作者。电话：+91-080-66186622；传真：91-80-。电子邮件地址：snehanshusaha@pes.edu。0© 2014年作者。由Elsevier B. V.出版。本是根据CCBY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。同行评议由美国应用科学研究所科学委员会负责。1nijjjya x�� �,0ijikkjkyya a�����069  Jyotirmoy Sarkar等人。/  AASRI Procedia  8 ( 2014 )  68 – 7401. 介绍0性能评估帮助我们了解系统的表现与其他系统相比如何。工作负载是任何性能评估过程中最关键的部分。如果工作负载选择不当，整个过程可能得出错误的结论。因此，工作负载选择是性能评估项目的一个组成部分。计算机体系结构是通过在计算机上运行工作负载并测量执行时间来进行评估的。新计算机也是以同样的方式设计的。由于新设计的计算机并不存在，因此无法运行任何工作负载。这就是工作负载表征的用武之地。工作负载表征的目标是描述工作负载的性能特征，以抽象性能度量为基础，这些度量可以预测最终的性能[1]。有几种技术可以对工作负载组件进行分类。其中一种广泛使用的技术是“参数值的加权和”，它使用总和将工作负载组件分类为类别。但是，决定参数权重的有适当的指导方针。在PCA之前，运行软件的分析师通常会假设权重的值。相反，可以使用PCA来计算权重的值。PCA是一种通过将相关变量转换为较少数量的不相关变量的过程。这是一种可以将高维数据集压缩为低维数据集的数据分析技术。PCA可以从多个起点和优化标准推导出来。其中最重要的是在数据压缩中最小化均方误差，找到具有最大方差的相互正交的方向以及使用正交变换对数据进行去相关化。这些不相关的变量称为主成分。01.1. 主成分分析的工作原理:0对于给定的 n 个参数 1 { ,  2 ,... n } x x x ，主成分分析将产生一组主要因子。对新产生的集合，以下条件将成立-0� 主要因子 ( i y ) 是初始参数 ( j x ) 的线性组合。0� 主要因子集是正交集。0它是一个有序集合  1 { ,  2 ,... n } y y y  按照方差百分比的降序排列，其中  1 y   是最高的方差百分比，而  n y是最低的。因此，前几个因子可以用来分类工作负载组件。我们可以在许多领域中找到主成分分析的应用，包括数据压缩、图像处理、可视化、模式识别和时间序列预测[2]。Sirvich和Kirby在人脸表示[3-4]中有效地使用了PCA。这种方法导致任何图像的特征分解，以便可以使用部分特征图像和相应的投影到特征图像子空间来重建图像[5]。PCA方法也被用于手写体识别、人造物体识别、工业机器人和移动机器人等[6]。在工作负载组成中，选择基准非常重要。选择要包含在内的基准70 Jyotirmoy Sarkar et al. / AASRI Procedia 8 ( 2014 ) 68 – 74 11niixan���,211()1nxiisxxn���� �1()()iiababnaabbxxxxxxss���Apply the results of the theorem to choose the eigen vectors by inspection. This is possible since the matrices obtained are symmetric and the Eigen values are real and distinct. �Use the Eigen vectors to compute the principal factors. Next, we prove a theorem related to eigen values and eigen vectors. Let us take a linear map :T uv��()( )( );TxyT xT y������� where ,x yu�;,u v are vector spaces of certain dimensions,&nmsay where nm� necessarily; e.g.,nmuRvR��RTxx��� ��� , then � is an Eigen value of &Tx is a corresponding Eigen vector. 2.2. Proposition 1:For the linear map:T uv�, if the Eigen values “� “are distinct, then T admits of linearly independent Eigen vectors. Proof: Linear Independence: A set of vectors 123{ ,,,.... }nv v vv is linearly independent if � scalars12(,,....)n� ���10niiiv���� implies 01,..iin� � � � i.e.iv ; any vector in the set is NOT a linear 0基准套件称为工作负载组成。Smith [7]使用了基于Fortran语言动态程序特征的度量标准。他们使用平方欧氏距离来衡量基准之间的差异。这种程序的缺点是使用欧氏距离来衡量差异。为了克服这一点，Eeckhout等人[8]提出了主成分分析（PCA）来消除变量之间的相关性和依赖性。对一些基准测量了一些程序特征，然后应用了PCA。02. 提出的工作0PCA中计算特征值和特征向量是最耗时的部分。本文的主要目标是通过跳过特征向量的计算来节省主成分分析（PCA）的计算时间。我们建议跳过特征向量的计算，而是检查特征向量。在线性变换和向量空间的动态中理解特征值和特征向量的作用对于提高PCA在工作负载表征问题的效率起着至关重要的作用。这将要求我们证明/引用线性代数中的重要定理。02.1. 算法0计算参数的均值和标准差。0计算参数的相关性。 10在每一步计算相关矩阵的QR分解 k k k A � Q R  (从 k  � 0  开始), 其中 k Q   是正交矩阵，k R是上三角矩阵。矩阵将收敛为一个三角矩阵，称为舒尔形式。从对角线上找出矩阵的特征值。71 Jyotirmoy Sarkar et al. / AASRI Procedia 8 ( 2014 ) 68 – 74 combination of any of the other vectors in the same set e.g. 11� �� �� � & 11������� are linearly independent. Proof of the theorem: (Using the Principle of Mathematical Induction) Basis Step: 2;n � NTS 1 1221200a va vaa�����Apply1 122()(0)TT a va vT���; T linear map 1122( )()0;a T va T v���1 1 12220avav����� (1) Also 1 1 121 20avav���� (2) Therefore (1)� (2) 22122()00ava�������122(;0)v�����2100aa���; Induction hypothesis: Assume the proposition is true for nm� ; Induction steps: on 1nm�� i.e. NTS 1 111....0mmmma va vav������=>121....0.mmaaaa ������Let1 111....0mmmma va vav������ i.e. 1 111(....)(0)mmmmT a va vavT������so,1 1 1111....0mmmmmmavavav���������� (3)Also, 1 1 111 11....0mmmmavavav��������� (4)(3)� (4)�22121111()....()0mmmavav������������By the hypothesis, 1{ ,...}mvv linear independent121...0mmaaaa �������1111()0mmmav�������111(()0&0)mmv��������Therefore, the Eigen vectors 11{ ,...,}mmvvv � are Linearly Independent. Proposition 2: A real, symmetric linear map T (matrix) admits of orthogonal Eigenvectors. Proof: Well established result [9]. Conclusion of proposition: The aforementioned matrix (or the linear map, T) has distinct eigen values (as 72 Jyotirmoy Sarkar et al. / AASRI Procedia 8 ( 2014 ) 68 – 74 always the case will be) and is real, symmetric. Therefore, the corresponding eigenvectors will be linearly independent & orthogonal to each other. This enables us to find the eigenvectors by inspection rather than computing step by step via set of simultaneous equations. This saves O (n) computations, crucial computation cost!2.3. ImplicationThe paper aims to improve time complexity of PCA algorithm. The following example will illustrate the principle behind PCA from initial parameters.We have collected synthetic data of the number of packets lost on two different network links. ax is the number of packets lost on link A and bx is the number of packets lost on link B Table 1. Data for Principal Component Analysis Example 1 Observation Number ax (Variables) bx (Variables)ay (Principal factors)by(Principal factors)1 300 400 -0.0027 -0.0014 2 510 330 -0.0014 0.0028 3 212 547 -0.0021 0.0049 4 309 690 0.0028 -0.0070 5 610 410 0.0014 0.0028 6 910 150 0.0007 0.0133 7 540 320 -0.0014 0.0042 8 440 540 0.0007 -0.0021 9 219 440 -0.0037 -0.0023 10 510 779 0.0070 -0.0054 First we have to compute the mean and standard deviation using the formulas given in Algorithm 2 4 5 6 04 5 61 0ax�� ; 460046010bx��;2axs=22 4 8 3 9 8 61 04 5 64 4 9 5 8 .49��� ; 234805.5bxs�Correlation among the variables as 0.486abx xR� �and hence the correlation matrix will be 1 .0 0 00 .4 8 60 .4 8 61 .0 0 0C���� ����� (5) Now we will compute the Eigen values from the above correlation matrix using characteristic equation 10.48600.4861CI����������22(1)0.4860�����73 Jyotirmoy Sarkar et al. / AASRI Procedia 8 ( 2014 ) 68 – 74 The Eigen values are 1.486 and 0.514. 3. Results and Discussion Now, the correlation matrix in (5) is both real and symmetric and is a candidate for the theorems to be applied. Figure1 below shows the average execution time of PCA algorithm over a sample of 5 different datasets. The execution time has been recorded in milliseconds. 4. Conclusion PCA is the simplest of the true Eigenvector-based multivariate analyses. It can be used to reveal internal structure of data in a way that best explains the variance in data. PCA is sensitive to outliers in the data that produce large number of errors. So, before applying PCA it is expected to remove outliers. As a limitation the result of PCA depend on the scaling of variables. The applicability of PCA constrained by certain assumption made in derivation. Our work explores the underlying principles of PCA and exploits the inherent mathematical theory for efficient computation. The figure below conclusively shows that computation time has been reduced to achieve the same results. 02004006008001000Till�Eigen�ValueTill�Eigen�VectorFig.1. execution times of Eigen values and Eigen vectors and the time saved. References [1] T. M. Conte and W. Hwu, Benchmark Characterization,"IEEE Computer, vol. 24, no. 1, pp. 48-56, Jan. 1991. [2] Raj Jain, The Art of Computer Systems Performance Analysis, Techniques for Experimental Design, Measurement, Simulation, and Modeling. [3] Kirby and Sirovich, 1990. Application of Karhunen-Loeve Procedure for the Characterization of Human Faces. IEEE [4] Taranpreet Singh, Face Recognition Based on PCA Algorithm. [5] S Ekhe, Y Chincholkar, Improved Face Recognition using PCA & LDA [6] R Gottumukkal, V K Asari, An Improved Face Recognition Technique Based on Modular PCA Approach. 74 Jyotirmoy Sarkar et al. / AASRI Procedia 8 ( 2014 ) 68 – 74 [7] R. H. Saavedra and A. J. Smith, “Analysis of Benchmark Characteristics and Benchmark Performance Prediction,” ACM TOCS, vol. 14, no. 4, pp. 344–384, Nov. 1996. [8] L. Eeckhout, H. Vandierendonck, and K. De Bosschere, “Quantifying the Impact of Input Data Sets on Program Behavior and its Applications,” JILP, vol. 5, Feb. 2003, http://www.jilp.org/vol5 [9] Gilbert Strang, “Introduction to Linear Algebra”, 4th Edition, SIAM, 2009.