Лекция: Binary Search

Завдання -необхідно перевірити наявність лінійного зв'язку між відповідними показниками діяльності комерційних банків України в модулі Multiple Regression ППП Statistica.

Зробити висновки щодо адекватності побудованої моделі, дати економічну інтерпретацію даної залежності й можливості її теоретичного використання.

Методичні рекомендації

Для побудови й аналізу простих лінійних економетричних моделей у ППП Statistica передбачений модуль Multiple Regression (Множинна регресія). Розглянемо порядок роботи в даному модулі.

1. Запуск Statistica і підготовка даних. У меню програм вибрати програму Statistica, після її запуску виберіть у меню пункт File-New для підготовки власних даних. Перед Вами з'явиться діалогове вікно в якому необхідно вказати кількість змінних (Number of variables) і кількість випадків (Number of Cases). Після уведення натисніть кнопку вікна OK. Після заповнення всіх комірок поля даних Ви одержите таблицю, аналогічну представленої на рис. 37.

Рис. 37. Вихідні дані

2. Розрахунки. Щоб приступити до обчислювальних процедур необхідно ввійти в позицію меню Statistics / Multiple Regression (рис. 38). Після підтвердження вибору модуля перед Вами з'явиться стартова панель даного модуля, де необхідно задати змінні для аналізу (рис. 39).

Рис.38. Вибір модуля

Рис. 39. Стартова панель модуля

Ініціюйте кнопку Variables (Змінні) і у вікні, що з'явилося, вкажіть Dependent (залежну) і Independent (незалежну) змінну для побудови простої регресійної моделі. Вибір змінних представлений на рис. 40. Після вказівки змінних підтвердіть свій вибір натисканням кнопки ОК.

Рис. 40. Вибір змінних для аналізу

3. Побудова моделі, визначення її характеристик та перевірка її статистичної значимості.

Побудуємо лінійну економетричну модель і визначимо всієї її характеристики (параметри моделі, середнєквадратичне відхилення параметрів моделі, дисперсію й середнєквадратичне відхилення помилок моделі, коефіцієнти кореляції й детермінації). Перевіримо статистичну значимість параметрів моделі за критерієм Ст’юдента, та адекватність моделі за критерієм Фішера. Побудуємо графік лінійної функції з довірчими інтервалами.

Результати побудови лінійної економетричної моделі будуть представлені в діалоговому вікні (рис.41). У верхній частині вікна представлена основна інформація моделі, у нижній частині знаходяться функціональні кнопки, що дозволяють всебічно розглянути результати аналізу.

Рис.41. Вікно результатів регресійного аналізу

Ініціювавши кнопку Summary: Regression results (Результати регресійного аналізу) ми визначимо найважливіші характеристики моделі й ступінь її адекватності (рис. 42).

Рис. 42. Результати регресійного аналізу

Проаналізуємо отримані результати моделі:

R = 0.95 – коефіцієнт множинної кореляції (у випадку простої лінійної регресії дорівнює модулю коефіцієнта кореляції);

R2= 0.9091 — коефіцієнт детермінації моделі;

Adjusted R2 = 0.9021 — скоректований коефіцієнт детермінації на число спостережень і число параметрів;

F (1,13) = 130.15 — критерій адекватності Фішера;

Std.Error of estimate = 0.2025 — середнє квадратичне відхилення помилок моделі;

В (а1, а2) = (-0,21; 1,28) – параметри моделі, отже модель має вигляд

Y = -0.2194 + 1.2796*x;

Std.Error of B = (0.10; 0.11) — середнє квадратичне відхилення параметрів моделі;

t(13) = (-2.14; 11.4) – значимість параметрів за критерієм Ст’юдента.

Побудуємо графік лінійної функції з довірчими інтервалами. Для цього в меню Graphs / Scatterplots необхідно вказати змінні, лінію рівня й довірчі інтервали (рис. 43). Ініціювавши кнопку ОК одержимо наступний графік (рис. 44).

Рис.43. Завдання параметрів графіка

Рис.44. Графік лінійної залежності

4. Аналіз помилок. Розрахуємо теоретичні значення залежної змінної й помилки моделі. Побудуємо гістограму й графік розподілу помилок на нормальному імовірнісному папері.

Щоб розрахувати й проаналізувати залишки, у нижній частині вікна результатів регресійного аналізу є опція Perform residual analysis (Всебічний аналіз залишків). Ініціювавши дану опцію ми одержимо меню для аналізу помилок моделі (рис.45).

Рис.45. Меню аналізу помилок

Кнопка аналізу помилок Summary: Residuals & Predicted відображує спостережувані значення залежної змінної (Observed value), теоретичні значення залежної змінної (Predicted value) і помилки моделі(Residual), як різницю спостережуваних і теоретичних значень (рис. 46).

Графік розподілу помилок на нормальному імовірнісному папері (Normal plot of residuals) наведений на рис. 47.

Рис. 46. Аналіз помилок моделі

Рис. 47. Графік розподілу помилок на нормальному імовірнісному папері

Оскільки, одна з основних гіпотез щодо випадкової величини говорить, що помилки повинні бути розподілені за нормальним законом, представимо гістограму розподілу помилок .(Residuals / Normal plot of residuals) і проаналізуємо її (рис.48).

Рис. 48. Гістограма розподілу помилок

5. Розрахунок прогнозу значень залежної змінної та довірчих інтервалів зміни. Оскільки модель є адекватною, її параметри значимі, то по моделі можна скласти прогноз. Щоб розрахувати прогнозні значення залежної змінної, у нижній частині вікна результатів регресійного аналізу є опція Predict dependent variable (Прогнозування залежної змінної). Ініціювавши дану опцію необхідно вказати значення незалежної змінної, для якої необхідно спрогнозувати залежну величину (рис.49).

Рис. 49. Значення незалежної змінної

Результати прогнозування представляються у вигляді таблиці, у якій зазначені коефіцієнти моделі й порядок розрахунків (рис. 50).

Рис. 50. Результати прогнозу

Прогнозне значення залежної змінної (Predicted) = 1,3160; і довірчі інтервали для прогнозного значення:

1,164405 ≤ 1,316016 ≤ 1,467627

Ми провели всебічний аналіз однофакторної лінійної економетричної моделі залежності балансового прибутку найбільших банків України від значення чистих активів їхньої діяльності.

Binary Search

A binary search is a fast search algorithm suitable for data sets of any reasonable size encountered. Unlike a linear search, it is suitable even for very large data sets because it eliminates large numbers of comparisons. A binary search differs from a linear search in that it requires sorted data to operate successfully.

We can explore how a binary search operates by considering how it would find an element in the following vector.

Figure 1 A vector containing nine elements

Given the vector pictured in Figure 1, we can use a binary search to find the element that contains the value 9. All binary searches begin by comparing the item being sought against the item in the middle of the data set. In this example, the middle element contains the value 21.

Figure 2 Selecting the middle element

The value we are seeking is 9. Since 9 is less than 21, we know that 9 must be stored in an element somewhere to the left of the middle element. With this in mind, we can safely ignore the right half of the vector and continue our search, only considering the left half of the vector. Figure 3 demonstrates this partitioning of the vector.

Figure 2 Partitioning the vector

After we partition the vector, the middle element changes. We then compare the value stored here to the value we seek. Since 5 is less than 9, we know that 9 must be stored in the right half of this partition. We can then ignore the left half of this partition, and compare against the midpoint of the right half.

Figure 4 Partitioning the vector, again

Figure 4 highlights the midpoint of the current vector partition in green. The value stored here equals the value we seek so our search is complete. For this vector, which contains nine elements, only three comparisons were needed to find the element that stored the value 9. Starting from the left side of the vector, a linear search needs only three comparisons also to find the element that stores the value 9. The real advantage of binary search appears when we consider larger data sets. The following table lists the maximum number of comparisons a binary search algorithm has to make to find any element in vectors of various sizes.

Table 1 Maximum comparisons of binary search

Even for a vector that contains a billion elements, a binary search algorithm needs to make at most thirty comparisons to find any element. An implementation of a binary search algorithm appears in Listing 2.

The only disadvantage of a binary search is that it requires sorted data. Without sorted data, the midpoint comparisons are meaningless and the search would incorrectly report that an element is not present in the data set. Given a vector of unsorted items, how can we sort the items so that we can use a binary search? There are many approaches that we can take. We introduce the various approaches in 4.1.2 Basic Sorting Algorithms.

Instead of relying on their own binary search implementations, C++ programmers can use the STL binary_search function. The STL binary_search interface resembles the find function interface. The only difference is that function binary_search returns a bool value indicating the success of the search. An example use of the STL binary_search appears in wordsearch.cpp. This program stores the words contained in a text file into a vector. The user then enters a word via the console. The program then performs a binary search to see if the text file contains the word. A sample text file containing the full text of Nathaniel Hawthorne's The House of the Seven Gables can be found here.