Literatura en el algoritmo para la división óptima en el cultivo de árboles de clasificación

Question

En ESL, Sección 9.7, hay un párrafo que indica que el tiempo de cómputo de un split en el crecimiento de una clasificación (o regresión) árbol típicamente escalas como $p N \log N$ donde $p$ es el número de predictores y $N$ es el número de muestras.

Un enfoque ingenuo resultados en un $pN^2$ escala, y no he sido capaz de encontrar ninguna referencia a la literatura que explica los detalles de la separación de la parte del algoritmo y cómo se logra un típico $p N \log N$ escala.

En el enfoque ingenuo el óptimo split para una variable dada, después de un primer ordenamiento de los valores observados, se buscó entre la $N-1$ de los puntos medios entre los valores observados, y el cálculo de la pérdida para cada división se puede hacer en el tiempo que las escalas como $N$.

Yo podría (y probablemente) estudiar el código fuente de algunas de las implementaciones sé, pero una literatura de referencia sería bueno $-$, en particular con respecto a la hora de la complejidad.

Answer 1

Ver mi respuesta de otra pregunta aquí. Aunque no tengo el papel de referencia, puede trivialmente encuentra que para $p$ entradas numéricas de longitud $N$ tienes que:

• iterar sobre todos los $p$ entradas: $O(p)$
• ordenar en forma ascendente cada entrada - $O(N log(N))$
• calcular 2 ejecución de las desviaciones de uno, empezando desde la izquierda y uno a partir de la derecha en el tiempo lineal - $O(N)$

El tiempo dominante para cada atributo es la ordenación del tiempo, así tenemos a $O(p N log(N))$.

Answer 2

Voy a dar una respuesta diferente, ya que es demasiado para un comentario y se trata de un enfoque más general.

Así, en la ESL, que describen, de hecho, el tiempo de cálculo para un branch-and-bound (más precisamente, se ve como un "divide y vencerás" para mí).

Se denota con a $N$ el número de observaciones y con $K$ el número de nodos hijos, cuando sembramos un árbol. Asumo que no nos suelta en la generalidad si tenemos en cuenta $K$ a ser fijo. También, podemos denotar con $f(N)$ el tiempo de procesamiento para el cómputo de los puntos de división en un nodo dado.

Por lo tanto, podemos escribir de forma recursiva la fórmula para el tiempo de ejecución como: $$T(N) = f(N) + K * T(N/K) $$ consideramos aquí que el niño nodos de dividir el conjunto de datos de entrada de tamaño $N$ $K$ subconjuntos de igual tamaño $N/K$. Sabemos que el tis es el mejor de los casos.

Sin embargo, podemos ver que este es un conocido de la aplicación de Maestro Teorema. Esto está bien documentado en la CLRS libro. Tengo la 3ª edición y los detalles están en la sección 4.5 y la prueba está en la siguiente sección. No recuerdo bien los detalles, pero recuerdo que no es demasiado complicado si uno amplía la recursividad y el grupo de algunos de los términos juntos.

Sin embargo, lo importante de este caso es que cuando $f(N)=O(N)$ - tiempo lineal, el tiempo resultante del algoritmo es $T(N) = O(N logN)$. Este tiempo se calcula para una sola variable de entrada, por lo tanto, nuestro tiempo total de $P$ variables serían $O(P N logN)$

Este tiempo es alcanzable para la siembra de árboles, si todas las entradas son clasificadas inicialmente en $O(P N logN)$, y la búsqueda de la división de valor toma el tiempo lineal en esta entradas ordenadas. Aquí podemos aplicar la línea de la varianza algoritmo, como ya he mencionado en mi respuesta anterior para $L_2 = \frac{1}{N}(y-\hat{y})^2$ . Para $L_1 = \frac{1}{N}|y-\hat{y}|$ es incluso más fácil encontrar la mediana. Confieso que nunca he probado alguna otra función de pérdida para los árboles.

Tenga en cuenta sin embargo que el Maestro Teorema se aplica para el mejor de los casos si las divisiones son iguales en tamaño. El peor caso es cuando la ruptura es muy desequilibrado. De ahí, se puede aplicar un caso diferente es el de Maestro Teorema y el tiempo se convertirá en $O(P N^2)$.

Como conclusión supongo que ESL autores utilizan el término por lo general en una forma que se utiliza para describir el rápido algoritmo de ordenación. Normalmente ordenación rápida da $O(N logN)$ tiempo de funcionamiento, teniendo peor de los casos $O(N^2)$, para algunos datos específicos de las configuraciones.

Espero te sirva de ayuda.