Интеллектуальный анализ данных учебное пособие. ИАД Лекции Замятин 20. Интеллектуальный анализ данных
 Скачать 2.95 Mb.
|
|
Метрика качества прогноза временного ряда Обозначение / название Формула Единица измерения Описание MAE – средняя абсолютная ошибка 1 𝑁 ∑|𝑌 𝑖 − 𝑌𝑝 𝑖 | 𝑁 𝑖=1 Единица измерения самого фактора Всегда неотрицательная, показывает среднюю ариф- метическую ошибку по наблюдениям. Применя- ется при малых значениях наблюдаемого фактора MAPE – средняя относительная ошибка 1 𝑁 ∑ |𝑌 𝑖 − 𝑌𝑝 𝑖 | |𝑌 𝑖 | 𝑁 𝑖=1 Доли или проценты Самая применяемая и про- стая метрика для ошибки прогнозирования. Всегда неотрицательная. Показы- вает среднюю долю (%) от- клонения прогноза от факта. Чувствительна к за- вышенным прогнозам ME – средняя ошибка 1 𝑁 ∑(𝑌 𝑖 − 𝑌𝑝 𝑖 ) 𝑁 𝑖=1 Единица измерения самого фактора Применяется чаще в фи- нансах и логистически- складских задачах. По знаку показателя опреде- ляют «завышенность» или «заниженность» построен- ного прогноза MSE – средняя абсолютная ошибка Квадрат- ная еди- ница изме- рения самого фактора Всегда неотрицательная. Часто используют корень MSE для сопоставимости единиц измерения. За счет квадрата ошибка более чувствительна к большим разовым отклонениям Max – средняя относительная ошибка Единица измерения самого фактора Выдает отличие факта от прогноза. Применяется, ко- гда критично отклонение выше какой-то величины Max – средняя ошибка Доли или проценты Аналогично, только относи- тельная величина. Приме- няется, когда критично от- клонение на какой-либо % SMAPE Доли или проценты Доработанная MAPE, бо- лее симметрична относи- тельно завышенных и за- ниженных прогнозов 10. Критерии точности 155 10.6. Метрики качества кластеризации В отличие от задач классификации в задачах кластеризации от- сутствуют размеченные данные, с которыми можно было бы ис- пользовать интуитивно понятные метрики качества. Для начала необходимо ввести несколько понятий, используе- мых при расчетах метрик качества кластеризации. Пусть 𝑋 – кла- стеризуемое множество, 𝑁 – количество элементов в множестве 𝑋, 𝑐 – число кластеров, 𝑛 𝑐 𝑖 – число элементов в кластере 𝐶 𝑖 , 𝑣 𝑖 = ∑ 𝑥 𝑥∈𝑐𝑖 𝑛 𝑐𝑖 − центр кластера 𝑐 𝑖 , 𝑋̅ = 1 𝑁 ∑ 𝑥 𝑗 𝑁 𝑗=1 − центральный эле- мент множества, 𝑣̅ = 1 с ∑ 𝑣 𝑖 𝑐 𝑖=1 − центр центров, dim − размерность множества 𝑋. Hubert Г statistic. Данная метрика отражает среднее расстояние между объектами разных кластеров: Г = 1 𝑀 ∑ ∑ 𝑃(𝑖, 𝑗)𝑄(𝑖, 𝑗) 𝑁 𝑗=𝑖+1 𝑁−1 𝑖=1 , (10.10) где 𝑀 = 𝑛 × (𝑛−1) 2 , 𝑃(𝑖, 𝑗) − матрица близости, 𝑄(𝑖, 𝑗) – расстояние между центрами кластеров 𝑣 𝑐 𝑖 и 𝑣 𝑐 𝑗 , к которым принадлежат эле- менты 𝑥 𝑖 и 𝑥 𝑗 соответственно. Чем больше значение метрики – тем лучше. CS-индекс (отделимость кластеров). CS-индекс измеряет от- ношение максимального расстояния между точками в кластере к минимальному межкластерному расстоянию. Оптимальная струк- тура кластеров характеризуется меньшим показателем CS: CS = ∑ { 1 𝑛𝑐𝑖 ∑ max(‖𝑥 𝑗 −𝑥 𝑘 ‖) 𝑥𝑗,𝑥𝑘∈𝑐𝑖 } 𝑐 𝑖=1 ∑ min 𝑗≠𝑖 (‖𝑣 𝑖 −𝑣 𝑗 ‖) 𝑐 𝑖=1 (10.11) VNND-индекс (индекс ближайших соседей). 𝐝 min (𝑥 𝑗 ) = = min 𝑦∈𝑐 𝑖 (‖𝑥 𝑖 − 𝑦‖) – расстояние от элемента 𝑥 𝑗 до его ближай- шего соседа. Интеллектуальный анализ данных 156 𝑑 min (𝑐 i ) ̅̅̅̅̅̅̅̅̅̅̅ = 1 𝑛 𝑐𝑖 (∑ d min (𝑥 𝑖 ) 𝑥 𝑗 ∈𝑐 𝑖 ) – среднее расстояние между ближайшими соседями в кластере 𝑐 𝑖 Отклонения от расстояния между ближайшими соседями: 𝑉(𝑐 𝑖 ) = 1 𝑛 𝑐𝑖 −1 ∑ (𝑑 min (𝑥 𝑗 ) − 𝑑 min (𝑐 i ) ̅̅̅̅̅̅̅̅̅̅̅) 2 𝑥 𝑗 ∈𝑐 𝑖 (10.12) Итоговое значение индекса определяется так: VNND = ∑ 𝑉(𝑐 𝑖 ) 𝑐 𝑖=1 (10.13) 11. Высокопроизводительная обработка данных 157 11. ВЫСОКОПРОИЗВОДИТЕЛЬНАЯ ОБРАБОТКА ДАННЫХ 11.1. Принципы высокопроизводительных вычислений Применение сложных, в том числе интеллектуальных, подходов к обработке данных, представленных мега-, гига- и терабайтами, требует особого внимания к обеспечению их высокопроизводитель- ной обработки. Выше отмечено, что в условиях стремительного наращивания объемов данных многие стандартные вычислитель- ные средства и традиционные алгоритмические подходы для такой сложной и затратной обработки в значительной степени непри- годны. Сформулируем несколько основных принципов организа- ции высокопроизводительных вычислений, которые следует учиты- вать в практическом применении методов Data Mining. Первый принцип организации высокопроизводительных вычис- лений заключается в увеличении производительности обработки данных за счет совершенствования вычислительной эффективности алгоритмов, позволяя применять достаточно сложную обработку данных, но в некоторых случаях доступную даже для ПЭВМ со стандартными характеристиками. Сегодня доступны различные вычислительные мощности. Вы- числительные кластеры организуют как на базе стандартных недо- рогих ПЭВМ, объединенных в локальную вычислительную сеть, так и в специализированных центрах, оснащенных суперкомпью- терной многопроцессорной техникой [60]. Поэтому второй прин- цип определяет целесообразность использования таких подходов к обработке данных, которые применимы как на дорогостоящей суперкомпьютерной технике, так и на недорогих ПЭВМ, объеди- ненных в сети. При этом подразумевается, что высокопроизводи- тельная обработка достигается двумя способами, которые могут быть использованы совместно. Интеллектуальный анализ данных 158 Первый способ предполагает обработку исключительно за счет применения более высокопроизводительной вычислительной тех- ники. Второй – адаптацию существующих подходов для возможно- сти не только канонического параллельного, но и так называемого распределенно-параллельного исполнения. Обширный класс парал- лельных вычислений характеризуется возможностью одновремен- ного решения одной вычислительной задачи путем ее декомпози- ции [60]. Очевидно, параллельные вычисления могут быть реализо- ваны на одной ПЭВМ в многопроцессном режиме под управлением многозадачной операционной системы [75]. Параллельные вычис- ления на нескольких вычислительных узлах (например, нескольких ПЭВМ, объединенных в локальную вычислительную сеть, или не- скольких процессорах суперкомпьютера) терминологически отно- сят к распределенным вычислениям. Именно поэтому здесь и далее, применяя термин распределенно-параллельные вычисления, будем иметь в виду вычислительный процесс, реализуемый не только как параллельный, но и как распределенный. Практическая организация высокопроизводительных распреде- ленно-параллельных вычислений с использованием указанных выше принципов требует ряда важных пояснений. Организация распределенных вычислений возможна с использо- ванием множества различных подходов и архитектур [63]. Однако при всем многообразии возможных вариантов принципиально отличают два различных класса построения вычислительных си- стем – системы с общей (разделяемой) памятью и системы с рас- пределенной памятью [60]. К первому варианту построения вычислительных систем отно- сят системы с симметричной архитектурой и симметричной орга- низацией вычислительного процесса – SMP-системы (англ. Symmetric MultiProcessing). Поддержка SMP-обработки данных присутствует в большинстве современных ОС при организации вы- числительных процессов на многопроцессных (многоядерных) ПЭВМ [75]. Однако разделяемая память требует решения вопросов синхронизации и исключительного доступа к разделяемым данным, а построение высокопроизводительных систем в этой архитектуре 11. Высокопроизводительная обработка данных 159 затруднено технологически сложностями объединения большого числа процессоров с единой оперативной памятью [60, 75]. Второй вариант предполагает объединение нескольких вычисли- тельных узлов (ВУ) с собственной памятью в единой коммуникаци- онной среде, взаимодействие между узлами в которой осуществля- ется путем пересылки сообщений. Причем такими ВУ могут быть как стандартные недорогие ПЭВМ, так и процессоры дорогостоя- щего суперкомпьютера. Такая архитектура построения вычисли- тельной системы характеризуется бóльшими возможностями по- строения высокопроизводительных вычислительных систем и значительного масштабирования доступных вычислительных мощ- ностей. Однако, в отличие от SMP-систем, здесь более высокая латентность (существенные накладные коммуникационные рас- ходы), негативно влияющая на производительность системы и требующая более внимательной организации распределенно-парал- лельной обработки [60]. Причем в случае построения вычислитель- ного кластера на базе ПЭВМ такая латентность, как правило, суще- ственно выше, чем при построении кластера на базе суперкомпью- тера, за счет значительно более развитой коммуникационной среды. В соответствии с классификацией архитектур вычислительных систем М. Флинна наибольшее распространение на практике полу- чили две модели параллельных вычислений – Multiple Process / Pro- gram – Multiple Data (MPMD, множество процессов / программ, множество данных) и Single Process / Program – Multiple Data (SPMD, один процесс / программа, множество данных) [60]. Модель MPMD предполагает, что параллельно выполняющиеся процессы исполняют различные программы (процессы, потоки) на различных процессорах. Модель SPMD обусловливает работу параллельно выполняющихся программ (процессов, потоков), но исполняющих идентичный код при обработке отличных (в общем случае) масси- вов данных. Очевидно, организацию распределенных вычислений целесооб- разно реализовать с использованием программ с параллельной об- работкой данных на основе модели SPMD. Во-первых, это более практично из-за необходимости разрабатывать и отлаживать лишь Интеллектуальный анализ данных 160 одну программу, а во-вторых, такие программы, как правило, при- менимы и при традиционном последовательном исполнении, что расширяет области их практической применимости. Кроме вышеизложенных особенностей организации высокопро- изводительных вычислений в различных архитектурах и на основе различных моделей, при разработке алгоритмического обеспечения параллельной обработки необходимо: – определить фрагменты вычислений, которые могут быть ис- полнены параллельно; – распределить данные по модулям локальной памяти отдель- ных ВУ; – согласовать распределение данных с параллелизмом вычис- лений. Важным является выполнение всех перечисленных условий, так как иначе значительные фрагменты вычислений не удастся предста- вить как параллельно исполняемые и реализация алгоритма в рас- пределенно-параллельной архитектуре не позволит добиться роста производительности. Задачи распределения данных по модулям па- мяти и задача согласования распределения данных важны для обес- печения низкой латентности между ВУ и обеспечения возможно- стей масштабирования системы. Помимо этого, при построении такого рода вычислительных си- стемы важно иметь четко измеримые показатели их эффективности. Первым таким критерием можно назвать параллельное ускорение, которое показывает ускорение выполнения по сравнению с после- довательным вариантом. Вычисляется оно для количества парал- лельных процессов p следующим образом: 𝑆 𝑝 (𝑛) = 𝑇 1 (𝑛) 𝑇 𝑝 (𝑛) ⁄ , (11.1) где n – параметр вычислительной сложности задачи (например, ко- личество входных данных), T – время решения задачи. Фактически это отношение времени выполнения на скалярной ПЭВМ к времени выполнения параллельного алгоритма. В общем случае 𝑆 𝑝 (𝑛) < 𝑝, так как параллельный алгоритм не может обеспечить идеальные 11. Высокопроизводительная обработка данных 161 балансировку ВУ и латентность. Максимальное значение 𝑆 𝑝 (𝑛) = 𝑛 (линейное ускорение). Вторым критерием является эффективность использования па- раллельным алгоритмом ВУ. Этот критерий определяет среднюю долю времени выполнения алгоритма, в течение которой процес- соры реально используются для решения задачи, и вычисляется сле- дующим образом: 𝐸 𝑝 (𝑛) = 𝑇 1 (𝑛) 𝑝𝑇 𝑝 (𝑛) ⁄ = 𝑆 𝑝 (𝑛) 𝑝 ⁄ . (11.2) Как видно, в лучшем случае 𝑆 𝑝 (𝑛) = 𝑝 и 𝐸 𝑝 (𝑛) = 1. Таким образом, повышение производительности обработки дан- ных может быть реализовано путем: – наращивания мощности аппаратной инфраструктуры; – применения распределенно-параллельных подходов к орга- низации вычислений на кластерах различной стоимости и конфигу- рации, различных моделей параллельных вычислений и архитектур организации вычислительного процесса; – увеличения вычислительной эффективности алгоритмов за счет оптимизации, использования приближенных эвристик вместо трудоемких расчетов и т.п. 11.2. Особенности построения вычислительного кластера Понятия «параллельное вычисление» и «распределенное вычис- ление» похожи тем, что в обоих случаях имеется в виду, что суще- ствует несколько потоков или процессов, работающих сообща, чаще всего над одной задачей. Обычно считается, что при параллельном вычислении процессы или потоки работают в разделяемой памяти без пересылки данных по сети, в распределенной системе существует несколько узлов, между которыми идет обмен данными по сети. Характер решаемой задачи определяет необходимые параметры вычислительной системы как на уровне оборудования, так и на уровне программного обеспечения. К параметрам оборудования от- носятся такие характеристики, как объем общего или локального хра Интеллектуальный анализ данных 162 нилища данных, объем оперативной памяти, число и параметры про- цессоров, устройство сети, ее пропускная способность и задержки. На уровне программного обеспечения определяются конкретная логика хранения и передачи данных, а также перераспределения за- дач, и, что немаловажно, контроль нагрузки и отказоустойчивости вычислительной системы. Определение параметров проектируемой вычислительной си- стемы и логики ее работы невозможно без определения параметров решаемой задачи. К таким параметрам относятся: – тип требуемого анализа: пакетная обработка (есть некий накопленный объем данных, который нужно обработать), обра- ботка в реальном времени (данные будут обработаны сразу после поступления), микропакетная обработка (занимает промежуточное положение между двумя предыдущими типами); – объем данных: объем поступающих данных, скорость поступ- ления и объем имеющихся данных (имеет особое значение, по- скольку критичным является его соотношение с объемом имеюще- гося хранилища); – тип данных: структурированные данные (таблицы баз дан- ных), неструктурированные (текст, изображения и видео) и полу- структурированные (JSON и XML); – скорость выдачи результата – рамки допустимого времени выдачи результата. Далее при рассмотрении вариантов построения вычислительных систем будем пользоваться понятием роли ВУ. Каждая из приведен- ных ниже ролей представляет собой набор некоторых функций, свя- занных общей задачей. Роль может быть реализована как в виде от- дельного приложения, так и как часть приложения. 1. Менеджер задач – принятие решений о передаче конкретной задачи конкретному исполнителю, мониторинг выполнения. 2. Исполнитель задач –выполнение вычислений в рамках за- дачи и выделенных ресурсов, возврат результата менеджеру задач. 3. Менеджер ресурсов –принятие решения о выделении процес- сорной мощности и оперативной памяти под конкретную задачу, мо- ниторинг доступных ресурсов, ведение перечня доступных ресурсов. 11. Высокопроизводительная обработка данных 163 4. Менеджер данных –принятие решения о месте хранения дан- ных или фрагментов данных, выдача данных по запросу путем сбора из конкретных мест хранения, если требуется. 5. Хранилище данных – место хранения данных. Варианты построения вычислительной системы. Выделяют три основных класса задач, требующих учета при построении вы- числительного кластера: 1. Небольшой объем данных, пакетная обработка, отсутствие требований ко времени выдачи результата. 2. Большой объем данных, пакетная обработка, отсутствие тре- бований к времени выдачи результата. 3. Большой объем данных, пакетная обработка, результат дол- жен быть получен как можно быстрее. Рассмотрим каждый из этих вариантов. Небольшой объем данных, пакетная обработка, отсутствие требований ко времени выдачи результата. Под небольшим объ- емом будем иметь в виду возможность хранить данные на одном компьютере. При таких требованиях вполне достаточно примене- ния традиционных подходов, предполагающих простое перераспре- деление задач по узлам. В зависимости от требуемого объема дис- кового пространства и требований к производительности может быть использован как один вычислительный узел (ВУ), так и не- сколько. В обоих случаях схема взаимодействия процессов будет примерно такой, как показано на рис. 50. Рис. 50. Схема варианта построения вычислительной системы Менеджер задач Данные Менеджер задач Исполнитель задач Менеджер задач Исполнитель задач Интеллектуальный анализ данных 164 В рамках данного подхода работают такие известные средства, как OpenMP и MPI. OpenMP используется для параллельных вычис- лений на одном вычислительном узле c помощью многопоточности, а MPI может применяться и на одном ВУ, и на нескольких и порож- дает процессы. В такой схеме исполняемый программный код содержит инструкции по разделению и обмену данными. В MPI данные могут как пересылаться между ВУ по сети, так и браться из разделяемых сетевых папок. |