السلام عليكم .
بحثت فى المنتدى كله ولم اجد اى نتائج عن Singular Value Decomposition SVD ، بالرغم من اهميته فى العديد من المجالات ، فهل اى عضو هنا يعرف ما هى انسب خوارزمية لتنفيذ Singular Value Decomposition SVD لتنفيذها برمجيا ،
خوارزمية ل Singular Value Decomposition SVD
يمكن استخدام دالة ماتلاب svd
استخدامها بسيط وسهل.
باختصار هي تقوم باختصار عدد الابعاد الى اقل ما يمكن بحيث تكون الابعاد المتبقية لها اكبر تغير variance (بمعنى اخر ضغط البيانات عن طريق ازالة المتكرر). عادة تستخدم كعملية سابقة لعمليات تحليل و تنقيب البيانات.
الخلفية الرياضية لها تعتمد على المتجهات وعلى مفهوم ال eigenvectors
بالتوفيق،
ibr_exn كتب:يمكن استخدام دالة ماتلاب svd
استخدامها بسيط وسهل.
باختصار هي تقوم باختصار عدد الابعاد الى اقل ما يمكن بحيث تكون الابعاد المتبقية لها اكبر تغير variance (بمعنى اخر ضغط البيانات عن طريق ازالة المتكرر). عادة تستخدم كعملية سابقة لعمليات تحليل و تنقيب البيانات.
الخلفية الرياضية لها تعتمد على المتجهات وعلى مفهوم ال eigenvectors
بالتوفيق،
انا اعرف تماما مفهوم ال SVD وكيفية تنفيذه على الماتلاب و يدويا فى حالة الماتريكس البسيطة 2*2 و 3*3 لكن انا اسال عن خوارزمية حله ، الماتلاب يحله كيف ؟ اكيد عن طريق خوارزمية معينة وتم برمجتها ، للاسف انا بحثت كثيرا عن ذلك لكن الخوارزميات الموجودة متوفرة بدون شرح عن طريقة عملها ، مجرد اكواد برمجية فقط
The best way to be ready for the future is to invent it
d3veloper كتب:انا اعرف تماما مفهوم ال SVD وكيفية تنفيذه على الماتلاب و يدويا فى حالة الماتريكس البسيطة 2*2 و 3*3 لكن انا اسال عن خوارزمية حله ، الماتلاب يحله كيف ؟ اكيد عن طريق خوارزمية معينة وتم برمجتها ، للاسف انا بحثت كثيرا عن ذلك لكن الخوارزميات الموجودة متوفرة بدون شرح عن طريقة عملها ، مجرد اكواد برمجية فقط
اعتقد اخى الفاضل طالما انك تستطيع تنفيذ مفهوم ال SVD يدويا على المصفوفات البسيطة كما ذكرت ، فالطبيعى انك تقدر تقوم ببرمجة ما تقوم به يدويا ، وبالتالى يمكنك ايضا تعميم البرنامج ليتعامل مع المصفوفات الأكبر.
لكن عامة طالما انك تبحث عن الخوارزمية نفسها ، فعليك بالأبحاث العلمية ففيها كل ماهو متعلق بالخوارزمية واساس عملها. ارفقت لك ثلاث ابحاث هنا ، ويمكنك البحث بنفسك عن المزيد
An Improved Algorithm for Computing the Singular Value Decomposition.pdf
computing the singular value decomposition on a ring of array processors.pdf
Singular Value Decomposition and Least Squares Solutions.pdf
بالله التوفيق ،،،،
لو على ما فهمت وهو ما يسمى بال Dimensionality Reduction
فهناك طرق كثيره ,, منها ما اشار لها الأخ ابراهيم المنيه على ال Eigen Values/Vectors ,,
الخوارزميه سهله تسمى PCA = Principal Component Analysis
لو بحثت عنها فى جوجل تجد الكثير جدا ,,
لو كان هذا فعلا ما تبحث عنه :D
عماد حمدي احمد كتب:اعتقد اخى الفاضل طالما انك تستطيع تنفيذ مفهوم ال SVD يدويا على المصفوفات البسيطة كما ذكرت ، فالطبيعى انك تقدر تقوم ببرمجة ما تقوم به يدويا ، وبالتالى يمكنك ايضا تعميم البرنامج ليتعامل مع المصفوفات الأكبر.
لكن عامة طالما انك تبحث عن الخوارزمية نفسها ، فعليك بالأبحاث العلمية ففيها كل ماهو متعلق بالخوارزمية واساس عملها. ارفقت لك ثلاث ابحاث هنا ، ويمكنك البحث بنفسك عن المزيد
An Improved Algorithm for Computing the Singular Value Decomposition.pdf
computing the singular value decomposition on a ring of array processors.pdf
Singular Value Decomposition and Least Squares Solutions.pdf
بالله التوفيق ،،،،
المشكلة تكمن فى سرعة تنفيذ الخوارزمية ، الطريقة اليدوية لو تم برمجتها هاتكون بطيئة جدا على الماتريكس ذات الاحجام الكبيرة وانا بالتاكيد جربت برمجتها من قبل ، لكن ابحث عن الخورزميات اكثر كفاءة مثل التى يعمل بها الماتلاب بالرغم من وجود ال Source Code كامل لها ، لكن ابحث عن شرح لهم و عن طريقة عملهم .
ثانيا اشكرك على الملفات ، اتمنى اجد فيها ما ابحث عنه
The best way to be ready for the future is to invent it
السلام عليكم
الأخوة الكرام بارك الله فيكم
ما هى الطريقية اليدوية لحساب SVD
فمعادلته تكون بالشكل
A = USV
ولكن كيف يحسب يدويا
وشكرا لكم
" وما توفيقى إلا بالله عليه توكلت وإليه أنيب "
-------------------------------------------------
قل : " لا حول ولا قوة إلا بالله "
-------------------------------------------------
هذا الرابط يساعدك على كيفية الحل يدويا :
وهذا لحل الماتريكس عمليا ، تم برمجته عن طريق الجافا سكريبت :happy:
http://users.telenet.be/paul.larmuseau/SVD.htm
وهذا عن طريق الجافا:
http://ocw.mit.edu/ans7870/18/18.06/javademo/SVD/index.html
اذا كنت تبحث ان الخوارزمية التى يعمل بها الماتلاب فى الاساس هى :
http://www.netlib.org/lapack/index.html
وهذا بعض المكتبات الاخرى التى تدعم ال SVD ولاكثر من لغة برمجة ، وانا ارشح ال C او ++C او Java
http://tedlab.mit.edu/~dr/SVDLIBC/
http://stitchpanorama.sourceforge.net/Python/svd.py
http://alias-i.com/lingpipe/demos/tutorial/svd/read-me.html
وهناك كتاب اسمه : Numerical Recipes in C++ The Art of Scientific Computing 3rd Ed
اكثر من رائع انصحك به بشده
وشكرا ...
تم تعديل هذه المشاركة بواسطة d3veloper في 24 نوفمبر 2010 في 13:00
The best way to be ready for the future is to invent it
السلام عليكم
جزاك الله خير على الروابط وهى مفيدة بإذن الله تعالى
ولكن هل هناك دالة مكتوبة بكود ال PHP تقوم بتنفيذ SVD ؟؟
شكرا لكم وبارك الله فيكم
" وما توفيقى إلا بالله عليه توكلت وإليه أنيب "
-------------------------------------------------
قل : " لا حول ولا قوة إلا بالله "
-------------------------------------------------
اا الفاروق اا كتب:السلام عليكم
جزاك الله خير على الروابط وهى مفيدة بإذن الله تعالى
ولكن هل هناك دالة مكتوبة بكود ال PHP تقوم بتنفيذ SVD ؟؟
شكرا لكم وبارك الله فيكم
<?php
/**
* @author Yehia Abed
* @copyright 2010
*/
class Matrix {
/**
* matrixMultiplication
*
* @param array $matrixA
* @param array $matrixB
* @return array
*/
public function matrixMultiplication($matrixA, $matrixB){
$rowsA = count($matrixA);
$colsA = count($matrixA[0]);
$rowsB = count($matrixB);
$colsB = count($matrixB[0]);
if($colsA == $rowsB){
for($i = 0; $i < $rowsA; $i++){
for($j = 0; $j < $colsB; $j++){
for($p = 0; $p < $colsA; $p++){
$matrixProduct[$i][$j] += $matrixA[$i][$p] * $matrixB[$p][$j];
}
}
}
}else {
echo "Matrix Multiplication can not be done !";
}
return $matrixProduct;
}
/**
* matrixTranspose
*
* @param array $matrix
* @return array
*/
public function matrixTranspose($matrix){
$m = count($matrix);
$n = count($matrix[0]);
for($i = 0; $i < $n; $i++){
for($j = 0; $j < $m; $j++){
$matrixT[$i][$j] = $matrix[$j][$i];
}
}
return $matrixT;
}
/**
* matrixRound
*
* @param array $matrix
* @return array
*/
public function matrixRound($matrix){
$m = count($matrix);
$n = count($matrix[0]);
for($i = 0; $i < $m; $i++){
for($j = 0; $j < $n; $j++){
$matrixT[$i][$j] = round($matrix[$i][$j], 2);
}
}
return $matrixT;
}
/**
* matrixConstruct
*
* @param array $matrix
* @param integer $rows
* @param integer $columns
* @return array
*/
public function matrixConstruct($matrix, $rows, $columns){
for($i = 0; $i < $rows; $i++){
for($j = 0; $j < $columns; $j++){
$neoMatrix[$i][$j] = $matrix[$i][$j];
}
}
return $neoMatrix;
}
/**
* sameSign
*
* @param integer $a
* @param integer $b
* @return integer
*/
private function sameSign($a, $b){
if($b >= 0){
$result = abs($a);
}else {
$result = - abs($a);
}
return $result;
}
/**
* maximum
*
* @param integer $a
* @param integer $b
* @return integer
*/
private function maximum($a, $b){
if($a < $b){
return $b;
}else {
return $a;
}
}
/**
* minimum
*
* @param integer $a
* @param integer $b
* @return integer
*/
private function minimum($a, $b){
if($a > $b){
return $b;
}else {
return $a;
}
}
/**
* pythag
*
* @param integer $a
* @param integer $b
* @return integer
*/
private function pythag($a, $b){
$absa = abs($a);
$absb = abs($b);
if( $absa > $absb ){
return $absa * sqrt( 1.0 + pow( $absb / $absa , 2) );
}else {
if( $absb > 0.0 ){
return $absb * sqrt( 1.0 + pow( $absa / $absb, 2 ) );
}else {
return 0.0;
}
}
}
/**
* SVD
*
* @param array $matrix
* @return array
*/
public function SVD($matrix){
$m = count($matrix);
$n = count($matrix[0]);
$U = $this->matrixConstruct($matrix, $m, $n);
$V = $this->matrixConstruct($matrix, $n, $n);
$eps = 2.22045e-016;
// Decompose Phase
// Householder reduction to bidiagonal form.
$g = $scale = $anorm = 0.0;
for($i = 0; $i < $n; $i++){
$l = $i + 2;
$rv1[$i] = $scale * $g;
$g = $s = $scale = 0.0;
if($i < $m){
for($k = $i; $k < $m; $k++) $scale += abs($U[$k][$i]);
if($scale != 0.0) {
for($k = $i; $k < $m; $k++) {
$U[$k][$i] /= $scale;
$s += $U[$k][$i] * $U[$k][$i];
}
$f = $U[$i][$i];
$g = - $this->sameSign(sqrt($s), $f);
$h = $f * $g - $s;
$U[$i][$i] = $f - $g;
for($j = $l - 1; $j < $n; $j++){
for($s = 0.0, $k = $i; $k < $m; $k++) $s += $U[$k][$i] * $U[$k][$j];
$f = $s / $h;
for($k = $i; $k < $m; $k++) $U[$k][$j] += $f * $U[$k][$i];
}
for($k = $i; $k < $m; $k++) $U[$k][$i] *= $scale;
}
}
$W[$i] = $scale * $g;
$g = $s = $scale = 0.0;
if($i + 1 <= $m && $i + 1 != $n){
for ($k= $l - 1; $k < $n; $k++) $scale += abs($U[$i][$k]);
if($scale != 0.0){
for ($k= $l - 1; $k < $n; $k++){
$U[$i][$k] /= $scale;
$s += $U[$i][$k] * $U[$i][$k];
}
$f = $U[$i][$l - 1];
$g = - $this->sameSign(sqrt($s), $f);
$h = $f * $g - $s;
$U[$i][$l - 1] = $f - $g;
for($k = $l - 1; $k < $n; $k++) $rv1[$k] = $U[$i][$k] / $h;
for($j = $l - 1; $j < $m; $j++){
for($s = 0.0, $k = $l - 1; $k < $n; $k++) $s += $U[$j][$k] * $U[$i][$k];
for($k = $l - 1; $k < $n; $k++) $U[$j][$k] += $s * $rv1[$k];
}
for($k= $l - 1; $k < $n; $k++) $U[$i][$k] *= $scale;
}
}
$anorm = $this->maximum($anorm, (abs($W[$i]) + abs($rv1[$i])));
}
// Accumulation of right-hand transformations.
for($i = $n - 1; $i >= 0; $i--){
if($i < $n - 1){
if($g != 0.0){
for($j = $l; $j < $n; $j++) // Double division to avoid possible underflow.
$V[$j][$i] = ($U[$i][$j] / $U[$i][$l]) / $g;
for($j = $l; $j < $n; $j++){
for($s = 0.0, $k = $l; $k < $n; $k++) $s += ($U[$i][$k] * $V[$k][$j]);
for($k = $l; $k < $n; $k++) $V[$k][$j] += $s * $V[$k][$i];
}
}
for($j = $l; $j < $n; $j++) $V[$i][$j] = $V[$j][$i] = 0.0;
}
$V[$i][$i] = 1.0;
$g = $rv1[$i];
$l = $i;
}
// Accumulation of left-hand transformations.
for($i = $this->minimum($m, $n) - 1; $i >= 0; $i--){
$l = $i + 1;
$g = $W[$i];
for($j = $l; $j < $n; $j++) $U[$i][$j] = 0.0;
if($g != 0.0){
$g = 1.0 / $g;
for($j = $l; $j < $n; $j++){
for($s = 0.0, $k = $l; $k < $m; $k++) $s += $U[$k][$i] * $U[$k][$j];
$f = ($s / $U[$i][$i]) * $g;
for($k = $i; $k < $m; $k++) $U[$k][$j] += $f * $U[$k][$i];
}
for($j = $i; $j < $m; $j++) $U[$j][$i] *= $g;
}else {
for($j = $i; $j < $m; $j++) $U[$j][$i] = 0.0;
}
++$U[$i][$i];
}
// Diagonalization of the bidiagonal form
// Loop over singular values, and over allowed iterations.
for($k = $n - 1; $k >= 0; $k--){
for($its = 0; $its < 30; $its++){
$flag = true;
for($l = $k; $l >= 0; $l--){
$nm = $l - 1;
if( $l == 0 || abs($rv1[$l]) <= $eps*$anorm){
$flag = false;
break;
}
if(abs($W[$nm]) <= $eps*$anorm) break;
}
if($flag){
$c = 0.0; // Cancellation of rv1[l], if l > 0.
$s = 1.0;
for($i = $l; $i < $k + 1; $i++){
$f = $s * $rv1[$i];
$rv1[$i] = $c * $rv1[$i];
if(abs($f) <= $eps*$anorm) break;
$g = $W[$i];
$h = $this->pythag($f,$g);
$W[$i] = $h;
$h = 1.0 / $h;
$c = $g * $h;
$s = -$f * $h;
for($j = 0; $j < $m; $j++){
$y = $U[$j][$nm];
$z = $U[$j][$i];
$U[$j][$nm] = $y * $c + $z * $s;
$U[$j][$i] = $z * $c - $y * $s;
}
}
}
$z = $W[$k];
if($l == $k){
if($z < 0.0){
$W[$k] = -$z; // Singular value is made nonnegative.
for($j = 0; $j < $n; $j++) $V[$j][$k] = -$V[$j][$k];
}
break;
}
if($its == 29) print("no convergence in 30 svd iterations");
$x = $W[$l]; // Shift from bottom 2-by-2 minor.
$nm = $k - 1;
$y = $W[$nm];
$g = $rv1[$nm];
$h = $rv1[$k];
$f = (($y - $z) * ($y + $z) + ($g - $h) * ($g + $h)) / (2.0 * $h * $y);
$g = $this->pythag($f,1.0);
$f = (($x - $z) * ($x + $z) + $h * (($y / ($f + $this->sameSign($g,$f))) - $h)) / $x;
$c = $s = 1.0;
for($j = $l; $j <= $nm; $j++){
$i = $j + 1;
$g = $rv1[$i];
$y = $W[$i];
$h = $s * $g;
$g = $c * $g;
$z = $this->pythag($f,$h);
$rv1[$j] = $z;
$c = $f / $z;
$s = $h / $z;
$f = $x * $c + $g * $s;
$g = $g * $c - $x * $s;
$h = $y * $s;
$y *= $c;
for($jj = 0; $jj < $n; $jj++){
$x = $V[$jj][$j];
$z = $V[$jj][$i];
$V[$jj][$j] = $x * $c + $z * $s;
$V[$jj][$i] = $z * $c - $x * $s;
}
$z = $this->pythag($f,$h);
$W[$j] = $z; // Rotation can be arbitrary if z = 0.
if($z){
$z = 1.0 / $z;
$c = $f * $z;
$s = $h * $z;
}
$f = $c * $g + $s * $y;
$x = $c * $y - $s * $g;
for($jj = 0; $jj < $m; $jj++){
$y = $U[$jj][$j];
$z = $U[$jj][$i];
$U[$jj][$j] = $y * $c + $z * $s;
$U[$jj][$i] = $z * $c - $y * $s;
}
}
$rv1[$l] = 0.0;
$rv1[$k] = $f;
$W[$k] = $x;
}
}
// Reorder Phase
// Sort. The method is Shell's sort.
// (The work is negligible as compared to that already done in decompose phase.)
$inc = 1;
do {
$inc *= 3;
$inc++;
} while($inc <= $n);
do {
$inc /= 3;
for($i = $inc; $i < $n; $i++){
$sw = $W[$i];
for($k = 0; $k < $m; $k++) $su[$k] = $U[$k][$i];
for($k = 0; $k < $n; $k++) $sv[$k] = $V[$k][$i];
$j = $i;
while($W[$j - $inc] < $sw){
$W[$j] = $W[$j - $inc];
for($k = 0; $k < $m; $k++) $U[$k][$j] = $U[$k][$j - $inc];
for($k = 0; $k < $n; $k++) $V[$k][$j] = $V[$k][$j - $inc];
$j -= $inc;
if($j < $inc) break;
}
$W[$j] = $sw;
for($k = 0; $k < $m; $k++) $U[$k][$j] = $su[$k];
for($k = 0; $k < $n; $k++) $V[$k][$j] = $sv[$k];
}
} while($inc > 1);
for($k = 0; $k < $n; $k++){
$s = 0;
for($i = 0; $i < $m; $i++) if ($U[$i][$k] < 0.0) $s++;
for($j = 0; $j < $n; $j++) if ($V[$j][$k] < 0.0) $s++;
if($s > ($m + $n)/2) {
for($i = 0; $i < $m; $i++) $U[$i][$k] = - $U[$i][$k];
for($j = 0; $j < $n; $j++) $V[$j][$k] = - $V[$j][$k];
}
}
// calculate the rank
for($i = 0; $i < count($W); $i++){
if(round($W[$i], 4) > 0){
$rank += 1;
}
}
// Low-Rank Approximation
$q = 0.9;
$k = 0;
for($i = 0; $i < $rank; $i++) $frobA += $W[$i];
do{
for($i = 0; $i <= $k; $i++) $frobAk += $W[$i];
$clt = $frobAk / $frobA;
$k++;
} while($clt < $q);
// prepare S matrix as n*n daigonal matrix of singular values
for($i = 0; $i < $n; $i++){
for($j = 0; $j < $n; $j++){
$S[$i][$j] = 0;
$S[$i][$i] = $W[$i];
}
}
$matrices['U'] = $U;
$matrices['S'] = $S;
$matrices['W'] = $W;
$matrices['V'] = $this->matrixTranspose($V);
$matrices['Rank'] = $rank;
$matrices['K'] = $k;
return $matrices;
}
}
// input matrix
$matrix = array(array('0.00', '0.00', '0.56', '0.56'. '0.00', '0.00', '1.00'),
array('0.49', '0.71', '0.00', '0.00'. '0.00', '0.71', '0.00'),
array('0.49', '0.71', '0.00', '0.00'. '0.00', '0.71', '0.00'),
array('0.72', '0.00', '0.00', '0.00'. '1.00', '0.00', '0.00'),
array('0.00', '0.00', '0.83', '0.83'. '0.00', '0.00', '0.00'));
/*
$matrix = array(array('22', '10', '2', '3', '7'),
array('14', '7', '10', '0', '8'),
array('-1', '13', '-1', '-11', '3'),
array('-3', '-2', '13', '-2', '4'),
array('9', '8', '1', '-2', '4'),
array('9', '1', '-7', '5', '-1'),
array('2', '-6', '6', '5', '1'),
array('4', '5', '0', '-2', '2'));
*/
//$matrix = array(array('1', '-1'), array('0', '1'), array('1', '0'), array('-1', '1'));
//$matrix = array(array('4', '0'), array('3', '-5'));
$matrixClass = new Matrix;
// start time
$startTime = round(microtime(true),4);
// run SVD for input matrix
$USV = $matrixClass->svd($matrix);
// end time
$endTime = round(microtime(true),4);
// calculate process time
$processTime = substr(($endTime - $startTime),0,5);
// calculate input matrix
$input = $matrixClass->matrixMultiplication($USV['U'] ,$matrixClass->matrixMultiplication($USV['S'], $USV['V']));
$input = $matrixClass->matrixRound($input);
$Uk = $matrixClass->matrixConstruct($USV['U'], count($USV['U']), $USV['K']);
$Ukt = $matrixClass->matrixTranspose($Uk);
for($i = 0; $i < count($Ukt); $i++){
for($j = 0; $j < count($Ukt[0]); $j++){
$tokensResults[$j] += $Ukt[$i][$j];
}
}
echo "Matrix U:";
echo "<br/>";
print_r($matrixClass->matrixRound($USV['U']));
echo "<br/><br/>";
echo "Matrix Uk:";
echo "<br/>";
print_r($matrixClass->matrixRound($Uk));
echo "<br/><br/>";
echo "Matrix Uk^t:";
echo "<br/>";
print_r($matrixClass->matrixRound($Ukt));
echo "<br/><br/>";
echo "Results:";
echo "<br/>";
print_r($tokensResults);
echo "<br/><br/>";
echo "Matrix S:";
echo "<br/>";
print_r($matrixClass->matrixRound($USV['S']));
echo "<br/><br/>";
echo "Matrix V^t:";
echo "<br/>";
print_r($matrixClass->matrixRound($USV['V']));
echo "<br/><br/>";
echo "processTime = ".$processTime;
echo "<br/><br/>";
echo "Input Matrix:";
echo "<br/>";
print_r($input);
echo "<br/><br/>";
echo "Rank:";
echo "<br/>";
print_r($USV['Rank']);
echo "<br/><br/>";
echo "K:";
echo "<br/>";
print_r($USV['K']);
echo "<br/><br/>";
?>اى خدمة اخرى ؟ :sleep:
The best way to be ready for the future is to invent it
السلام عليكم
الاخ d3veloper جزاك الله خير
على السرعة والكود
وساجربه واوافيك بالرد ان شاء الله تعالى
" وما توفيقى إلا بالله عليه توكلت وإليه أنيب "
-------------------------------------------------
قل : " لا حول ولا قوة إلا بالله "
-------------------------------------------------