Singular Value Decomposition (SVD) em PHP

Question

Eu gostaria de implementar decomposição singular do valor (SVD) em PHP. Eu sei que existem várias bibliotecas externas que poderia fazer isso por mim. Mas eu tenho duas questões relativas PHP, no entanto: 1) Você acha que é possível e / ou razoável para codificar o SVD em PHP? 2) Se (1) é sim: Você pode me ajudar com o código-lo em PHP

?

Eu já codificado algumas partes da SVD sozinho. Aqui está o código que fiz comentários para o curso de ação. Algumas peças deste código não são completamente correto.

Seria ótimo se você pudesse me ajudar. Muito obrigado antecipadamente!

Answer 1

SVD-python É um muito claro de implementação, parcimoniosa da SVD. É praticamente psuedocode e deve ser bastante fácil de entender e comparar / desenhar para sua implementação php, mesmo se você não sabe muito python.

SVD-python

Dito isso, como os outros eu não seria de esperar para ser capaz de fazer LSA muito pesado com a implementação php que soa como uma web-host muito limitado.

Felicidades

Edit: O módulo acima não faz nada por si só, mas há um exemplo incluído no comentários de abertura. Supondo que você baixou o módulo python, e foi acessíveis (por exemplo, na mesma pasta), você poderia implementar um exemplo trivial como segue,

#!/usr/bin/python
import svd
import math

a = [[22.,10., 2.,  3., 7.],
     [14., 7.,10.,  0., 8.],
     [-1.,13.,-1.,-11., 3.],
     [-3.,-2.,13., -2., 4.],
     [ 9., 8., 1., -2., 4.],
     [ 9., 1.,-7.,  5.,-1.],
     [ 2.,-6., 6.,  5., 1.],
     [ 4., 5., 0., -2., 2.]]

u,w,vt = svd.svd(a)
print w

Aqui 'w' contém sua lista de valores singulares.
Claro que isso só faz com que você parte do caminho para análise semântica latente e seus parentes. Você geralmente querem reduzir o número de valores singulares, então empregar alguma distância apropriada métrica para medir a similaridade entre os seus documentos, ou palavras, ou documentos e palavras, etc. O co-seno do ângulo entre os vetores resultantes é bastante popular.

semântica latente Mapping (pdf)

é de longe o, mais concisa e papel informativo mais clara que eu li sobre os restantes passos você necessidade de trabalhar para fora após a SVD.

Edit2: Também note que se você estiver trabalhando com matrizes termo-documento muito grandes (Estou assumindo que este é o que está fazendo) é quase certamente vai ser muito mais eficiente para realizar a decomposição em modo offline, e em seguida, executar apenas as comparações de forma ao vivo em resposta a pedidos. enquanto svd-python é grande para a aprendizagem, o svdlibc é mais o que você gostaria de tão pesada computação.

Finalmente, como mencionado no papel bellegarda acima, lembre-se que você não tem que recalcular o SVD cada vez que você começa um novo documento ou solicitação. dependendo do que você está tentando fazer você poderia provavelmente fugir com a realização do svd uma vez por semana ou assim, em modo offline, uma máquina local, e, em seguida, enviar os resultados (tamanho / largura de banda preocupações não obstante).

de qualquer maneira boa sorte!

Answer 2

Tenha cuidado quando você diz "Eu não ligo para o que os prazos são". SVD é uma operação O(N^3) (ou O(MN^2) se é uma matriz m*n retangular) o que significa que você pode muito facilmente ser em uma situação onde o problema pode levar um tempo muito longo. Se o caso de 100 * 100 leva um minuto, o caso 1000 * 1000 seria 10 ^ 3 minutos, ou cerca de 17 horas (e, provavelmente, pior, de forma realista, como é provável que você estar fora de cache). Com algo como PHP, o prefactor -. O número multiplicando a N^3 a fim de calcular a contagem FLOP necessário, poderia ser muito, muito grande

Dito isto, é claro que é possível código-lo em PHP - a língua tem as estruturas e operações de dados necessários.

Answer 3

Eu sei que este é um velho Q, mas aqui é a minha 2-bits:

1) Um verdadeiro SVD é muito mais lenta do que as aproximações de inspiração de cálculo utilizados, por exemplo, no prémio Netflix. Veja: http://www.sifter.org/~simon/journal/20061211.html

Há uma implementação (em C) aqui: http://www.timelydevelopment.com/demos/NetflixPrize.aspx

2) C seria mais rápido, mas PHP pode certamente fazê-lo.

PHP Architect autor Cal Evans: "PHP é uma linguagem de scripting web ... [mas] eu usei PHP como uma linguagem de script para escrever o equivalente DOS de arquivos em lote ou o equivalente Linux de scripts shell tenho. descobriu que a maioria do que eu preciso fazer pode ser feito de dentro do PHP. Existe ainda um projeto para que você possa construir aplicações desktop via PHP, o projeto PHP-GTK ".

Answer 4

Quanto à pergunta 1: Ele definitivamente é possível. Se é razoável depende do seu cenário: Como grande são as suas matrizes? Quantas vezes você pretende executar o código? É executado em um web site ou a partir da linha de comando? Se você se preocupam com velocidade, gostaria de sugerir escrever uma simples extensão que envolve chamadas para o GNU Scientific Library .

Answer 5

Sim, é posible, mas a implementação SVD em php ins't a abordagem ideal. Como você pode ver aqui PHP é mais lento do que C, e também mais lento do que C ++, então talvez fosse melhor se você pudesse fazê-lo em uma dessas línguas e chamá-los como uma função para obter seus resultados. Você pode encontrar uma implementação do algoritmo aqui , para que pode guiar-se através dela.

Sobre a função de chamada pode usar:

• O exec () Função

A função do sistema é bastante útil e poderosa, mas um dos maiores problemas com ele é que todo o texto resultante do programa vai diretamente para o fluxo de saída. Haverá situações em que você gostaria de formatar o texto resultante e exibi-lo de alguma forma diferente, ou não exibi-lo em tudo.

• O sistema () Função

A função de sistema em PHP usa um argumento string com o comando a ser executado, bem como quaisquer argumentos você deseja passados ??para esse comando. Esta função executa o comando especificado, e despeja qualquer texto resultante para o fluxo de saída (ou a saída HTTP em uma situação de servidor web, ou o console se você estiver rodando o PHP como uma ferramenta de linha de comando). O retorno desta função é a última linha de saída do programa, se ele emite saída de texto.

• O passthru () Função

Uma função fascinante que PHP fornece semelhantes aos que vimos até agora é a função de intermediário. Esta função, como os outros, executa o programa que você diga a ele. No entanto, ele então começa a enviar imediatamente a saída crua deste programa para o fluxo de saída com o qual o PHP está trabalhando atualmente (isto é, ou HTTP em um cenário de servidor web, ou o shell em uma versão de linha de comando do PHP).

Answer 6

1. Sim. isso é perfeitamente possível de ser implementado em PHP. Eu não sei o que o prazo razoável para execução e quão grande ele pode calcular. Eu provavelmente teria que implementar o algoritmo para ter uma idéia rought.

2. Sim, eu posso ajudá-lo a codificá-lo. Mas por que você precisa de ajuda? não o código que você escreveu trabalho?

Assim como uma questão de lado. Qual versão do PHP você usa?