ВВЕДЕНИЕ В РАЗРЕЖЕННЫЕ МАТРИЦЫ SPARSE MATRIX

другую разреженную матрцу,

массивы с индексами строк и столбцов и сами значенния.

Разреженные матрицы Scipy имеют полезные методы для конвертации в плотные (
или
), сжатые строкой (
) и сжатые столбцом (
).

Как создать список координат в Scipy

Создадим разреженную матрицу на основе плотной матрицы из предыдущей статьи. Пример кода на Python того, как создаются разреженные матрицы Scipy:

import numpy as np
import scipy.sparse as sparse

arr = np.array([
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 2, 1, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 3, 0],
])

print(sparse.coo_matrix(arr))

# Результат:
(0, 1) 1
(1, 2) 2
(1, 3) 1
(1, 6) 1
(3, 3) 1
(3, 5) 3

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

Мы могли бы также передать массивы индексов строк и столбцов с ненулевыми значениями. Вот так это выглядит в Python:

import numpy as np
import scipy.sparse as sparse

rows = [0, 1, 1, 1, 3 ,3]
cols = [1, 2, 3, 6, 3, 5]
data = [1, 2, 1, 1, 1, 3]

coo = sparse.coo_matrix((data, (rows, cols)))
# Результат тот же, что и выше

Преимущества списка координат:

обеспечивает быстрое преобразование между разреженными форматами, например, CSR и CSC;

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

Недостатки списка координат:

• не поддерживает напрямую арифметические операции и извлечение подматриц (slicing).

Как создать с форматом сжатого хранения строкой (CSS) в Scipy

Сжатое хранение строкой (Compressed Sparse Row, CSR) подразумевает подсчет кумулятивной суммы количества элементов в строке вместо индексов строк.

В Python-библиотеке Scipy для создания разреженных матриц с сжатым хранением строкой используется функция csr_matrix
:

  # `arr' тот же, что и выше
csr = sparse.csr_matrix(arr)
print(csr)

# Результат:
(0, 1) 1
(1, 2) 2
(1, 3) 1
(1, 6) 1
(3, 3) 1
(3, 5) 3  

Разреженные матрицы данного формата поддерживают арифметические операции: сложение, вычитание, умножение, деление и возведение в степень.

Преимущества сжатого хранения строкой:

• эффективные операции с матрицами такого же формата (CSR + CSR, CSR * CSR и т.д.);
• эффективное извлечение строк;
• быстрое умножение матриц.

Недостатки сжатого хранения строкой:

• медленное извлечение столбцов;
• медленное преобразование в форматы список списков (LIL)
  и словарь ключей (DOK)
  .

Как создать с форматом сжатого хранения столбцом (CSС) в Scipy

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

В Python-библиотеке Scipy для создания разреженных матриц с сжатым хранением столбцом используется функция csc_matrix
:

  csc = sparse.csc_matrix(arr)
print(csc)

# Результат:
(0, 1) 1
(1, 2) 2
(1, 3) 1
(3, 3) 1
(3, 5) 3
(1, 6) 1  

Обратите внимание, что последними элементами идет 3, а затем 1, поскольку подсчет происходит по столбам, а столбец с со значением 3 встречается раньше значения 1.

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

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

         

        

        

        

    # coordinate-value format
# (1, 1)        2
# (3, 4)        5
# (0, 2)        9
# (2, 3)        1
# (4, 3)        6

    # coo.toarray() for ndarray instead

      
              
              
              
              
              

  

    
        # data memory and overhead memory
                
                           
        
          
            
        

  
# Sparse: 480
# Dense: 448

   

  
# Sparse: 480
# Dense: 80112

  

      

       # store value 42 at coordinate (3, 7)

     # zero elements are accessible
 

      # union of key views
    

   
 

  

      

      # works as expected
    

    

    
     

    # fix issue by removing bad point

      # don't get me started
       

  

       

       # set individual point

          # set two points

     # set main diagonal

          # set entire column

  

        
                
                
              
                
                

  

   

         
          

     # expose jagged structure

  
        
       
          
        
        

  

     # module docstring
 'LInked List sparse matrix class

  

       # convert format

  
       

  
        

  
        

  

    

     
# 111 µs ± 3.66 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

      # another way to convert

     
# 251 µs ± 8.06 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

    

       # order of magnitude slower!
# 632 ms ± 2.02 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

  

        # can use dense arrays

     

          # can use lists

      # can use sparse arrays

       # zeros to create column gap

             
                   
                    

     
              

    # ipython previous output

          
                 
                 
                 
                 
                 
                 
                 
                 
                 
                 

  

       # replace cutoff data

  

         
                
             

    # same array repr as earlier

        
               
               
                
                
                
                

  

Специализированные функции

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

Подробное рассмотрение этих деталей оставлено в качестве упражнения для заядлого читателя.

Другие библиотеки

SciPy — не единственный ресурс для работы с разреженными структурами в экосистеме Python.
Хотя большинство из них, похоже, используют пакет SciPy для внутренних целей, все они сделали его собственным.
Я представлю несколько библиотек, которые кажутся мне наиболее интересными, но это не должно быть концом всего.

Панды

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

      

    

    # uses a MultiIndex for the coordinates

       
       
       
       
       
       
       
        
       
        
       
       
  

   
   

         

    

    # class inheritance hierarchy


 
 
 
 
 
 
 

       # not restricted to null values

   

           
 

     

  

Scikit-Learn

Мощный инструмент машинного обучения, Scikit-Learn
, поддерживает разреженные матрицы во многих областях.
Это важно, поскольку большие данные процветают на разреженных матрицах (при условии достаточной разреженности).
В конце концов, кто бы не хотел получить прирост производительности от этих алгоритмов обработки чисел?
Больно ждать SVM с интенсивным использованием ЦП
, не говоря уже о том, что некоторые данные не помещаются в рабочую память!

Матрицы терминов-документов Scikit-Learn, созданные с помощью векторизаторов текста
результат в матрицах CSR.
Это крайне важно для НЛП, поскольку большинство слов используются редко, если вообще используются.
В противном случае наивное использование плотного формата может привести к узким местам в скорости и большой потере памяти.

      

    

  
 

     # store for future use

  

Другие области, в которых Scikit-Learn имеет возможность выводить разреженные матрицы, включают:

• sklearn.preprocessing. OneHotEncoder
• sklearn.preprocessing. МеткаБинаризатор
• sklearn.feature_extraction. ДиктВекторизатор

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

Разреженные PyData

В качестве еще одной реализации разреженная библиотека PyData
предоставляет интерфейс типа np.ndarray
вместо np.matrix
, позволяющий создавать многомерные разреженные массивы.
Предостережение: на момент написания этой статьи поддерживаются только форматы COO и DOK.

        # avoid name clobbering with scipy.sparse

         # 3-D sparse array

  
       

      # not possible in scipy.sparse

  
         # fill_value updates!

  

                 
                         
                         
                         

                        
                 
          
                         

                        
                 
                         
                         

  

      # scipy COO
           
                # leverage existing base class
    
            # self & other
             
    
            
               

  

К сожалению НЕТ ( ~
) невозможно, так как это превратило бы разреженную матрицу в плотную (теоретически self - 1
).
До сих пор так и есть.
Как видно ранее, sparse
будет динамически обновлять значение заполнения в соответствии с текущими состояниями.

Заключительные мысли

Надеюсь, эта статья объяснила, как правильно использовать разреженные структуры данных, чтобы вы могли с уверенностью использовать их в будущих проектах.
Знание плюсов и минусов каждого формата (в том числе плотного) поможет выбрать оптимальный для конкретной задачи.
Помните, что хотя разреженные матрицы и являются отличным инструментом, они не обязательно являются заменой массивов.
Если матрица недостаточно разрежена, множество скрытых массивов хранения фактически займут больше ресурсов, чем обычный плотный массив.
Более того, если вам нужно регулярно изменять массив, выполнять промежуточные вычисления и отображать выходные данные, то разреженность просто не стоит усилий.
Но если отбросить все эти опасения, будем надеяться, что разреженные матрицы помогут «облегчить» вашу нагрузку.

Сравнение форматов матриц

† BSR повышает NotImplementedError:
а не явно повышать TypeError: 'xxx_matrix' object is not subscriptable
. Так что, возможно, в будущем он будет поддерживать индексацию.

‡ При условии достаточного количества NNZ.

     # the end :D

  

Код, используемый для создания вышеуказанных анимаций, находится по адресу моего GitHub
.