Algorithme pour surveiller dynamiquement les quantiles

Je veux estimer le quantile de certaines données. Les données sont si énormes qu'elles ne peuvent pas être stockées dans la mémoire. Et les données ne sont pas statiques, de nouvelles données continuent d'arriver. Quelqu'un connaît-il un algorithme pour surveiller les quantiles des données observées jusqu'à présent avec une mémoire et des calculs très limités? Je trouve l' algorithme P2 utile, mais il ne fonctionne pas très bien pour mes données, qui sont distribuées de manière extrêmement lourde.

L'algorithme P2 est une belle trouvaille. Il fonctionne en faisant plusieurs estimations du quantile, en les mettant à jour périodiquement et en utilisant une interpolation quadratique (non linéaire, non cubique) pour estimer le quantile. Les auteurs affirment que l'interpolation quadratique fonctionne mieux dans les queues que l'interpolation linéaire et que le cubisme deviendrait trop difficile et difficile.

Vous n'indiquez pas exactement comment cette approche échoue pour vos données "lourdes", mais il est facile de deviner: les estimations des quantiles extrêmes pour les distributions lourdes seront instables jusqu'à ce qu'une grande quantité de données soit collectée. Mais cela va être un problème (dans une moindre mesure) même si vous deviez stocker toutes les données, alors ne vous attendez pas à des miracles!

Quoi qu'il en soit, pourquoi ne pas définir des marqueurs auxiliaires - appelons-les et sein desquels vous êtes certain que le quantile se situera et stocker toutes les données situées entre et ? Lorsque votre tampon se remplira, vous devrez mettre à jour ces marqueurs, en conservant toujours . Un algorithme simple pour ce faire peut être conçu à partir d'une combinaison de (a) l'estimation P2 actuelle du quantile et (b) des comptages stockés du nombre de données inférieur à et du nombre de données supérieur à . De cette façon, vous pouvez, avec une grande certitude, estimer le quantile aussi bien que si vous aviez l'ensemble de données toujours disponible, mais vous n'avez besoin que d'un tampon relativement petit.x 6 x 0 x 6 x 0 ≤ x 6 x 0 x $x_0$$x_6$$x_0$$x_6$$x_0 \le x_6$$x_0$$x_6$

Plus précisément, je propose une structure de données pour conserver des informations partielles sur une séquence de valeurs de données . Ici, est une liste chaînéen x 1 , x 2 , … , x n $(k, \mathbf{y}, n)$$n$$x_1, x_2, \ldots, x_n$$\mathbf{y}$

Dans cette notation, désigne l' plus petite des valeurs lues jusqu'ici. est une constante, la taille du tampon . i th n x m $x^{(n)}_{[i]}$$i^\text{th}$$n$ $x$$m$$\mathbf{y}$

L'algorithme commence par remplir avec les premières valeurs de données rencontrées et les placer dans l'ordre trié, du plus petit au plus grand. Soit le quantile à estimer; par exemple, = 0,99. En lisant il y a trois actions possibles: m q q x n + $\mathbf{y}$$m$$q$$q$$x_{n+1}$

• Si , incrémenter .$x_{n+1} \lt x^{(n)}_{[k+1]}$$k$

• Si , ne faites rien.$x_{n+1} \gt x^{(n)}_{[k+m]}$

• Sinon, insérez dans .$x_{n+1}$$\mathbf{y}$

Dans tous les cas, incrémentez .$n$

La procédure d' insertion place dans dans l'ordre trié, puis élimine l'une des valeurs extrêmes de : y $x_{n+1}$$\mathbf{y}$$\mathbf{y}$

• Si , alors supprimez de et incrémentez ;x ( n ) [ k + 1 ] y$k + m/2 \lt n q$$x^{(n)}_{[k+1]}$$\mathbf{y}$$k$

• Sinon, supprimez de .$x^{(n)}_{[k+m]}$$\mathbf{y}$

À condition que soit suffisamment grand, cette procédure mettra entre parenthèses le vrai quantile de la distribution avec une probabilité élevée. À tout stade il peut être estimé de la manière habituelle en termes de et , qui se trouvera probablement dans . (Je crois que ne doit être mis à l'échelle que comme la racine carrée de la quantité maximale de données ( ), mais je n'ai pas effectué d'analyse rigoureuse pour le prouver.) Quoi qu'il en soit, l'algorithme détectera s'il a réussi (par comparer et à ).n x ( n ) [ ⌊ q n ⌋ ] x ( n ) [ ⌈ q n ⌉ ] y m N k / n ( k + $m$$n$$x^{(n)}_{[\lfloor{q n}\rfloor]}$$x^{(n)}_{[\lceil{q n}\rceil]}$$\mathbf{y}$$m$$N$$k/n$$(k+m)/n$$q$

Un test avec jusqu'à 100 000 valeurs, en utilisant et (le cas le plus difficile) indique que cet algorithme a un taux de réussite de 99,5% pour obtenir la valeur correcte de . Pour un flux de valeurs, cela nécessiterait un tampon de seulement deux millions (mais trois ou quatre millions seraient un meilleur choix). L'utilisation d'une liste triée à double lien pour le tampon nécessite = effort tout en identifiant et en supprimant le max ou le min sont des opérations . L'insertion relativement coûteuse doit généralement être effectuée uniquement q=0,5x ( n ) [ ⌊ q n ⌋ ] N=10$m = 2\sqrt{N}$$q=.5$$x^{(n)}_{[\lfloor{q n}\rfloor]}$$N=10^{12}$O(log(N))O$O(\log(\sqrt{N}))$$O(\log(N))$O ( $O(1)$$O(\sqrt{N})$fois. Ainsi, les coûts de calcul de cet algorithme sont dans le temps et dans le stockage.O($O(N + \sqrt{N} \log(N)) = O(N)$$O(\sqrt{N})$

Je pense que la suggestion de whuber est excellente et j'essaierais d'abord. Cependant, si vous trouvez que vous ne pouvez vraiment pas accueillir le stockage ou que cela ne fonctionne pas pour une autre raison, voici une idée pour une généralisation différente de P2. Ce n'est pas aussi détaillé que ce que suggère Whuber - plus comme une idée de recherche plutôt que comme une solution.$O(\sqrt N)$

Au lieu de suivre les quantiles à , , , et , comme le suggère l'algorithme P2 d'origine, vous pouvez simplement suivre plus de quantiles (mais toujours un nombre constant). Il semble que l'algorithme le permette de manière très simple; tout ce que vous avez à faire est de calculer le "bucket" correct pour les points entrants, et la bonne façon de mettre à jour les quantiles (en utilisant de façon quadratique des nombres adjacents).p / 2 p ( 1 + p ) / 2 $0$$p/2$$p$$(1+p)/2$$1$

Disons que vous gardez une trace de points. Vous pouvez essayer de suivre le quantile à , , , , , , , , (en choisissant les points de manière équidistante entre et , et entre et ), ou même en utilisant nœuds Chebyshev de la forme et . Si0 p / 12 ... p ⋅ 11 / 12 p p + ( 1 - p ) / 12 ... p + 11 ⋅ ( 1 - p ) / 12 1 0 p p 1 22 p / 2 ⋅ ( 1 + cos ( 2 i - 1 ) $25$$0$$p/12$$\dotsc$$p \cdot 11/12$$p$$p + (1-p)/12$$\dotsc$$p + 11\cdot(1-p)/12$$1$$0$$p$$p$$1$$22$ $p/2 \cdot (1 + \cos \frac{(2 i - 1)\pi}{22})$$p + (1 - p)/2 \cdot (1 + \cos \frac{(2i-1)\pi}{22})$$p$est proche de ou , vous pouvez essayer de mettre moins de points du côté où il y a moins de masse de probabilité et plus de l'autre côté.$0$$1$

Si vous décidez de poursuivre, je (et éventuellement d'autres sur ce site) serais intéressé de savoir si cela fonctionne ...

Press et al., Numerical Recipes 8.5.2 "Estimation en un seul passage de quantiles arbitraires" p. 435, donnez un IQAgent de classe c ++ qui met à jour un cdf approximatif linéaire par morceaux.

Cela peut être adapté à partir d'algorithmes qui déterminent la médiane d'un ensemble de données en ligne. Pour plus d'informations, consultez ce post stackoverflow - /programming/1387497/find-median-value-from-a-growing-set

Je regarderais la régression quantile. Vous pouvez l'utiliser pour déterminer une estimation paramétrique des quantiles que vous souhaitez examiner. Il ne fait aucune hypothèse concernant la normalité, il gère donc assez bien l'hétéroscédasticité et peut être utilisé sur une base de fenêtre mobile. Il s'agit essentiellement d'une régression pénalisée L1-Norm, donc ce n'est pas trop intensif numériquement et il y a des packages R, SAS et SPSS assez complets, ainsi que quelques implémentations matlab. Voici les wikis principaux et le package R pour plus d'informations.

Édité:

Découvrez le lien croisé d'échange de pile mathématique: Quelqu'un a cité quelques articles qui présentent essentiellement l'idée très simple d'utiliser simplement une fenêtre mobile de statistiques d'ordre pour estimer les quantiles. Littéralement, tout ce que vous avez à faire est de trier les valeurs du plus petit au plus grand, de sélectionner le quantile souhaité et de sélectionner la valeur la plus élevée dans ce quantile. Vous pouvez évidemment accorder plus de poids aux observations les plus récentes si vous pensez qu'elles sont plus représentatives des conditions actuelles. Cela donnera probablement des estimations approximatives, mais c'est assez simple à faire et vous n'avez pas à passer par les mouvements de levage lourd quantitatif. Juste une pensée.

Il est possible d'estimer (et de suivre) les quantiles en ligne (il en va de même pour les paramètres d'une régression quantile). En substance, cela se résume à une descente de gradient stochastique sur la fonction de vérification-perte qui définit la régression quantile (les quantiles étant représentés par un modèle ne contenant qu'une interception), par exemple en mettant à jour les paramètres inconnus au fur et à mesure que les observations arrivent.

Voir l'article de Bell Labs "Incremental Quantile Estimation for Massive Tracking" ( ftp://ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/kdd/p516-chen.pdf )

Un autre algorithme important est M. Greenwald et S. Khanna 2004 - Calcul en ligne efficace de l'espace des résumés quantiles.