Как рассчитать шкалу оценки Rousseeuw's и Croux '(1993) Qn для больших выборок?

13

Пусть поэтому для очень короткой выборки, такой как ее можно вычислить от нахождения статики го порядка парных разностей: Qn=Cn.{|XiXj|;i<j}(k){1,3,6,2,7,5}k

    7 6 5 3 2 1
1   6 5 4 2 1
2   5 4 3 1
3   4 3 2
5   2 1
6   1
7

ч = [п / 2] + 1 = 4

к = ч (ч-1) / 2 = 8

Таким образом,Qn=Cn.2

Очевидно, что для больших выборок, состоящих из 80 000 записей, нам нужна очень большая память.

Есть ли способ вычислить в 1D пространстве вместо 2D?Qn

Ссылка на ответ ftp://ftp.win.ua.ac.be/pub/preprints/92/Timeff92.pdf, хотя я не могу полностью понять это.

К-1
источник
1
Хорошо, ответ для парней, которые будут читать это позже: если вы просто хотите рассчитать надежную оценочную шкалу для фрагмента данных 1, установите последнюю версию R 2, установите пакет robustbase, 3 готов к работе! но если вы разрабатываете код вне этой среды, вам нужно использовать взвешенные высокие медианы, чтобы минимизировать необходимые вычисления для Sn или Qn.
К-1
1
Ссылка на статью не работает. Правильная ссылка (даже лучше, с цитатой из наиболее релевантной информации) помогла бы нам найти информацию; в таком виде бесполезно, когда ссылка умирает (как это часто бывает).
Glen_b
2
не должно ли быть k = h выбрать 2 = h (h-1) / 2 = 6 ? Это не меняет конечного результата.
тигр
почему Qn = Cn * 2, почему 2? как рассчитывалось?
Лидокс

Ответы:

15

Обновление: суть проблемы заключается в том, что для достижения временной сложности требуется порядок хранения .O(nlog(n))O(n)


Нет, O(nlog(n)) - нижняя теоретическая граница для временной сложности (см. (1)) выбора элемента kth среди всех n(n1)2 возможных.|xixj|:1i<jn

Вы можете получить пространство , но только наивно проверяя все комбинации за время .O(1)xixjO(n2)

Хорошей новостью является то, что вы можете использовать оценщик масштаба (см. (2) и (3) для улучшенной версии и некоторых сравнений по времени), реализованный в функции в пакете . Одномерная оценка является двухступенчатой ​​(т.е. повторно взвешенной) оценкой масштаба. Он имеет эффективность Гаусса 95 процентов, точку разбивки 50 процентов и сложность времени и пространства (плюс его легко можно сделать «онлайн», что позволяет сократить половину вычислительных затрат при повторном использовании - хотя вы для реализации этой опции придется копаться в коде, это довольно просто сделать).τscaleTau2()RrobustbaseτO(n)O(1)R

  1. Сложность выбора и ранжирования в X + Y и матрицах с отсортированными столбцами Г. Н. Фредериксон и Д. Б. Джонсон, Журнал компьютерных и системных наук, том 24, выпуск 2, апрель 1982, страницы 197-208.
  2. Йохай, В. и Замар, Р. (1988). Высокая точка пробоя оценки регрессии посредством минимизации эффективной шкалы. Журнал Американской статистической ассоциации 83 406–413.
  3. Маронна Р. и Замар Р. (2002). Надежные оценки местоположения и дисперсии для многомерных наборов данных. Технометрия 44 307–317

Изменить Чтобы использовать это

  1. Запустите R(это бесплатно и может быть загружено здесь )
  2. Установите пакет, набрав:
install.packages("robustbase")
  1. Загрузите пакет, набрав:
library("robustbase")
  1. Загрузите файл данных и запустите функцию:
mydatavector <- read.table("address to my file in text format", header=T)
scaleTau2(mydatavector)
user603
источник
2
@ user603: тау, о котором ты говорил. Кстати, почему это не широко распространено, если оно имеет такую ​​хорошую статистическую и вычислительную эффективность и точку разбивки?
Кварц
2
а) вы можете вычислить сумасшедшие и срединные онлайн . Отсюда легко вычислить Тау. б) поломка не является устойчивой и тау имеет ужасный уклон в присутствии выбросов. Вы можете найти больше аргументов против этого в разделе 5 статьи Qn
user603
1
@ user603 ты имеешь в виду эту статью? wis.kuleuven.be/stat/robust/papers/publications-1994/…
Герман Демидов,
1
@ user603, согласно статье, кривая смещения говорит нам, насколько оценщик может измениться из-за данной доли загрязнения. и S n были смещены для моих смоделированных примеров (нормальное распределение + 20% от чрезвычайно высоких / низких значений), и уровень смещения был сопоставим. Может быть, я что-то не так понял, но и похоже, страдают от одной и той же проблемы. QnSnSnQn
Герман Демидов
1
@ user603 извините, эффект не может быть виден для образцов размером 100. Я ясно вижу проблему с использованием больших размеров образцов. У всех них ужасные уклоны, но у самый большой. τ
Герман Демидов
0

(Очень короткий ответ) Текст для комментирования говорит

избегайте ответов на вопросы в комментариях.

Итак, вот оно: Есть статья об онлайн-алгоритме, который, похоже, работает достаточно хорошо: Применение Estimator OnlineQn .

РЕДАКТИРОВАТЬ

(пользователем user603). Алгоритм, связанный с этой статьей, представляет собой версию Q n с движущимся окном .Qn

Для большой выборки разделенной на временные окна шириной n < N , { x i } t i = t - n + 1, мы можем применить Q n к каждому временному окну, получая N - n + 1 значения Q н . Обозначим эти значения { Q i n } N - n + 1 i ={xi}i=1Nn<N{xi}i=tn+1tQnNn+1Qn{Qni}i=1Nn+1

Приведенный здесь алгоритм позволяет получить при средней стоимости меньше, чем наихудший O ( n log ( n ) ), необходимый для вычисления Q i n с нуля.Qni|Qni1 O(nlog(n))Qni

Однако этот алгоритм не может использоваться для вычисления полной исходной выборки { x i } N i = 1 . Также необходимо поддерживать буфер, размер которого может достигать O ( n 2 ) (хотя он часто намного меньше).Qn{xi}i=1NO(n2)

Serv-вкл
источник
Хотя вы не должны отвечать в комментариях, вы также не должны публиковать комментарии как ответы, и если ваш ответ является только ссылкой, это не ответ (но может быть комментарием). Если вы хотите, чтобы это был ответ, а не комментарий, ваш ответ должен каким-либо образом содержать соответствующую информацию, такую ​​как цитата из ссылки, на которую ссылаются должным образом, или ваше собственное объяснение важных деталей. Если вы можете, пожалуйста, предоставьте необходимую информацию; в качестве альтернативы я могу преобразовать это в комментарий для вас.
Glen_b
@Glen_b: идти вперед и конвертировать. Спасибо за разъяснение.
серв-ин
1
@ user603 Возможно, вы могли бы (как в ссылках в моем комментарии) отредактировать основную информацию в приведенном выше ответе - так как в настоящее время это не входит в рекомендации сетей SE для ответов.
Glen_b
Нет проблем, я буду! (но здесь уже поздно)
user603
@ user603 Спасибо; Тогда я оставлю это здесь
Glen_b
0

это мой инструмент Qn ...

Я программировал это на C, и результат таков:

void bubbleSort(double *datos, int N)
{
 for (int j=0; j<N-1 ;j++)     
  for (int i=j+1; i<N; i++)    
   if (datos[i]<datos[j])      
   {
    double tmp=datos[i];
    datos[i]=datos[j];
    datos[j]=tmp;
   }
}

double  fFactorial(long N)    
{
 double factorial=1.0;

 for (long i=1; i<=N; ++i)
  factorial*=(double)i;

 return factorial;  
}

double fQ_n(double *datos, int N)  // Rousseeuw's and Croux (1993) Qn scale estimator
{
 bubbleSort(datos, N);

 int m=(int)((fFactorial((long)N))/(fFactorial(2)*fFactorial((long)N-2)));

 double D[m];
 //double Cn=2.2219;      //not used now :) constant value https://www.itl.nist.gov/div898/software/dataplot/refman2/auxillar/qn_scale.htm

 int k=(int)((fFactorial((long)N/2+1))/(fFactorial(2)*fFactorial((long)N/2+1-2)));

 int y=0;

 for (int i=0; i<N; i++)
  for (int j=N-1; j>=0; j--)
   if (i<j)
   {
    D[y]=abs(datos[i]-datos[j]);
    y++;
   }

 bubbleSort(D, m);

 return D[k-1];
}

int main(int argc, char **argv)    
{
 double datos[6]={1,2,3,5,6,7};
 int N=6;

 // Priting in terminal the final solution
 printf("\n==[Results] ========================================\n\n");

 printf(" Q_n=%0.3f\n",fQ_n(datos,N));

 return 0;
}
Виктор
источник
1
Хотя реализация часто смешивается с содержательным содержанием вопросов, мы должны быть сайтом для предоставления информации о статистике, машинном обучении и т. Д., А не кода. Также может быть полезно предоставить код, но, пожалуйста, разработайте свой содержательный ответ в тексте для людей, которые недостаточно хорошо читают этот язык, чтобы распознать и извлечь ответ из кода.
gung - Восстановить Монику
Это наивный алгоритм O (n ** 2) ~
user603