Сильно разреженная матрица структура: Разреженные матрицы (sparse matrix) для чайников

Разреженные матрицы (sparse matrix) для чайников

Автор Роман Котюбеев

В одной из статей по Apache Spark я говорил о разреженных (sparse) матрицах, но не вдавался в подробности. Многих сбивают с толку эти разреженные матрицы, поскольку формат их хранения отличается от плотных матриц. Тем не менее, разреженные матрицы очень часто используются в Data Science, поскольку их хранение менее затратное. Сегодня мы шаг за шагом рассмотрим переход от плотных матриц к разреженным, начав со списка координат (COOrdinate list) и закончив сжатым хранением строкой (CSR) и столбцом (CSC).

Локальные векторы: плотные и разреженные

Допустим, что у нас имеется матрица (см. рисунок ниже). При беглом взгляде осознаем, что в ней много нулей (возможно, это матрица c категориальными значениями) А что если бы это была матрица 1000×1000? А матрица 100000×500000 со всеми этими нулями? Нет смысла хранить матрицу, где большая часть элементов – это нули. Поэтому пришли к так называемым разреженным матриц (sparse matrix).

Плотная матрица

Разреженные матрицы представляют в различных форматах:

• координатный список (Coordinate List),
• сжатое хранение строкой (Compressed Sparse Row),
• сжатое хранение столбцом (Compressed Sparse Column),
• список списков (List of lists),
• словарь ключей (Dict of keys)

Мы расскажем о первых трех, так как они встречаются чаще.

Список координат (Coordinate List)

Возможно, самый очевидный формат хранения разреженных матриц является список координат. Такой формат представляет собой триплет (строка, столбец, значение). При этом, хранятся только ненулевые значения. Например, матрицу выше можно записать следующим образом:

Представление списка координат

В этом формате еще хранится размерность матрицы. Подразумевается, что не записанные значения являются нулями.

Улучшаем, применив правило row-major order

Мы можем еще улучшить список координат. Давайте вместо того чтобы хранить каждый индекс строки, будем хранить количество ненулевых значений на каждой строке. Вот, что случится, после применения данного правила:

Улучшенный список координат

Подобное правило примененное к строкам называется порядок по строкам (row-major mode). Ничто не мешает применить его к столбцам, тогда это будет порядок по столбцам (column-major order) [1].

Как можно заметить, теперь мы храним меньше данных: в данном примере меньше на два элемента по сравнению с оригинальным списком координат.

А что насчет компьютера? Получается, что он хранит три массива и размерность разреженной матрицы. Тогда как извлечь отдельные строки (поскольку это row-major order) из нее? Алгоритм извлечения p-й строки достаточно прост. Допустим, нам нужна 3-я строка (не забываем про счет с 0), т.е. последняя строка (0,0,0,1,0,3,0), тогда требуется:

1. Определить количество n ненулевых элементов выше p-й строки. Выполнить эту процедуру путем суммирования элементов в векторе Не-0 в строке вплоть до p-й строки. Для 3-й строки получается 1 + 3 + 0 = 4, значит количество ненулевых элементов выше 3-й строки равно 4.
2. Определить количество k элементов в p-й строке. Это значение равно p-му элементу вектора Не-0 в строке. Для 3-е строки это значение равно 2.
3. Дойти до элемента n + 1 векторов Столбец и Значение. В нашем случае это 4 + 1 = 5.
4. Взять k пар элементов векторов Столбец и Значение. В нашем случае это пары (3, 1) и (5, 3).
5. Вернуть вектор размера N (где N – это количество строк) с заполненными соответствующими парами, а остальные элементы заполняются нулями. В нашем случае это a[3] = 1 и a[5] = 3, а все остальное — это нули.

Сжатое хранение строкой (Compressed Sparse Row, CSR)

А что если мы захотим извлечь строку 2-ю, потом 1-ю, потом снова 2-ю и т. д. Исходя из алгоритма, происходит суммирование элементов вектора Не-0 в строке каждый раз при извлечение очередной строки. Так, может быть, сразу и заменим вектор

Не-0 в строке на кумулятивную сумму количества ненулевых элементов в строке и назовем новый вектор Кумулята Не-0 в строке. Тогда получится такой результат:

Формат CSR

И вот снова требуется получить p-ю строку, например, 3-ю. Тогда алгоритм ее получения будет следующим:

1. Определить количество ненулевых элементов выше p-й строки. Это просто (p — 1)-й элемент вектора Кумулята Не-0 в строке. Для 3-й строки — это 4.
2. Определить количество ненулевых элементов в строке p. Это количество равно разнице между p-м и (p-1)-м элементами вектора Кумулята Не-0 в строке. Для 3-й строки эта разница между 3-м и 2-м элементами, т.е. 6 — 4 = 2.
3. Шаги 3, 4, 5 такие же, как и выше.

В первом шаге нужно добавить условие при извлечении 0-ю строки: Если требуется 0-я строка, вернуть 0 — поскольку выше этой строки ничего нет.

Такой формат хранения называется сжатое хранение строкой (Compressed Sparse Row, CSR).

Сжатое хранение столбцом (Compressed Sparse Column, CSC)

В задачах машинного обучения (machine learning) наиболее распространенной практикой является извлечение столбцов (признаков) нежели строк. С точки зрения математики строки и столбцы матрицы эквивалентны, поэтому правила выше можно применять к столбцам. Такая форма представления называться сжатое хранение столбцом (Compressed Sparse Column, CSC).

Если мы будем считать кумуляту по столбцам, т.е. по правилу порядка по столбцам (column-major order), то получим следующее:

Формат CSC

При извлечении столбца считаем то, что левее и правее необходимого. И также возвращается 0 на первом шаге алгоритма при извлечении 0-го столбца.

Еще больше подробностей о векторах, матрицах и других структурах данных с примерами из Data Science вы узнаете на специализированном курсе по машинному обучению «PYML: Введение в машинное обучение на Python» в лицензированном учебном центре обучения и повышения квалификации разработчиков, менеджеров, архитекторов, инженеров, администраторов, Data Scientist’ов и аналитиков Big Data в Москве.

Смотреть расписание

Записаться на курс

Источники

1. https://en.wikipedia.org/wiki/Row-_and_column-major_order

НОУ ИНТУИТ | Лекция | Умножение разреженных матриц

Аннотация: В лекции рассматриваются типовые алгоритмы, применяемые в работе с плотными и разреженными матрицами. Рассказывается о некоторых форматах хранения этих матриц. Рассматриваются основные свойства матриц, методы решения СЛАУ, прямые и итерационные методы.

Ключевые слова: матрица, система линейных уравнений, вектор, норма, параметр, итерация, точность, компонент, Главная диагональ, представление, сходимость, дискретизация, выражение, радиус, решение системы линейных уравнений, функция, градиент, анализ, модель вычислений, операции

Цель лекции: Основной целью лекции является применение полученные знания о разработке и отладке параллельных программ в реализации численных алгоритмов для работы с матрицами.

Презентация к лекции

Видеозапись лекции — (объем — 707 МБ).

Прямые методы решения СЛАУ

Методы решения систем линейных алгебраических уравнений (СЛАУ) относятся к численным методам алгебры. При формальном подходе решение подобных задач не встречает затруднений: решение системы можно найти, раскрыв определители в формуле Крамера. Однако при непосредственном раскрытии определителей решение системы с n неизвестными требует арифметических операций; уже при

n порядка 20 такое число операций недоступно для современных компьютеров. При сколько-нибудь больших n применение методов с таким порядком числа операций будет невозможно и в обозримом будущем. Другой причиной, по которой этот классический способ неприменим даже при малых n, является сильное влияние на окончательный результат округлений при вычислениях.

Методы решения алгебраических задач можно разделить на точные и итерационные. Классы задач, для решения которых обычно применяют методы этих групп, можно условно назвать соответственно классами задач со средним и большим числом неизвестных. Изменение объема и структуры памяти вычислительных систем, увеличение их быстродействия и развитие численных методов приводят к смещению границ применения методов в сторону систем более высоких порядков.

Например, в 80-х годах прошлого века точные методы применялись для решения систем до порядка 10⁴, итерационные – до порядка 10⁷, в 90-х – до порядков 10⁵ и 10⁸ соответственно. Современные суперкомпьютеры способны использовать точные методы при решении еще больших систем.

Мы будем рассматривать систему из n линейных алгебраических уравнений вида

( 7. 1)

В матричном виде система может быть представлена как

( 7.2)

где есть вещественная матрица размера ; b и x — вектора из n элементов.

Под задачей решения системы линейных уравнений для заданных матрицы А и вектора b мы будем считать нахождение значения вектора неизвестных x, при котором выполняются все уравнения системы.

Метод исключения Гаусса

В первую очередь рассмотрим алгоритмыы, предназначенные для решения системы

( 7. 3)

с произвольной квадратной матрицей А. Основой для всех них служит широко известный метод последовательного исключения неизвестных, или же метод Гаусса.

Метод Гаусса основывается на возможности выполнения преобразований линейных уравнений, которые не меняют при этом решение рассматриваемой системы (такие преобразования носят наименование эквивалентных). К числу таких преобразований относятся:

• умножение любого из уравнений на ненулевую константу,
• перестановка уравнений,
• прибавление к уравнению любого другого уравнения системы.

Метод Гаусса включает последовательное выполнение двух этапов. На первом этапе, который называется прямой ход, исходная система линейных уравнений при помощи последовательного исключения неизвестных приводится к верхнему треугольному виду. При выполнении обратного хода (второй этап алгоритма) осуществляется определение значений неизвестных.

Последовательный алгоритм

Прямой ход состоит в последовательном исключении неизвестных в уравнениях решаемой системы линейных уравнений.

На итерации i, метода производится исключение неизвестной i для всех уравнений с номерами k, больших i(т.е.) Для этого из этих уравнений осуществляется вычитание строки i, умноженной на константу с тем, чтобы результирующий коэффициент при неизвестной в строках оказался нулевым – все необходимые вычисления могут быть определены при помощи соотношений:

( 7.4)

intuit.ru/2010/edi»>где — множители Гаусса.

В итоге приходим к системе с верхней треугольной матрицей

При выполнении прямого хода метода Гаусса строка, которая используется для исключения неизвестных, носит наименование ведущей, а диагональный элемент ведущей строки называется ведущим элементом. Как можно заметить, выполнение вычислений является возможным только, если ведущий элемент имеет ненулевое значение. Более того, если ведущий элемент

имеет малое значение, то деление и умножение строк на этот элемент может приводить к накоплению вычислительной погрешности и вычислительной неустойчивости алгоритма.

Избежать подобной проблемы можно, если при выполнении каждой очередной итерации прямого хода метода Гаусса определить коэффициент с максимальным значением по абсолютной величине в столбце, соответствующем исключаемой неизвестной, т. е.

и выбрать в качестве ведущей строку, в которой этот коэффициент располагается (данная схема выбора ведущего значения носит наименование метода главных элементов).

Обратный ход алгоритма состоит в следующем. После приведения матрицы коэффициентов к верхнему треугольному виду становится возможным определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной

, после этого из предпоследнего уравнения становится возможным определение переменной

и т.д. В общем виде выполняемые вычисления при обратном ходе метода Гаусса могут быть представлены при помощи соотношений:

Оценим трудоемкость метода Гаусса. При выполнении прямого хода число операций составит

Для выполнения обратного хода потребуется

intuit.ru/2010/edi»>Таким образом, общее время выполнения метода Гаусса при больших n можно оценить как

где время выполнения одной операции.

Параллельный алгоритм

При внимательном рассмотрении метода Гаусса можно заметить, что все вычисления сводятся к однотипным вычислительным операциям над строками матрицы коэффициентов системы линейных уравнений. Как результат, в основу параллельной реализации алгоритма Гаусса может быть положен принцип распараллеливания по данным. В качестве базовой подзадачи можно принять тогда все вычисления, связанные с обработкой одной строки матрицы A и соответствующего элемента вектора b. Рассмотрим общую схему параллельных вычислений и возникающие при этом информационные зависимости между базовыми подзадачами.

Для выполнения прямого хода метода Гаусса необходимо осуществить итерацию по исключению неизвестных для преобразования матрицы коэффициентов A к верхнему треугольному виду. Выполнение итерации i, , прямого хода метода Гаусса включает ряд последовательных действий. Прежде всего, в самом начале итерации необходимо выбрать ведущую строку, которая при использовании метода главных элементов определяется поиском строки с наибольшим по абсолютной величине значением среди элементов столбца i, соответствующего исключаемой переменной . Зная ведущую строку, подзадачи выполняют вычитание строк, обеспечивая тем самым исключение соответствующей неизвестной .

При выполнении обратного хода метода Гаусса подзадачи выполняют необходимые вычисления для нахождения значения неизвестных. Как только какая-либо подзадача i, , определяет значение своей переменной , это значение должно быть использовано всеми подзадачам с номерами k, : подзадачи подставляют полученное значение новой неизвестной и выполняют корректировку значений для элементов вектора b.

Выделенные базовые подзадачи характеризуются одинаковой вычислительной трудоемкостью. Однако размер матрицы, описывающей систему линейных уравнений, является существенно большим, чем число потоков в программе (т.е.,), и базовые подзадачи можно укрупнить, объединив в рамках одной подзадачи несколько строк матрицы. При этом применение последовательной схемы разделения данных для параллельного решения систем линейных уравнений приведет к неравномерной вычислительной нагрузке между потоками: по мере исключения (на прямом ходе) или определения (на обратном ходе) неизвестных в методе Гаусса для большей части потоков все необходимые вычисления будут завершены и они окажутся простаивающими. Возможное решение проблемы балансировки вычислений может состоять в использовании ленточной циклической схемы для распределения данных между укрупненными подзадачами. В этом случае матрица A делится на наборы (полосы) строк вида (см. рис. 7.1).

Рис. 7.1. Ленточная схема

intuit.ru/2010/edi»>Сопоставив схему разделения данных и порядок выполнения вычислений в методе Гаусса, можно отметить, что использование циклического способа формирования полос позволяет обеспечить лучшую балансировку вычислительной нагрузки между подзадачами.

Итак, проведя анализ последовательного варианта алгоритма Гаусса, можно заключить, что распараллеливание возможно для следующих вычислительных процедур:

• поиск ведущей строки,
• вычитание ведущей строки из всех строк, подлежащих обработке,
• выполнение обратного хода.

Оценим трудоемкость рассмотренного параллельного варианта метода Гаусса. Пусть n есть порядок решаемой системы линейных уравнений, а p, , обозначает число потоков. При разработке параллельного алгоритма все вычислительные операции, выполняемые алгоритмом Гаусса, были распределены между потоками параллельной программы. Следовательно, время, необходимое для выполнения вычислений на этапе прямого хода, можно оценить как

Подставив выражение получим, что время выполнения вычислений для параллельного варианта метода Гаусса описывается выражением:

Теперь можно оценить величину накладных расходов, обусловленных организацией и закрытием параллельных секций. Пусть – время, необходимое на организацию и закрытие параллельной секции. Параллельная секция создается при каждом выборе ведущей строки, при выполнении вычитания ведущей строки из остальных строк линейной системы, подлежащих обработке, а также при выполнении каждой итерации обратного хода метода Гаусса. Таким образом, общее число параллельных секций составляет .

Сводя воедино все полученные оценки можно заключить, что время выполнения параллельного метода Гаусса описывается соотношением

( 7. 5)

Связь метода Гаусса и LU-разложения

LU-разложение — представление матрицы A в виде

( 7.6)

где L — нижняя треугольная матрица с диагональными элементами, равными единице, а U — верхняя треугольная матрица с ненулевыми диагональными элементами. LU-разложение также называют LU-факторизацией. Известно [4], что LU-разложение существует и единственно, если главные миноры матрицы A отличны от нуля.

Алгоритм LU-разложения тесно связан с методом исключения Гаусса. В самом деле, пусть мы решаем систему уравнений вида (7. 2). Непосредственно проверяется, что преобразования k-го шага метода Гаусса равносильны домножению системы (7.2) слева на матрицу

где — множители Гаусса из (7.4). Как было рассмотрено в п. 7.1.1, прямой ход метода Гаусса преобразует исходную систему уравнений к виду

с верхней треугольной матрицей U. Зная матрицы , можно записать матрицу U и вектор c как

Обозначим Можно непосредственно проверить, что

Отсюда получаем .

Таким образом, матрицу L можно получить как нижнюю треугольную матрицу коэффициентов Гаусса, а матрицу U — как верхнюю треугольную матрицу, получаемую в результате работы метода Гаусса. При этом очевидно, что трудоемкость получения LU-факторизации будет такой же-.

ru/2010/edi»>Рассмотренный нами алгоритм LU-факторизации реализован с помощью исключения по столбцу. Следует отметить, что можно сформулировать аналогичный алгоритм, основанный на исключении по строке. В самом деле, основная идея алгоритма с помощью исключения по столбцу заключается в том, что на i-й итерации ведущая строка с подходящими множителями вычитается из строк, лежащих ниже, чтобы занулить все элементы матрицы, расположенные в i-м столбце ниже диагонали. Между тем возможно и другое: на каждой i-й итерации можно вычитать из i-й строки все строки, расположенные выше, умноженные на подходящие коэффициенты, так, чтобы занулить все элементы i-й строки левее диагонали. При этом элементы матрицы L ниже главной диагонали и элементы матрицы U на главной диагонали и выше нее можно вычислять на месте матрицы А. Как и в случае исключения по столбцу, приведенная схема требует проведения операций

Рассмотрим теперь еще один способ LU-факторизаци, называемый компактной схемой. Пусть матрица допускает LU-разложение (7.6), где

т.е. при а при . Из соотношения (7.6) следует, что

Преобразуем эту сумму двумя способами:

Отсюда находим

Оценка числа операций данного алгоритма LUфакторизаци также составляет

Если разложение (7.6) получено, то решение системы (7.2) сводится к последовательному решению двух систем уравнений с треугольными матрицами (обратный ход)

( 7.7)

Обратный ход требует операций.

Как следует из приведенных оценок, вычислительная сложность метода исключения Гаусса и метода LU-разложения одинакова. Однако если необходимо решить несколько систем с одинаковыми матрицами коэффициентов, но различными векторами свободных членов (правая часть СЛАУ), то метод LU-разложения окажется предпочтительным, так как в этом случае нет необходимости производить разложение матрицы коэффициентов многократно. Достаточно лишь сохранить полученные треугольные матрицы в памяти и, подставляя различные вектора свободных членов, получать решения методами прямой и обратной подстановки. Это позволит значительно сократить объем вычислений по сравнению с методом Гаусса.

Разреженная матрица – LearnDataSci

Автор: Фатих Карабибер
Кандидат наук. кандидат вычислительной техники, специалист по данным

Разреженная матрица — это частный случай матрицы, в которой количество нулевых элементов намного превышает количество ненулевых элементов. Как правило, если 2/3 всех элементов в матрице составляют нули, ее можно назвать разреженной матрицей. При использовании разреженного матричного представления, в котором хранятся только ненулевые значения, пространство, используемое для представления данных, и время сканирования матрицы значительно сокращаются.

Многие приложения в науке о данных и машинном обучении используют разреженные матрицы, такие как:

• Обработка естественного языка : Встречаемость слов в документах может быть представлена ​​в разреженной матрице. Слова в документе — это лишь небольшое подмножество слов в языке. Если у нас есть строка для каждого документа и столбец для каждого слова, то сохранение количества вхождений слова в документе имеет высокий процент нулей в каждом столбце.
• Системы рекомендаций : Разреженная матрица может использоваться для представления того, смотрел ли какой-либо конкретный пользователь какой-либо фильм. См. пример в нашей статье о локальном хешировании (LSH).
• Анализ рыночной корзины : Поскольку количество купленных товаров ничтожно мало по сравнению с количеством не купленных товаров, для представления всех товаров и клиентов используется разреженная матрица.

Возьмем в качестве примера систему рекомендаций фильмов. Существуют миллионы пользователей и тысячи фильмов, поэтому пользователи не могут смотреть и оценивать все фильмы. Эти данные можно представить в виде матрицы, где строки — это пользователи, а столбцы — фильмы.

Большинство элементов матрицы будут пустыми, где отсутствующие значения будут заменены нулями. Поскольку небольшой процент матрицы имеет ненулевые значения, эту матрицу можно считать разреженной матрицей. Небольшая часть данных приведена ниже:

Разреженность этой матрицы можно рассчитать, получив отношение нулевых элементов к общему количеству элементов. В этом примере разреженность рассчитывается как:

$$\begin{align} разреженность &= \frac {n_{zeros}}{n_{total}} \\[.5em] &= \frac{26}{35 } \\[.5em] &= 0,742 \end{align}$$

Видно, что количество нулей в разреженной матрице очень велико. Представление всех нулевых значений в такой матрице привело бы к большому использованию памяти, поэтому на практике сохраняются только ненулевые значения разреженной матрицы.

Другим примером может быть использование матрицы для представления встречаемости слов в документах. Размерность матрицы терминов-документов будет равна $n \times m$, где $n$ — количество документов, а $m$ — количество слов в языковой модели. В результате большинство элементов матрицы будут нулевыми, поскольку для анализа данных важны только ненулевые значения. В дополнение к большому объему используемого пространства возникнет проблема времени вычислений, поскольку все элементы будут сканироваться для доступа к ненулевым элементам. Этот процесс приводит к проблеме вычислительной сложности.

Чтобы преодолеть эти проблемы, мы можем использовать различные структуры данных для представления разреженной матрицы. Одним из распространенных форматов представления разреженной матрицы является список координат (COO) , который использует трехэлементные кортежи для хранения координат ненулевых значений в матрице. Например, следующая таблица может быть построена для представления разреженной матрицы термин-документ:

В этой таблице индексы строк и столбцов с ненулевыми значениями хранятся в разреженном представлении. Пусть $k$ — количество ненулевых элементов в матрице размера $n \times m$, тогда долю пространства, сэкономленного разреженным матричным представлением, можно просто вычислить следующим образом:

$$ p = 1- \frac{3k}{nm} $$

Пространство, полученное при представлении разреженной матрицы, прямо пропорционально значению разреженности.

Существует множество других способов представления разреженной матрицы, например Словарь ключей (DOK) и Список списков (LIL) . В следующем разделе будут объяснены различные форматы представления с помощью Python.

Библиотека Scipy предоставляет пакет scipy.sparse для создания разреженных матриц и управления ими (https://docs.scipy.org/doc/scipy/reference/sparse.html. Различные форматы представления и некоторые полезные функции для разреженных матриц определены в этом пакете.

Здесь мы рассмотрим некоторые основные функции.

Будет построена простая разреженная матрица, чтобы показать форматы представления разреженной матрицы в Python.

 импортировать numpy как np
из scipy import sparse 

 X = np.array([[0,0,0,3,0,0,4],
              [0,5,0,0,0,0,0],
              [0,0,5,0,0,4,0],
              [4,0,0,0,0,0,1],
              [0,2,0,0,3,0,0]])
print(X) 

Выход:

 [[0 0 0 3 0 0 4]
 [0 5 0 0 0 0 0]
 [0 0 5 0 0 4 0]
 [4 0 0 0 0 0 1]
 [0 2 0 0 3 0 0]] 

В этой матрице много нулей, поэтому давайте посчитаем разреженность матрицы:

 разреженность = 1.0 - (np.count_nonzero(X) / X.size)
print('Разреженность X равна ', разреженность ) 

Out:

 Разреженность X равна 0,7428571428571429 

Мы можем преобразовать эту плотную матрицу в разреженную матрицу с помощью функции trix() . csr0556 sparse().csr0_matrix. Индексы строк/столбцов ненулевых значений хранятся в матрице сжатых разреженных строк (CSR):

 # Преобразование X в разреженную матрицу
S1 = разреженная.csr_matrix(X)
распечатать(ф"""
Тип представления разреженной матрицы: {type(S1)}
Разреженная матрица:\n{S1}
Разреженные данные: {S1.data}
Индексы столбцов: {S1.indices}
Указатели на данные: {S1.indptr}
""") 

Выход:

 Тип представления разреженной матрицы: 
Разреженная матрица:
  (0, 3) 3
  (0, 6) 4
  (1, 1) 5
  (2, 2) 5
  (2, 5) 4
  (3, 0) 4
  (3, 6) 1
  (4, 1) 2
  (4, 4) 3
Разреженные данные: [3 4 5 5 4 4 1 2 3]
Индексы столбцов: [3 6 1 2 5 0 6 1 4]
Указатели на данные: [0 2 3 5 7 9] 

Другой эффективной структурой для построения разреженных матриц является Dictionary Of Keys (DOK) , где словарь python используется для представления ненулевых значений для разреженной матрицы.

В этом представлении keys() используется для индексов, а values() используется для значений ненулевых элементов:

 S2 = sparse.dok_matrix(X)
распечатать(ф"""
Тип представления разреженной матрицы: {type(S2)}
Разреженная матрица:\n{S2}
Ключи в словаре: {S2.keys()}
Значения в словаре: {S2.values()}
""") 

Выход:

 Тип представления разреженной матрицы: 
Разреженная матрица:
  (0, 3) 3
  (0, 6) 4
  (1, 1) 5
  (2, 2) 5
  (2, 5) 4
  (3, 0) 4
  (3, 6) 1
  (4, 1) 2
  (4, 4) 3
Ключи в словаре: dict_keys([(0, 3), (0, 6), (1, 1), (2, 2), (2, 5), (3, 0), (3, 6), ( 4, 1), (4, 4)])
Значения в словаре: dict_values([3, 4, 5, 5, 4, 4, 1, 2, 3]) 

Последний формат представления, показанный здесь, представляет собой построчный список разреженных списков (LIL) матрица. В первом списке хранятся индексы столбцов для каждой строки, а во втором списке хранятся значения строк элемента.

 S3 = разреженная.lil_matrix(X)
распечатать(ф"""
Тип представления разреженной матрицы: {type(S3)}
Разреженная матрица:\n{S3}
Списки для строк: {S3.rows}
Списки для столбцов: {S3.data}
""") 

Выход:

 Тип представления разреженной матрицы: 
Разреженная матрица:
  (0, 3) 3
  (0, 6) 4
  (1, 1) 5
  (2, 2) 5
  (2, 5) 4
  (3, 0) 4
  (3, 6) 1
  (4, 1) 2
  (4, 4) 3
Списки для строк: [список ([3, 6]) список ([1]) список ([2, 5]) список ([0, 6]) список ([1, 4])]
Списки для столбцов: [список ([3, 4]) список ([5]) список ([5, 4]) список ([4, 1]) список ([2, 3])] 

В пакете scipy.sparse также есть функция todense() для преобразования разреженной матрицы в плотную матрицу:

 # Преобразование разреженной матрицы в плотную матрицу
X = S1. todense()
print(X) 

Выход:

 [[0 0 0 3 0 0 4]
 [0 5 0 0 0 0 0]
 [0 0 5 0 0 4 0]
 [4 0 0 0 0 0 1]
 [0 2 0 0 3 0 0]] 

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

Мы будем использовать набор данных групп новостей , доступный непосредственно из sklearn, чтобы показать пример использования разреженной матрицы. Этот набор данных содержит тысячи новостных сообщений по 20 различным темам.

Документ может быть представлен в виде вектора терминов, где каждый термин является характеристикой, а значение представляет собой количество раз, когда соответствующий термин встречается в документе. Таким образом, матрица может использоваться для представления вхождений слов во всех документах, где документы представляют собой строки, а термины — столбцы. Поскольку количество ненулевых значений будет небольшим, эту матрицу можно представить в виде разреженной матрицы.

Давайте импортируем и загрузим набор данных из sklearn:

 из sklearn.datasets import fetch_20newsgroups
newsgroups_train = fetch_20newsgroups(subset='train', category= ['sci.electronics', 'sci.space']) 

Предварительный просмотр примера записи в этом наборе данных:

 newsgroups_train.data[0] 

Out:

 "От: [email protected] (Крис Бест)\nТема: Re: Пищевые дегидраторы\nОрганизация: ваша служба\nЛинейки: 10\nРаспространение: США\nNNTP-хост: hpctdkz.col.hp.com\n \n> Есть ли у кого-нибудь дегидратор для пищевых продуктов, который я видел\n> в последнее время по ночному телевидению? Мне интересно, используют ли они принудительную подачу воздуха, тепло\n> или и то, и другое. Если задействовано тепло , кто-нибудь знает, при какой температуре они работают?\n> Моя жена хотела бы такой, а я не склонен платить >100 долларов за коробку, вентилятор\n> и обогреватель.  Мне кажется, вы должны быть в состоянии бросить вместе с дегидратором\n> всего за несколько баксов. Черт возьми, технологии всего 1000 лет?\n\n----------\n\nДа, но 1000 лет назад вы не могли' нельзя покупать у парня с накрашенными волосами!\n" 

Теперь мы будем использовать CountVectorizer для векторизации текста в матрицу документа термина:

 из sklearn.feature_extraction.text import CountVectorizer
cv = CountVectorizer()
cv.fit (группы новостей_train.data)
# Создаем матрицу терминов-документов
word_matrix = cv.transform(newsgroups_train.data) 

 print(f'Тип матрицы: {type(word_matrix)}\n')
print(f'Matrix:\n{word_matrix}') 

Out:

 Тип матрицы: 
Матрица:
  (0, 0) 1
  (0, 1) 1
  (0, 187) 1
  (0, 188) 1
  (0, 189) 1
  (0, 3013) 1
  (0, 3387) 1
  (0, 3424) 1
  (0, 3502) 1
  (0, 3688) 2
  (0, 3794) 2
  (0, 4144) 1
  (0, 4514) 1
  (0, 4557) 1
  (0, 4650) 1
  (0, 4936) 1
  (0, 4962) 1
  (0, 5127) 1
  (0, 5225) 1
  (0, 5234) 1
  (0, 5360) 1
  (0, 5912) 1
  (0, 6180) 2
  (0, 6237) 2
  (0, 6822) 1
  : :
  (1183, 20345) 1
  (1183, 20370) 1
  (1183, 20381) 1
  (1183, 20386) 1
  (1183, 20398) 2
  (1183, 20416) 1
  (1183, 20509) 1
  (1183, 20548) 11
  (1183, 20975) 1
  (1183, 21002) 2
  (1183, 21077) 2
  (1183, 21224) 1
  (1183, 21305) 1
  (1183, 21344) 3
  (1183, 21345) 2
  (1183, 21358) 1
  (1183, 21541) 1
  (1183, 21892) 1
  (1183, 22075) 1
  (1183, 22096) 1
  (1183, 22139) 1
  (1183, 22233) 2
  (1183, 22318) 3
  (1183, 22347) 1
  (1183, 22478) 5 

 print(f'Размер матрицы: {word_matrix. shape}') 

Выход:

 Размер матрицы: (1184, 22577) 

 print(f'Число Ненулевые значения: {word_matrix.nnz}') 

Исходящие:

 Количество ненулевых значений: 174709 

Далее мы можем вычислить разреженность:

 разреженность = word_matrix.nnz / (word_matrix .shape[0] * word_matrix.shape[1])
print('Значение разреженности: ', разреженность) 

Выход:

 Значение разреженности: 0,006535778758339329 

Преобразование разреженной матрицы в плотную:

 D = word_matrix. todense()
print(D) 

Выход:

 [[1 1 0 ... 0 0 0]
 [0 0 0 ... 0 0 0]
 [0 0 0 ... 0 0 0]
 ...
 [0 2 0 ... 0 0 0]
 [0 1 0 ... 0 0 0]
 [0 0 0 ... 0 0 0]] 

С плотной версией мы можем рассчитать долю пространства, сэкономленного разреженным матричным представлением:

 r = 1 - (3 * np.count_nonzero(D)) / D. размер
print('Доля сэкономленного места равна ', r) 

Вышло:

 Доля сэкономленного места: 0,980392663724982 

Учебники по структурам данных — Разреженная матрица на примере

Разместите здесь свое объявление

 Предыдущий Далее 

В компьютерном программировании матрица может быть определена с помощью двумерного массива. Любой массив с ‘m’ столбцами и ‘n’ строками представляет собой матрицу m X n. Может возникнуть ситуация, когда матрица содержит больше НУЛЕВЫХ значений, чем НЕНУЛЕВЫХ. Такая матрица известна как разреженная матрица.

Разреженная матрица — это матрица, содержащая очень мало ненулевых элементов.

Когда разреженная матрица представлена ​​двумерным массивом, мы тратим много места на представление этой матрицы. Например, рассмотрим матрицу размером 100 X 100, содержащую только 10 ненулевых элементов. В этой матрице только 10 ячеек заполнены ненулевыми значениями, а остальные ячейки матрицы заполнены нулями. Это означает, что всего мы выделяем 100 X 100 X 2 = 20000 байт пространства для хранения этой целочисленной матрицы. И чтобы получить доступ к этим 10 ненулевым элементам, нам нужно произвести сканирование 10000 раз. Для простоты мы используем следующее представление разреженной матрицы.

Разреженная матрица может быть представлена ​​с помощью ДВУХ представлений, а именно…

1. Триплетное представление (представление в виде массива)
2. Связанное представление

Триплетное представление (представление в виде массива)

В этом представлении мы рассматриваем только ненулевые значения вместе с их значениями индексов строк и столбцов. В этом представлении строка 0 ^th хранит общее количество строк, общее количество столбцов и общее количество ненулевых значений в разреженной матрице.

Например, рассмотрим матрицу размера 5 X 6, содержащую 6 ненулевых значений. Эта матрица может быть представлена, как показано на рисунке…

В приведенном выше примере матрицы есть только 6 ненулевых элементов (это 9, 8, 4, 2, 5 и 2), а размер матрицы равен 5. X 6. Мы представляем эту матрицу, как показано на изображении выше. Здесь первая строка в правой таблице заполнена значениями 5, 6 и 6, что указывает на то, что это разреженная матрица с 5 строками, 6 столбцами и 6 ненулевыми значениями. Вторая строка заполнена 0, 4 и 9что указывает, что ненулевое значение 9 находится в 4-м столбце 0-й строки в разреженной матрице. Точно так же остальные ненулевые значения также следуют аналогичному шаблону.

 #include
использование пространства имен std;
основной ()
{
    // разреженная матрица класса 5x6 с 6 ненулевыми значениями
    int разреженнаяМатрица[5][6] =
    {
        {0, 0, 0, 0, 9, 0},
        {0, 8, 0, 0, 0, 0},
        {4, 0, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 5},
        {0, 0, 2, 0, 0, 0}
    };
    // Нахождение всех ненулевых значений в разреженной матрице
    целочисленный размер = 0;
    for (целая строка = 0; строка < 5; строка ++)
        for (целый столбец = 0; столбец < 6; столбец++)
            если (sparseMatrix[строка][столбец] != 0)
                размер++;
    // Определение матрицы результатов
    intresultMatrix[3][размер];
    // Генерация матрицы результатов
    инт к = 0;
    for (целая строка = 0; строка < 5; строка ++)
        for (целый столбец = 0; столбец < 6; столбец++)
            если (sparseMatrix[строка][столбец] != 0)
            {
                матрица результатов[0][k] = строка;
                матрица результатов[1][k] = столбец;
                resultMatrix[2][k] = sparseMatrix[строка][столбец];
                к++;
            }
    // Отображение матрицы результатов
    cout<<"Триплетное представление: "<
 Выходные данные
 Связанное представление 
 В связанном представлении мы используем структуру данных связанного списка для представления разреженной матрицы. В этом связанном списке мы используем два разных узла, а именно узел заголовка   и узел элемента  . Узел заголовка состоит из трех полей, а узел элемента состоит из пяти полей, как показано на рисунке...
 Рассмотрим приведенную выше ту же разреженную матрицу, которая используется в представлении Triplet. Эта разреженная матрица может быть представлена ​​с помощью связанного представления, как показано на рисунке ниже...
 В приведенном выше представлении H0, h2,..., H5 указывают узлы заголовков, которые используются для представления индексов. Остальные узлы используются для представления ненулевых элементов в матрице, за исключением самого первого узла, который используется для представления абстрактной информации разреженной матрицы (т. Е. Это матрица 5 X 6 с 6 ненулевыми элементами).
 В этом представлении в каждой строке и столбце правое поле последнего узла указывает на соответствующий узел заголовка.