精华内容
下载资源
问答
  • SciPy中稀疏矩阵的处理

    千次阅读 2018-10-06 18:07:14
    矩阵中,若数值为0的元素数目远远多于非0元素的数目,并且非0元素分布没有规律时,则称该矩阵为稀疏矩阵。 ——来自百度百科。 为什么会用到稀疏矩阵,最近在做协同过滤算法时,调用...知识来源:Scipy Lectur...

    在矩阵中,若数值为0的元素数目远远多于非0元素的数目,并且非0元素分布没有规律时,则称该矩阵为稀疏矩阵。    ——来自百度百科。

    为什么会用到稀疏矩阵,最近在做协同过滤算法时,调用评分图和信任图,数据的稀疏程度达到99.9%,这样的数据存储到内存中,0会占据大量的内存,本想无所谓,但奈何内存放不下这样的数据量,无奈进行稀疏矩阵的存储与计算。记录下学习笔记。

    知识来源:Scipy Lecture Nodes 中文版

    先举一个小栗子,展示双精度数据大小和内存之间的关系图

    import numpy as np
    import matplotlib.pyplot as plt
    
    x = np.linspace(0, 1e6, 10)
    plt.plot(x, 8.0 * (x**2) / 1e6, lw=5)
    plt.xlabel('size n')
    plt.ylabel('memory [MB]')
    plt.show()
    

    显示结果

    稀疏矩阵的存储:

    稀疏矩阵作为一个矩阵,绝大多数都是0,为空。存储所有的0是浪费。 

    所以想办法进行压缩。节省大量内存空间。

    稀疏矩阵的可视化图(样例):

    scipy.sparse中有七类稀疏矩阵:

    csc_matrix: 压缩列格式
    csr_matrix: 压缩行格式
    bsr_matrix: 块压缩行格式
    lil_matrix: 列表的列表格式
    dok_matrix: 值的字典格式
    coo_matrix: 座标格式 (即 IJV, 三维格式)
    dia_matrix: 对角线格式

    每一个类型适用于一些任务
    许多都利用了由Nathan Bell提供的稀疏工具 C ++ 模块

      • 算术操作的默认实现
        • 通常转化为CSR
        • 为了效率而子类覆盖
      • 形状、数据类型设置/获取
      • 非0索引
      • 格式转化、与Numpy交互(toarray(), todense())
      • ...
    • 属性:

      • mtx.A - 与mtx.toarray()相同
      • mtx.T - 转置 (与mtx.transpose()相同)
      • mtx.H - Hermitian (列举) 转置
      • mtx.real - 复矩阵的真部
      • mtx.imag - 复矩阵的虚部
      • mtx.size - 非零数 (与self.getnnz()相同)
      • mtx.shape - 行数和列数 (元组)
    • 数据通常储存在Numpy数组中

    对角线格式 (DIA)

    形状 (n_diag, length) 的密集Numpy数组的对角线。固定长度距离当离主对角线比较远时会浪费空间。_data_matrix的子类 (带数据属性的稀疏矩阵类)
    每个对角线的偏移:0 是主对角线,负偏移 = 下面,正偏移 = 上面
    快速矩阵 * 向量 (sparsetools)(*代表矩阵相乘)
    构建器接受 :1、密集矩阵 (数组);2、稀疏矩阵;3、形状元组 (创建空矩阵);4、(数据, 偏移) 元组
    没有切片、没有单个项目访问
    用法 : 通过有限微分解偏微分方程;有一个迭代求解器

    举例DIA矩阵

    【1】

    import numpy as np
    import scipy.sparse as sparse
    import matplotlib.pyplot as plt
    
    data = np.array([[1, 2, 3, 4]]).repeat(3, axis=0)
    offsets = np.array([0, -1, 2])
    mtx = sparse.dia_matrix((data, offsets), shape=(4, 4))
    print(mtx)
    

         

    由此可以看出,mtx是一个4*4的矩阵,mtx的值,我是真不知道为什么,跪求高人指点,网友说看下面的图能看懂了,可能我脑回路有问题,我是真没看懂

    è¿éåå¾çæè¿°

    【2】右图为大神给的解释图,但是我还是有点问题

    dia_matrix源码:

    【3】矩阵相乘

    列表格式(LIL)

    基于行的连接列表。1、每一行是一个Python列表(排序的)非零元素的列索引;2、行存储在Numpy数组中 (dtype=np.object);3、非零值也近似存储
    高效增量构建稀疏矩阵
    构建器接受 :1、密集矩阵 (数组);2、稀疏矩阵;3、形状元组 (创建一个空矩阵)

    举例LIL矩阵

    【1】

    【2】,更多的切片和索引

    字典格式 (DOK)

    Python字典的子类:1、键是 (行, 列) 索引元组 (不允许重复的条目);2、值是对应的非零值
    高效增量构建稀疏矩阵
    构建器支持:1、密集矩阵 (数组);2、稀疏矩阵;3、形状元组 (创建空矩阵)
    高效 O(1) 对单个元素的访问
    一旦创建完成后可以被高效转换为coo_matrix
    算术很慢 (循环用dict.iteritems())
    用法:当稀疏模式是未知的假设或改变时

    座标格式 (COO)

    称为 ‘ijv’ 或 ‘triplet’ 格式:1、三个NumPy数组: row, col, data;2、data[i]是在 (row[i], col[i]) 位置的值;3、允许重复值
    构建稀疏矩阵的高速模式
    构建器接受:1、密集矩阵 (数组);2、稀疏矩阵;3、形状元组 (创建空数组);4、(data, ij)元组
    可以与CSR/CSC格式非常快的互相转换
    快速的矩阵 * 向量 (sparsetools)
    快速而简便的逐项操作:直接操作数据数组 (快速NumPy机制)
    没有切片,没有算术 (直接)
    使用:1、在各种稀疏格式间的灵活转换;2、当转化到其他形式 (通常是 CSR 或 CSC), 重复的条目被加总到一起

    case【1】

    行格式 (CSR)

    面向行
    三个Numpy数组: indices, indptr, data

    1. indices是列索引的数组
    2. data是对应的非零值数组
    3. indptr指向indices和data开始的行
    4. 长度是n_row + 1, 最后一个项目 = 值数量 = indices和data的长度
    5. 第i行的非零值是列索引为indices[indptr[i]:indptr[i+1]]的data[indptr[i]:indptr[i+1]]
    6. 项目 (i, j) 可以通过data[indptr[i]+k], k是j在indices[indptr[i]:indptr[i+1]]的位置来访问

    快速矩阵向量相乘和其他算术 (sparsetools)
    构建器接受:1、密集矩阵 (数组);2、稀疏矩阵;3、形状元组 (创建空矩阵);4、(data, ij) 元组;5、(data, indices, indptr) 元组
    高效行切片,面向行的操作
    较慢的列切片,改变稀疏结构代价昂贵

    用途:

    1. 实际计算 (大多数线性求解器都支持这个格式)

    case

    【1】用(data, indices, indptr)元组创建:

    解释下mtx.indptr,mtx.indices

    # 对于第i行,非0数据列是indices[indptr[i]:indptr[i+1]] 数据是data[indptr[i]:indptr[i+1]]
    # 第0行,有非0的数据列是indices[indptr[0]:indptr[1]] = indices[0:2] = [0,2]
    # 数据是data[indptr[0]:indptr[1]] = data[0:2] = [1,2],所以在第0行第0列是1,第0行第2列是2
    # 第1行,有非0的数据列是indices[indptr[1]:indptr[2]] = indices[2:3] = [2]
    # 数据是data[indptr[1]:indptr[2] = data[2:3] = [3],所以在第1行第2列是3
    # 第2行,有非0的数据列是indices[indptr[2]:indptr[3]] = indices[3:6] = [0,1,2]
    # 数据是data[indptr[2]:indptr[3]] = data[3:6] = [4,5,6],所以在第2行第0列是4,第2行第1行是5,第2行第2列是6

    【2】用(data, ij)元组创建:

    列格式 (CSC) (与CSR类似)

    三个Numpy数组: indices、indptr、data

    1. indices是行
    2. 索引的数组
    3. data是对应的非零值
    4. indptr指向indices和data开始的列
    5. 长度是n_col + 1, 最后一个条目 = 值数量 = indices和data的长度
    6. 第i列的非零值是行索引为indices[indptr[i]:indptr[i+1]]的data[indptr[i]:indptr[i+1]]
    7. 项目 (i, j) 可以作为data[indptr[j]+k]访问, k是i在indices[indptr[j]:indptr[j+1]]的位置

    快速矩阵向量相乘和其他算术 (sparsetools)
    构建器接受:1、密集矩阵 (数组);2、稀疏矩阵;3、形状元组 (创建空矩阵);4、(data, ij)元组;5、(data, indices, indptr)元组
    高效列切片、面向列的操作
    较慢的行切片、改变稀疏结构代价昂贵
    用途:

    1. 实际计算 (巨大多数线性求解器支持这个格式)

    case

    【1】用(data, indices, indptr)元组创建:

    解释下mtx.indptr,mtx.indices

    # 对于第i列,非0数据行是indices[indptr[i]:indptr[i+1]] 数据是data[indptr[i]:indptr[i+1]]
    # 第0列,有非0的数据行是indices[indptr[0]:indptr[1]] = indices[0:2] = [0,2]
    # 数据是data[indptr[0]:indptr[1]] = data[0:2] = [1,2],所以在第0列第0行是1,第0列第2行是2
    # 第1列,有非0的数据行是indices[indptr[1]:indptr[2]] = indices[2:3] = [2]
    # 数据是data[indptr[1]:indptr[2] = data[2:3] = [3],所以在第1列第2行是3
    # 第2列,有非0的数据行是indices[indptr[2]:indptr[3]] = indices[3:6] = [0,1,2]
    # 数据是data[indptr[2]:indptr[3]] = data[3:6] = [4,5,6],所以在第2列第0行是4,第2列第1行是5,第2列第2行是6

    【2】用(data, ij)元组创建:

    块压缩行格式 (BSR)

    CSR带有密集的固定形状的子矩阵而不是纯量的项目
    块大小(R, C)必须可以整除矩阵的形状(M, N)
    三个Numpy数组: indices、indptr、data

    1. indices是每个块列索引的数组
    2. data是形状为(nnz, R, C)对应的非零值

    快速矩阵向量相乘和其他的算术 (sparsetools)
    构建器接受:1、密集矩阵 (数组);2、稀疏矩阵;3、形状元组 (创建空的矩阵);4、(data, ij)元组;5、(data, indices, indptr)元组
    许多对于带有密集子矩阵的稀疏矩阵算术操作比CSR更高效很多
    用途:

    1. 类似CSR

    case

    【1】(data, ij)元组创建:

    【2】用块大小(data, indices, indptr)的元组创建:

    展开全文
  • SciPy教程 - 稀疏矩阵scipy.sparse

    万次阅读 多人点赞 2014-12-06 00:15:33
    sparse模块的官方document:http://docs.scipy.org/doc/scipy/reference/sparse.html 一、sparse matrix稀疏矩阵不同的存储形式在sparse模块中对应如下 bsr_matrix(arg1[, sh

    http://blog.csdn.net/pipisorry/article/details/41762945

    稀疏矩阵在Python科学计算中的实际意义

    对于那些零元素数目远远多于非零元素数目,并且非零元素的分布没有规律的矩阵称为稀疏矩阵(sparse)。

    由于稀疏矩阵中非零元素较少,零元素较多,因此可以采用只存储非零元素的方法来进行压缩存储。对于一个用二维数组存储的稀疏矩阵Amn,如果假设存储每个数组元素需要L个字节,那么存储整个矩阵需要m*n*L个字节。但是,这些存储空间的大部分存放的是0元素,从而造成大量的空间浪费。为了节省存储空间,可以只存储其中的非0元素。大大减少了空间的存储。

    另外对于很多元素为零的稀疏矩阵,仅存储非零元素可使矩阵操作效率更高。也就是稀疏矩阵的计算速度更快,因为只对非零元素进行操作,这是稀疏矩阵的一个突出的优点。

    python不能自动创建稀疏矩阵,所以要用scipy中特殊的命令来得到稀疏矩阵。

    皮皮blog



    稀疏矩阵的常用存储格式

    对于很多元素为零的稀疏矩阵,仅存储非零元素可使矩阵操作效率更高。现有许多种稀疏矩阵的存储方式,但是多数采用相同的基本技术,即存储矩阵所有的非零元素到一个线性数组中,并提供辅助数组来描述原数组中非零元素的位置。

    Sparse Matrix Storage Formats稀疏矩阵的存储格式

    1. Coordinate Format (COO)

    是一种坐标形式的稀疏矩阵。采用三个数组row、col和data保存非零元素的信息,这三个数组的长度相同,row保存元素的行,col保存元素的列,data保存元素的值。存储的主要优点是灵活、简单,仅存储非零元素以及每个非零元素的坐标。但是COO不支持元素的存取和增删,一旦创建之后,除了将之转换成其它格式的矩阵,几乎无法对其做任何操作和矩阵运算。

    COO使用3个数组进行存储:values,rows, andcolumn。

    其中

    数组values: 实数或复数数据,包括矩阵中的非零元素,顺序任意。

    数组rows: 数据所处的行。

    数组columns: 数据所处的列。

    参数:矩阵中非零元素的数量 nnz,3个数组的长度均为nnz.

    2. Diagonal Storage Format (DIA)

    如果稀疏矩阵有仅包含非0元素的对角线,则对角存储格式(DIA)可以减少非0元素定位的信息量。这种存储格式对有限元素或者有限差分离散化的矩阵尤其有效。

    DIA通过两个数组确定: values、distance。

    其中values:对角线元素的值;

    distance:第i个distance是当前第i个对角线和主对角线的距离。

    If the sparse matrix has diagonals containing only zero elements, then the diagonal storage format can be used to reduce the amount of information needed to locate the non-zero elements. This storage format is particularly useful in many applications where the matrix arises from a finite element or finite difference discretization.

    The Intel MKL diagonal storage format is specified by two arrays:values anddistance, and two parameters:ndiag, which is the number of non-empty diagonals, andlval, which is the declared leading dimension in the calling (sub)programs. 

    values

    A real or complex two-dimensional array is dimensioned aslval byndiag. Each column of it contains the non-zero elements of certain diagonal ofA. The key point of the storage is that each element invalues retains the row number of the original matrix. To achieve this diagonals in the lower triangular part of the matrix are padded from the top, and those in the upper triangular part are padded from the bottom. Note that the value ofdistance(i) is the number of elements to be padded for diagonali.

    distance

    An integer array with dimension ndiag. Elementi of the arraydistance is the distance betweeni-diagonal and the main diagonal. The distance is positive if the diagonal is above the main diagonal, and negative if the diagonal is below the main diagonal. The main diagonal has a distance equal to zero.

    3. Compressed Sparse Row Format (CSR)

    压缩稀疏行格式(CSR)通过四个数组确定: values,columns, pointerB, pointerE.

    其中

    数组values:是一个实(复)数,包含矩阵A中的非0元,以行优先的形式保存;数组columns:第i个整型元素代表矩阵A中第i列;

    数组pointerB :第j个整型元素给出矩阵A行j中第一个非0元的位置,等价于pointerB(j) -pointerB(1)+1 ;

    数组pointerE:第j个整型元素给出矩阵A第j行最后一个非0元的位置,等价于pointerE(j)-pointerB(1)。

    The Intel MKL compressed sparse row (CSR) format is specified by four arrays: thevalues,columns,pointerB, andpointerE. The following table describes the arrays in terms of the values, row, and column positions of the non-zero elements in a sparse matrixA.

    values

    A real or complex array that contains the non-zero elements ofA. Values of the non-zero elements ofA are mapped into thevalues array using the row-major storage mapping described above.

    columns

    Element i of the integer array columns is the number of the column inA that contains thei-th value in thevalues array.

    pointerB

    Element j of this integer array gives the index of the element in thevalues array that is first non-zero element in a rowj ofA. Note that this index is equal topointerB(j) -pointerB(1)+1 .

    pointerE

    An integer array that contains row indices, such thatpointerE(j)-pointerB(1) is the index of the element in thevalues array that is last non-zero element in a row j of A.

    4. Compressed Sparse Column Format (CSC)

    压缩稀疏列格式(CSC)类似CSR格式,只是用的是列而不是行压缩。换句话说,矩阵A的CSC 格式和矩阵A的转置的CSR是一样的。

    同样CSC也是由四个数组确定:values, columns, pointerB, and pointerE. 含义类同CSR。

    The compressed sparse column format (CSC) is similar to the CSR format, but the columns are used instead the rows. In other words, the CSC format is identical to the CSR format for the transposed matrix. The CSR format is specified by four arrays: values, columns, pointerB, and pointerE. The following table describes the arrays in terms of the values, row, and column positions of the non-zero elements in a sparse matrixA.

    values

    A real or complex array that contains the non-zero elements ofA. Values of the non-zero elements ofA are mapped into thevalues array using the column-major storage mapping.

    rows

    Element i of the integer array rows is the number of the row inA that contains thei-th value in thevalues array.

    pointerB

    Element j of this integer array gives the index of the element in thevalues array that is first non-zero element in a columnj ofA. Note that this index is equal topointerB(j) -pointerB(1)+1 .

    pointerE

    An integer array that contains column indices, such thatpointerE(j)-pointerB(1) is the index of the element in thevalues array that is last non-zero element in a column j ofA.

    5. Skyline Storage Format

    The skyline storage format is important for the direct sparse solvers, and it is well suited for Cholesky or LU decomposition when no pivoting is required.

    The skyline storage format accepted in Intel MKL can store only triangular matrix or triangular part of a matrix. This format is specified by two arrays:values andpointers. The following table describes these arrays:

    values

    A scalar array. For a lower triangular matrix it contains the set of elements from each row of the matrix starting from the first non-zero element to and including the diagonal element. For an upper triangular matrix it contains the set of elements from each column of the matrix starting with the first non-zero element down to and including the diagonal element. Encountered zero elements are included in the sets.

    pointers

    An integer array with dimension (m+1), where m is the number of rows for lower triangle (columns for the upper triangle).pointers(i) -pointers(1)+1 gives the index of element invalues that is first non-zero element in row (column)i. The value ofpointers(m+1) is set tonnz+pointers(1), wherennz is the number of elements in the arrayvalues.

    6. Block Compressed Sparse Row Format (BSR)

    原矩阵A:


    block_size为2时,分块表示的压缩矩阵E:


    BSR的zero-based索引表示:

                                         values  =  (1 02 1 6 7 8 2 1 4 5 1 4 3 0 0 7 2 0 0)

                                         columns  = (0  1   1   1   2)

                                         pointerB= (0   2  3)

                                         pointerE= (2   3  5)

            分块压缩稀疏行格式(BSR) 通过四个数组确定:values,columns,pointerB, pointerE.

             其中数组values:是一个实(复)数,包含原始矩阵A中的非0元,以行优先的形式保存;

    数组columns:第i个整型元素代表块压缩矩阵E中第i列;

    数组pointerB :第j个整型元素给出columns第j个非0块的起始位置;

    数组pointerE:第j个整型元素给出columns数组中第j个非0块的终止位置。


    The Intel MKL block compressed sparse row (BSR) format for sparse matrices is specified by four arrays:values,columns,pointerB, andpointerE. The following table describes these arrays.

    values

    A real array that contains the elements of the non-zero blocks of a sparse matrix. The elements are stored block-by-block in row-major order. A non-zero block is the block that contains at least one non-zero element. All elements of non-zero blocks are stored, even if some of them is equal to zero. Within each non-zero block elements are stored in column-major order in the case of one-based indexing, and in row-major order in the case of the zero-based indexing.

    columns

    Element i of the integer array columns is the number of the column in the block matrix that contains thei-th non-zero block.

    pointerB

    Element j of this integer array gives the index of the element in thecolumns array that is first non-zero block in a rowj of the block matrix.

    pointerE

    Element j of this integer array gives the index of the element in thecolumns array that contains the last non-zero block in a rowj of the block matrix plus 1.

    7.  ELLPACK (ELL)

    8. Hybrid (HYB)  


    由ELL+COO两种格式结合而成。

    dok_matrix

    基于keys的字典稀疏矩阵。

    lil_matrix

    基于行链接列表的稀疏矩阵,增量式创建稀疏矩阵的结构。

    [Sparse Matrix Storage Formats]

    [NathanBell1-10-1000.pdf]

    [Sparse Matrix Representations & Iterative Solvers, Lesson 1 by Nathan Bell]

    [稀疏矩阵的存储格式(Sparse Matrix Storage Formats)]

    [Intel MKL 库中使用的稀疏矩阵格式]

    皮皮blog



    不同稀疏矩阵的优缺点和使用经验

    sparse matrix稀疏矩阵不同的存储形式在sparse模块中对应如下:
    bsr_matrix(arg1[, shape, dtype,copy, blocksize]) Block Sparse Row matrix
    coo_matrix(arg1[, shape, dtype,copy]) A sparse matrix in COOrdinate format.
    csc_matrix(arg1[, shape, dtype,copy]) Compressed Sparse Column matrix
    csr_matrix(arg1[, shape, dtype,copy]) Compressed Sparse Row matrix
    dia_matrix(arg1[, shape, dtype,copy]) Sparse matrix with DIAgonal storage
    dok_matrix(arg1[, shape, dtype,copy]) Dictionary Of Keys based sparse matrix.
    lil_matrix(arg1[, shape, dtype,copy]) Row-based linked list sparse matrix

    scipy不同稀疏矩阵的介绍和优缺点

    scipy.sparse库中提供了多种表示稀疏矩阵的格式,每种格式都有不同的用处。同时稀疏矩阵可以支持加、减、乘、除和幂等算术操作。Sparse matrices can be used in arithmetic operations: they support addition, subtraction, multiplication, division,and matrix power.

    分块压缩稀疏行格式(BSR)bsr_matrix(arg1, shape=None, dtype=None, copy=False, blocksize=None)Block Sparse Row matrix:

    和压缩稀疏行格式(CSR)很相似,但是BSR更适合于有密集子矩阵的稀疏矩阵,分块矩阵通常出现在向量值有限的离散元中,在这种情景下,比CSR和CSC算术操作更有效。The Block Compressed Row (BSR) format is very similar to the Compressed Sparse Row (CSR) format. BSR is appropriate for sparse matrices with dense sub matrices. Block matrices often arise in vector-valued finite element discretizations. In such cases, BSR is considerably more efficient than CSR and CSC for many sparse arithmetic operations.

    csc_matrix(arg1,shape=None, dtype=None, copy=False)压缩的列稀疏矩阵CSC :

    高效的CSC +CSC, CSC * CSC算术运算;高效的列切片操作。但是矩阵内积操作没有CSR, BSR快;行切片操作慢(相比CSR);稀疏结构的变化代价高(相比LIL 或者 DOK)。

    Advantages of the CSC format
    •efficient arithmetic operations CSC + CSC, CSC * CSC, etc.
    •efficient column slicing
    •fast matrix vector products (CSR, BSR may be faster!)
    Disadvantages of the CSC format
    •slow row slicing operations (consider CSR)
    •changes to the sparsity structure are expensive (consider LIL or DOK)

    csr_matrix(arg1, shape=None, dtype=None, copy=False)Compressed Sparse Row matrix压缩稀疏行格式(CSR):

    高效的CSR + CSR, CSR *CSR算术运算;高效的行切片操作;高效的矩阵内积内积操作。但是列切片操作慢(相比CSC);稀疏结构的变化代价高(相比LIL 或者 DOK)。CSR格式在存储稀疏矩阵时非零元素平均使用的字节数(Bytes per Nonzero Entry)最为稳定(float类型约为8.5,double类型约为12.5)。CSR格式常用于读入数据后进行稀疏矩阵计算。

    Advantages of the CSR format
    •efficient arithmetic operations CSR + CSR, CSR * CSR, etc.
    •efficient row slicing
    •fast matrix vector products
    Disadvantages of the CSR format
    •slow column slicing operations (consider CSC)
    •changes to the sparsity structure are expensive (consider LIL or DOK)

    coo_matrix(arg1,shape=None,dtype=None,copy=False)坐标格式(COO):

    坐标形式的一种稀疏矩阵。采用三个数组row、col和data保存非零元素的信息。这三个数组的长度相同,row保存元素的行,col保存元素的列,data保存元素的值。

    coo_matrix不支持元素的存取和增删,一旦创建之后,除了将之转换成其它格式的矩阵,几乎无法对其做任何操作和矩阵运算。

    Advantages of the COO format
    •facilitates fast conversion among sparse formats
    •permits duplicate entries (see example)
    •very fast conversion to and from CSR/CSC formats

    优点:便利快捷的在不同稀疏格式间转换;允许重复录入,允许重复的元素;从CSR\CSC格式转换非常快速。
    Disadvantages of the COO format
    •does not directly support:
    –arithmetic operations
    –slicing
    缺点:不能直接进行科学计算和切片操作

    COO格式常用于从文件中进行稀疏矩阵的读写,如matrix market即采用COO格式。

    最常用的函数:

    tocsc()

    Return a copy of this matrix in Compressed Sparse Column format

    tocsr()

    Return a copy of this matrix in Compressed Sparse Row format

    todense([order, out])

    Return a dense matrix representation of this matrix

    许多稀疏矩阵的数据都是采用这种格式保存在文件中的,例如某个CSV文件中可能有这样三列:“用户ID,商品ID,评价值”。采用numpy.loadtxt或pandas.read_csv将数据读入之后,可以通过coo_matrix快速将其转换成稀疏矩阵:矩阵的每行对应一位用户,每列对应一件商品,而元素值为用户对商品的评价。

    dia_matrix(arg1, shape=None, dtype=None, copy=False)Sparse matrix with DIAgonal storage

    对角存储格式(DIA)和ELL格式在进行稀疏矩阵-矢量乘积(sparse matrix-vector products)时效率最高,所以它们是应用迭代法(如共轭梯度法)解稀疏线性系统最快的格式;DIA格式存储数据的非零元素平均使用的字节数与矩阵类型有较大关系,适合于StructuredMesh结构的稀疏矩阵(float类型约为4.05,double类型约为8.10)。对于Unstructured Mesh以及Random Matrix,DIA格式使用的字节数是CSR格式的十几倍。

    dok_matrix(arg1, shape=None, dtype=None, copy=False)Dictionary Of Keys based sparse matrix.

    dok_matrix从dict继承,它采用字典保存矩阵中不为0的元素:字典的键是一个保存元素(行,列)信息的元组,其对应的值为矩阵中位于(行,列)中的元素值。显然字典格式的稀疏矩阵很适合单个元素的添加、删除和存取操作。通常用来逐渐添加非零元素,然后转换成其它支持快速运算的格式。

    基于字典存储的稀疏矩阵。

    This is an efficient structure for constructing sparse matrices incrementally.Allows for efficient O(1) access of individual elements. Duplicates are not allowed. Can be efficiently converted to a coo_matrix once constructed.

    lil_matrix(arg1, shape=None, dtype=None, copy=False)Row-based linked list sparse matrix
    This is an efficient structure for constructing sparse matrices incrementally.

    基于行连接存储的稀疏矩阵。lil_matrix使用两个列表保存非零元素。data保存每行中的非零元素,rows保存非零元素所在的列。这种格式也很适合逐个添加元素,并且能快速获取行相关的数据。

    Advantages of the LIL format
    •supports flexible slicing
    •changes to the matrix sparsity structure are efficient
    Disadvantages of the LIL format
    •arithmetic operations LIL + LIL are slow (consider CSR or CSC)
    •slow column slicing (consider CSC)
    •slow matrix vector products (consider CSR or CSC)
    Intended Usage
    •LIL is a convenient format for constructing sparse matrices
    •once a matrix has been constructed, convert to CSR or CSC format for fast arithmetic and matrix vector operations
    •consider using the COO format when constructing large matrices

    Note:{dok_matrix和lil_matrix适合逐渐添加元素}

    综合

    2. COO和CSR格式比起DIA和ELL来,更加灵活,易于操作;

    3. ELL的优点是快速,而COO优点是灵活,二者结合后的HYB格式是一种不错的稀疏矩阵表示格式;

    4. 根据Nathan Bell的工作:

    CSR格式在存储稀疏矩阵时非零元素平均使用的字节数(Bytes per Nonzero Entry)最为稳定(float类型约为8.5,double类型约为12.5)

    而DIA格式存储数据的非零元素平均使用的字节数与矩阵类型有较大关系,适合于StructuredMesh结构的稀疏矩阵(float类型约为4.05,double类型约为8.10)

    对于Unstructured Mesh以及Random Matrix,DIA格式使用的字节数是CSR格式的十几倍;

    5. 一些线性代数计算库:COO格式常用于从文件中进行稀疏矩阵的读写,如matrix market即采用COO格式,而CSR格式常用于读入数据后进行稀疏矩阵计算。

    [scipy-ref-0.14.0 - Sparse matrices (scipy.sparse)]

    [用Python做科学计算-第二版SciPy-数值计算库-稀疏矩阵-sparse]

    皮皮blog




    scipy.sparse稀疏矩阵的调用格式及参数、属性、方法说明

    sparse matrix稀疏矩阵不同的存储形式在sparse模块中对应如下:

    调用格式及参数说明:

    arg1:密集矩阵或者另一个稀疏矩阵;

    shape=(M, N):创建的稀疏矩阵的shape为(M, N)未指定时从索引数组中推断;

    dtype:稀疏矩阵元素类型,默认为’d’;

    copy:bool类型,是否进行深拷贝,默认False。

    其中BSR特有的参数blocksize:分块矩阵分块大小,而且必须被矩阵shape (M,N)整除。未指定时会自动使用启发式方法找到合适的分块大小。

    坐标格式(COO) :

    coo_matrix(arg1[, shape, dtype,copy])

    [coo_matrix]

     

    对角存储格式(DIA) :

    dia_matrix(arg1[, shape, dtype,copy])

    [dia_matrix]

     

    压缩稀疏行格式(CSR) :

    csr_matrix(arg1[, shape, dtype,copy])

    [csr_matrix]

     

    压缩稀疏列格式(CSC) :

    csc_matrix(arg1[, shape, dtype,copy])

    [csc_matrix]

     

    分块压缩稀疏行格式(BSR) :

    bsr_matrix(arg1[, shape, dtype,copy,blocksize])

    [bsr_matrix]

    稀疏矩阵常用属性

    dtype        矩阵数据类型

    shape       (2-tuple)矩阵形状

    ndim         (int)矩阵维数

    nnz   非0元个数

    data矩阵的数据数组

    row  COO特有的,矩阵行索引

    col    COO特有的,矩阵列索引

    has_sorted_indices BSR有的,是否有排序索引

    indices      BSR特有的,BSR格式的索引数组

    indptr       BSR特有的,BSR格式的索引指针数组

    blocksize  BSR特有的,矩阵块大小

    等等

    稀疏矩阵常用方法

    asformat(format)    返回给定格式的稀疏矩阵

    astype(t)  返回给定元素格式的稀疏矩阵

    diagonal()         返回矩阵主对角元素

    dot(other)         坐标点积

    getcol(j) 返回矩阵列j的一个拷贝,作为一个(mx 1) 稀疏矩阵 (列向量)

    getrow(i) 返回矩阵行i的一个拷贝,作为一个(1 x n)  稀疏矩阵 (行向量)

    max([axis])       给定轴的矩阵最大元素

    nonzero() 非0元索引

    todense([order, out])       返回当前稀疏矩阵的密集矩阵表示

    sparse模块中用于创建稀疏矩阵的函数

    • eye(m[, n, k, dtype, format])

    Sparse matrix with ones on diagonal

    • identity(n[, dtype, format])

    Identity matrix in sparse format

    • kron(A, B[, format])

    kronecker product of sparse matrices A and B

    • kronsum(A, B[, format])

    kronecker sum of sparse matrices A and B

    • diags(diagonals[, offsets, shape, format, dtype])

    Construct a sparse matrix from diagonals.

    • spdiags(data, diags, m, n[, format])

    Return a sparse matrix from diagonals.

    • block_diag(mats[, format, dtype])

    Build a block diagonal sparse matrix from provided matrices.

    • tril(A[, k, format])

    Return the lower triangular portion of a matrix in sparse format

    • triu(A[, k, format])

    Return the upper triangular portion of a matrix in sparse format

    • bmat(blocks[, format, dtype])

    Build a sparse matrix from sparse sub-blocks

    • hstack(blocks[, format, dtype])

    Stack sparse matrices horizontally (column wise)

    • vstack(blocks[, format, dtype])

    Stack sparse matrices vertically (row wise)

    • rand(m, n[, density, format, dtype, ...])

    Generate a sparse matrix of the given shape and density with uniformly distributed values.

    • random(m, n[, density, format, dtype, ...])

    Generate a sparse matrix of the given shape and density  with randomly distributed values.

    皮皮blog



    sparse matrix稀疏矩阵的相关操作

    创建和查看稀疏矩阵

    以coo_matrix为例:

    1 直接将dense矩阵转换成稀疏矩阵
    A =coo_matrix([[1,2],[3,4]])
    print(A)
      (0, 0)    1
      (0, 1)    2
      (1, 0)    3
      (1, 1)    4
    
    2 按照相应存储形式的要求构建矩阵:
    row  = array([0,0,0,0,1,3,1])
    col  = array([0,0,0,2,1,3,1])
    data = array([1,1,1,8,1,1,1])
    
    matrix = coo_matrix((data, (row,col)), shape=(4,4))
    print(matrix)
    print(matrix.todense())
      (0, 0)    1
      (0, 0)    1
      (0, 0)    1
      (0, 2)    8
      (1, 1)    1
      (3, 3)    1
      (1, 1)    1
    [[3 0 8 0]
     [0 2 0 0]
     [0 0 0 0]
     [0 0 0 1]]

    Note:csr_matrix总是返回稀疏矩阵,而不会返回一维向量。即使csr_matrix([2,3])也返回矩阵。

    稀疏矩阵大小

    csr = csr_matrix([[1, 5], [4, 0], [1, 3]])
    print(csr.todense())    #todense()之后是<class 'numpy.matrixlib.defmatrix.matrix'>
    print(csr.shape)
    print(csr.shape[1])
    [[1 5]
     [4 0]
     [1 3]]
    (3, 2)
    2

    稀疏矩阵下标存取slice

    print(csr)
      (0, 0)    1
      (0, 1)    5
      (1, 0)    4
      (2, 0)    1
      (2, 1)    3
    print(csr[0]) #<class 'scipy.sparse.csr.csr_matrix'>
      (0, 0)    1
      (0, 1)    5
    print(csr[1,1])
    1
    
    print(csr[0,0])
    0
    
    for c in csr:    #每次读取csr中的一行 type(c) <class 'scipy.sparse.csr.csr_matrix'>
        print(c)
        break
      (0, 0)    1
      (0, 1)    5

    csr_mat = csr_matrix([1, 5, 0])
    print(csr_mat.todense())
    # print(type(csr_mat.nonzero()))  #<class 'tuple'>
    for row, col in csr_mat.nonzero():
        print(row, col, csr_mat[row, col])
    [[1 5 0]]
    0 0 1
    0 1 5

    将稀疏矩阵横向或者纵向合并

    from scipy.sparse import coo_matrix, vstack
    csr = csr_matrix([[1, 5, 5], [4, 0, 6], [1, 3, 7]])
    print(csr.todense())
    [[1 5 5]
     [4 0 6]
     [1 3 7]]
    csr2 = csr_matrix([[3, 0, 9]])
    print(csr2.todense())
    [[3 0 9]]
    print(vstack([csr, csr2]).todense())
    [[1 5 5]
     [4 0 6]
     [1 3 7]
     [3 0 9]]
    
    Note:如果合并数据形式不一样,不能合并。一个矩阵中的数据格式必须是相同的。
    diags函数建立稀疏的对角矩阵

    sparce矩阵的读取

    可以像常规矩阵一样通过下标读取。也可以通过getrow(i),gecol(i)读取特定的列或者特定的行,以及nonzero()读取非零元素的位置。
    对于大多数(似乎只处了coo之外)稀疏矩阵的存储格式,都可以进行slice操作,比如对于csc,csr。也可以进行arithmeticoperations,矩阵的加减乘除,速度很快。

    取矩阵的指定列数

    sub = matrix.getcol(1)    #'coo_matrix' object does not support indexing,不能使用matrix[1]
    print(sub)
      (1, 0)    2
    sub = matrix.todense()[:,[1,2]] #常规矩阵取指定列print(sub)
    [[0 8]
     [2 0]
     [0 0]
     [0 0]]

    稀疏矩阵点积计算

    A = csr_matrix([[1, 2, 0], [0, 0, 3]])
    print(A.todense())
    [[1 2 0]
     [0 0 3]]
    v = A.T
    print(v.todense())
    [[1 0]
     [2 0]
     [0 3]]
    d = A.dot(v)
    print(d)
    
      (0, 0)    5
      (1, 1)    9

    A = lil_matrix([[1, 2, 0], [0, 0, 3], [4, 0, 5]])
    v = array([1, 0, -1])
    s = datetime.datetime.now()
    for i in range(100000):
        d = A.dot(v)    #这里v是一个ndarray
    print(datetime.datetime.now() - s)
    
    计算时间:
    bsr:0:00:01.666072
    coo:1.04
    csc:0.93
    csr:0.90
    dia:1.06
    dok:1.57
    lil:11.37
    故推荐用csr计算点积
    
    csr_mat1 = csr_matrix([1, 2, 0])
    csr_mat2 = csr_matrix([1, 0, -1])
    similar = (csr_mat1.dot(csr_mat2.transpose()))   #这里csr_mat2也是一个csr_matrix
    print(type(similar))
    print(similar)
    print(similar[0, 0])
    <class 'scipy.sparse.csr.csr_matrix'>
      (0, 0)    1
    1
    

    scipy稀疏矩阵在文件中的读取(读取和保存稀疏矩阵)

    mmwrite(target, a[, comment, field, precision]) Writes the sparse or dense array a to a Matrix Market formatted file.

    mmread(source) Reads the contents of a Matrix Market file ‘filename’ into a matrix.<class 'scipy.sparse.coo.coo_matrix'>

    mminfo(source) Queries the contents of the Matrix Market file ‘filename’ to extract size and storage.

    def save_csr_mat(
            item_item_sparse_mat_filename=r'.\datasets\lastfm-dataset-1K\item_item_csr_mat.mtx'):
        random.seed(10)
        raw_user_item_mat = random.randint(0, 6, (3, 2))
        d = csr_matrix(raw_user_item_mat)
        print(d.todense())
        print(d)
        mmwrite(item_item_sparse_mat_filename, d)
        print("item_item_sparse_mat_file information: ")
        print(mminfo(item_item_sparse_mat_filename))
        k = mmread(item_item_sparse_mat_filename)
        print(k.todense())
    
    [[1 5]
     [4 0]
     [1 3]]  
    
      (0, 0)    1
      (0, 1)    5
      (1, 0)    4
      (2, 0)    1
      (2, 1)    3
    
    item_item_sparse_mat_file information: 
    (3, 2, 5, 'coordinate', 'integer', 'general')
    
    [[1 5]
     [4 0]
     [1 3]]
    
    保存的文件中的内容:
    %%MatrixMarket matrix coordinate integer general
    %
    3 2 5
    1 1 1
    1 2 5
    2 1 4
    3 1 1
    3 2 3
    
    Note:保存的文件拓展名应为.mtx

    [scipy-ref-0.14.0 -  Matrix Market files]

    其它用户参考[scipy.sparse用法精要]

    皮皮blog


    一种比较省内存的稀疏矩阵Python存储方案

    python字典模拟稀疏矩阵

    {lz觉得这种主要用于稀疏检索和存储,而不适合应用于计算}

        推荐系统中经常需要处理类似user_id, item_id, rating这样的数据,其实就是数学里面的稀疏矩阵,scipy中提供了sparse模块来解决这个问题。但scipy.sparse有很多问题不太合用:1、不能很好的同时支持data[i, ...]、data[..., j]、data[i, j]快速切片;2、由于数据保存在内存中,不能很好的支持海量数据处理。
        要支持data[i, ...]、data[..., j]的快速切片,需要i或者j的数据集中存储;同时,为了保存海量的数据,也需要把数据的一部分放在硬盘上,用内存做buffer。
        这里的解决方案比较简单,用一个类Dict的东西来存储数据,对于某个i(比如9527),它的数据保存在dict['i9527']里面,需要取出data[9527, ...]的时候,只要取出dict['i9527']即可,dict['i9527']原本是一个dict对象,储存某个j对应的值,为了节省内存空间,我们把这个dict以二进制字符串形式存储 。采用类Dict来存储数据的另一个好处是你可以随便用内存Dict或者其他任何形式的DBM,甚至传说中的 Tokyo Cabinet.
    [http:// blogread.cn/it/article/1229]
    [ How to Think Like a Computer Scientist 讲授了 dictionary 和如何 使用 dictionary 模拟稀疏矩阵。]

    sklearn特征提取中的稀疏情景

    加载字典的中的特征:类 DictVectorizer 可以把特征向量转化成标准的Python字典对象的一个列表,同时也是被scikit-learn的估计器使用的一个NumPy/SciPy体现(ndarray)
    即使处理时并不是特别快,python的字典有易于使用的优势,适用于稀疏情景(缺失特征不会被存储),存储特征的名字和值。
    特征哈希:类 FeatureHasher 是一个快速且低内存消耗的向量化方法,使用了 feature hashing 技术,或可称为”hashing trick”。没有像矢量化那样,为计算训练得到的特征建立哈西表,类 FeatureHasher 的实例使用了一个哈希函数来直接确定特征在样本矩阵中的列号。这样在可检查性上增加了速度减少了内存开销。这个类不会记住输入特征的形状,也没有 inverse_transform 方法。
    [ sklearn 特征提取]
    from: http://blog.csdn.net/pipisorry/article/details/41762945

    ref: [sparse模块的官方document]

    http://blog.sina.com.cn/s/blog_6a90ae320101aavg.html


    展开全文
  • 文章目录稀疏矩阵简介稀疏矩阵Scipy 矩阵存储矩阵属性通用方法稀疏矩阵分类COO - coo_matrix适用场景优缺点实例化方法特殊属性代码示例CSR - csr_matrix适用场景优缺点实例化特殊属性CSC - csc_matrix实例化特殊属性...

    原文链接 : https://dreamhomes.github.io/posts/202012311027.html


    稀疏矩阵

    • 稀疏矩阵

      • 具有少量非零项的矩阵 - Number of Non-Zero (NNZ) < 0.5
      • (在矩阵中,若数值0的元素数目远多于非0元素的数目,并且非0元素分布没有规律)
    • 矩阵的稠密度

      • 非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。

    Scipy 矩阵存储

    存储矩阵的一般方法是采用二维数组,其优点是可以随机地访问每一个元素,因而能够容易实现矩阵的各种运算。
    对于稀疏矩阵,它通常具有很大的维度,有时甚大到整个矩阵(零元素)占用了绝大部分内存
    采用二维数组的存储方法既浪费大量的存储单元来存放零元素,又要在运算中浪费大量的时间来进行零元素的无效运算。因此必须考虑对稀疏矩阵进行压缩存储(只存储非零元素)。

    from scipy import sparse
    help(sparse)
    
    '''
    Sparse Matrix Storage Formats
    There are seven available sparse matrix types:
    
            1. csc_matrix: Compressed Sparse Column format
            2. csr_matrix: Compressed Sparse Row format
            3. bsr_matrix: Block Sparse Row format
            4. lil_matrix: List of Lists format
            5. dok_matrix: Dictionary of Keys format
            6. coo_matrix: COOrdinate format (aka IJV, triplet format)
            7. dia_matrix: DIAgonal format
            8. spmatrix: Sparse matrix base clas
    '''
    

    矩阵属性

    from scipy.sparse import csr_matrix
    
    ### 共有属性
    mat.shape  # 矩阵形状
    mat.dtype  # 数据类型
    mat.ndim  # 矩阵维度
    mat.nnz   # 非零个数
    mat.data  # 非零值, 一维数组
    
    ### COO 特有的
    coo.row  # 矩阵行索引
    coo.col  # 矩阵列索引
    
    ### CSR\CSC\BSR 特有的
    bsr.indices    # 索引数组
    bsr.indptr     # 指针数组
    bsr.has_sorted_indices  # 索引是否排序
    bsr.blocksize  # BSR矩阵块大小
    

    通用方法

    import scipy.sparse as sp
    
    ### 转换矩阵格式
    tobsr()、tocsr()、to_csc()、to_dia()、to_dok()、to_lil()
    mat.toarray()  # 转为array
    mat.todense()  # 转为dense
    # 返回给定格式的稀疏矩阵
    mat.asformat(format)
    # 返回给定元素格式的稀疏矩阵
    mat.astype(t)  
    
    ### 检查矩阵格式
    issparse、isspmatrix_lil、isspmatrix_csc、isspmatrix_csr
    sp.issparse(mat)
    
    ### 获取矩阵数据
    mat.getcol(j)  # 返回矩阵列j的一个拷贝,作为一个(mx 1) 稀疏矩阵 (列向量)
    mat.getrow(i)  # 返回矩阵行i的一个拷贝,作为一个(1 x n)  稀疏矩阵 (行向量)
    mat.nonzero()  # 非0元索引
    mat.diagonal()   # 返回矩阵主对角元素
    mat.max([axis])  # 给定轴的矩阵最大元素
    
    ### 矩阵运算
    mat += mat     # 加
    mat = mat * 5  # 乘
    mat.dot(other)  # 坐标点积
    
    
    resize(self, *shape)
    transpose(self[, axes, copy])
    

    稀疏矩阵分类

    COO - coo_matrix

    Coordinate Matrix 对角存储矩阵

    • 采用三元组(row, col, data)(或称为ijv format)的形式来存储矩阵中非零元素的信息
    • 三个数组 rowcoldata 分别保存非零元素的行下标、列下标与值(一般长度相同)
    • coo[row[k]][col[k]] = data[k] ,即矩阵的第 row[k] 行、第 col[k] 列的值为 data[k]

    • row[0] = 1 , column[0] = 1 时, data[0] = 2 ,故 coo[1][1] = 2
    • row[3] = 0 , column[3] = 2 时, data[3] = 9 ,故 coo[0][3] = 9

    适用场景

    • 主要用来创建矩阵,因为coo_matrix无法对矩阵的元素进行增删改等操作
    • 一旦创建之后,除了将之转换成其它格式的矩阵,几乎无法对其做任何操作和矩阵运算

    优缺点

    优点

    • 转换成其它存储格式很快捷简便(tobsr()tocsr()to_csc()to_dia()to_dok()to_lil()
    • 能与CSR / CSC格式的快速转换
    • 允许重复的索引(例如在1行1列处存了值2.0,又在1行1列处存了值3.0,则转换成其它矩阵时就是2.0+3.0=5.0)

    缺点

    • 不支持切片和算术运算操作
    • 如果稀疏矩阵仅包含非0元素的对角线,则对角存储格式(DIA)可以减少非0元素定位的信息量
    • 这种存储格式对有限元素或者有限差分离散化的矩阵尤其有效

    实例化方法

    • coo_matrix(D):D代表密集矩阵;

    • coo_matrix(S):S代表其他类型稀疏矩阵

    • coo_matrix((M, N), [dtype]):构建一个shape为M*N的空矩阵,默认数据类型是d

    • coo_matrix((data, (i, j)), [shape=(M, N)])):三元组初始化

      • i[:] : 行索引
      • j[:] : 列索引
      • A[i[k], j[k]]=data[k]

    特殊属性

    • data:稀疏矩阵存储的值,是一个一维数组
    • row:与data同等长度的一维数组,表征data中每个元素的行号
    • col:与data同等长度的一维数组,表征data中每个元素的列号

    代码示例

    # 数据
    row = [0, 1, 2, 2]
    col = [0, 1, 2, 3]
    data = [1, 2, 3, 4]
    
    # 生成coo格式的矩阵
    # <class 'scipy.sparse.coo.coo_matrix'>
    coo_mat = sparse.coo_matrix((data, (row, col)), shape=(4, 4),  dtype=np.int)
    
    # coordinate-value format
    print(coo)
    '''
    (0, 0)        1
    (1, 1)        2
    (2, 2)        3
    (3, 3)        4
    '''
    
    # 查看数据
    coo.data
    coo.row
    coo.col
    
    # 转化array
    # <class 'numpy.ndarray'>
    coo_mat.toarray()
    '''
    array([[1, 0, 0, 0],
           [0, 2, 0, 0],
           [0, 0, 3, 4],
           [0, 0, 0, 0]])
    '''
    

    CSR - csr_matrix

    Compressed Sparse Row Matrix 压缩稀疏行格式

    • csr_matrix是按行对矩阵进行压缩的

    • 通过 indices, indptrdata 来确定矩阵。

    • data 表示矩阵中的非零数据

    • 对于第 i 行而言,该行中非零元素的列索引为 indices[indptr[i]:indptr[i+1]]

    • 可以将 indptr 理解成利用其自身索引 i 来指向第 i 行元素的列索引

    • 根据[indptr[i]:indptr[i+1]],我就得到了该行中的非零元素个数,如

      • index[i] = 3index[i+1] = 3 ,则第 i 行的没有非零元素
      • index[j] = 6index[j+1] = 7 ,则第 j 行的非零元素的列索引为 indices[6:7]
    • 得到了行索引、列索引,相应的数据存放在: data[indptr[i]:indptr[i+1]]

    • 对于矩阵第 0 行,我们需要先得到其非零元素列索引

    • indptr[0] = 0indptr[1] = 2 可知,第 0 行有两个非零元素。

      • 它们的列索引为 indices[0:2] = [0, 2] ,且存放的数据为 data[0] = 8data[1] = 2
      • 因此矩阵第 0 行的非零元素 csr[0][0] = 8csr[0][2] = 2
    • 对于矩阵第 4 行,同样我们需要先计算其非零元素列索引

    • indptr[4] = 3indptr[5] = 6 可知,第 4 行有3个非零元素。

      • 它们的列索引为 indices[3:6] = [2, 3,4] ,且存放的数据为 data[3] = 7data[4] = 1data[5] = 2
      • 因此矩阵第 4 行的非零元素 csr[4][2] = 7csr[4][3] = 1csr[4][4] = 2

    适用场景

    • 常用于读入数据后进行稀疏矩阵计算,运算高效

    优缺点

    优点

    • 高效的稀疏矩阵算术运算
    • 高效的行切片
    • 快速地矩阵矢量积运算

    缺点

    • 较慢地列切片操作(可以考虑CSC)
    • 转换到稀疏结构代价较高(可以考虑LIL,DOK)

    实例化

    • csr_matrix(D):D代表密集矩阵;

    • csr_matrix(S):S代表其他类型稀疏矩阵

    • csr_matrix((M, N), [dtype]):构建一个shape为M*N的空矩阵,默认数据类型是d

    • csr_matrix((data, (row_ind, col_ind)), [shape=(M, N)]))

    • 三者关系:a[row_ind[k], col_ind[k]] = data[k]

    • csr_matrix((data, indices, indptr), [shape=(M, N)])

    • 第i行的列索引存储在其中indices[indptr[i]:indptr[i+1]]

      • 其对应值存储在中data[indptr[i]:indptr[i+1]]

    特殊属性

    • data :稀疏矩阵存储的值,一维数组
    • indices :存储矩阵有有非零值的列索引
    • indptr :类似指向列索引的指针数组
    • has_sorted_indices:索引 indices 是否排序
    # 生成数据
    indptr = np.array([0, 2, 3, 3, 3, 6, 6, 7])
    indices = np.array([0, 2, 2, 2, 3, 4, 3])
    data = np.array([8, 2, 5, 7, 1, 2, 9])
    
    # 创建矩阵
    csr = sparse.csr_matrix((data, indices, indptr))
    
    # 转为array
    csr.toarray()
    '''
    array([[8, 0, 2, 0, 0],
           [0, 0, 5, 0, 0],
           [0, 0, 0, 0, 0],
           [0, 0, 0, 0, 0],
           [0, 0, 7, 1, 2],
           [0, 0, 0, 0, 0],
           [0, 0, 0, 9, 0]])
    '''
    

    CSC - csc_matrix

    Compressed Sparse Column Matrix 压缩稀疏列矩阵

    • csc_matrix是按列对矩阵进行压缩的

    • 通过 indices, indptrdata 来确定矩阵,可以对比CSR

    • data 表示矩阵中的非零数据

    • 对于第 i 列而言,该行中非零元素的行索引为indices[indptr[i]:indptr[i+1]]

    • 可以将 indptr 理解成利用其自身索引 i 来指向第 i 列元素的列索引

    • 根据[indptr[i]:indptr[i+1]],我就得到了该行中的非零元素个数,如

      • index[i] = 1index[i+1] = 1 ,则第 i 列的没有非零元素
      • index[j] = 4index[j+1] = 6 ,则第 j列的非零元素的行索引为 indices[4:6]
    • 得到了列索引、行索引,相应的数据存放在: data[indptr[i]:indptr[i+1]]

    • 对于矩阵第 0 列,我们需要先得到其非零元素行索引

      • indptr[0] = 0indptr[1] = 1 可知,第 0列行有1个非零元素。
      • 它们的行索引为 indices[0:1] = [0] ,且存放的数据为 data[0] = 8
      • 因此矩阵第 0 行的非零元素 csc[0][0] = 8
    • 对于矩阵第 3 列,同样我们需要先计算其非零元素行索引

      • indptr[3] = 4indptr[4] = 6 可知,第 4 行有2个非零元素。
      • 它们的行索引为 indices[4:6] = [4, 6] ,且存放的数据为 data[4] = 1data[5] = 9
      • 因此矩阵第 i 行的非零元素 csr[4][3] = 1csr[6][3] = 9

    实例化

    • csc_matrix(D):D代表密集矩阵;

    • csc_matrix(S):S代表其他类型稀疏矩阵

    • csc_matrix((M, N), [dtype]):构建一个shape为M*N的空矩阵,默认数据类型是d

    • csc_matrix((data, (row_ind, col_ind)), [shape=(M, N)]))

      • 三者关系:a[row_ind[k], col_ind[k]] = data[k]
    • csc_matrix((data, indices, indptr), [shape=(M, N)])

      • 第i列的列索引存储在其中indices[indptr[i]:indptr[i+1]]
      • 其对应值存储在中data[indptr[i]:indptr[i+1]]

    特殊属性

    • data :稀疏矩阵存储的值,一维数组
    • indices :存储矩阵有有非零值的行索引
    • indptr :类似指向列索引的指针数组
    • has_sorted_indices :索引是否排序
    # 生成数据
    row = np.array([0, 2, 2, 0, 1, 2])
    col = np.array([0, 0, 1, 2, 2, 2])
    data = np.array([1, 2, 3, 4, 5, 6])
    
    # 创建矩阵
    csc = sparse.csc_matrix((data, (row, col)), shape=(3, 3)).toarray()
    
    # 转为array
    csc.toarray()
    '''
    array([[1, 0, 4],
           [0, 0, 5],
           [2, 3, 6]], dtype=int64)
    '''
    
    # 按col列来压缩
    # 对于第i列,非0数据行是indices[indptr[i]:indptr[i+1]] 数据是data[indptr[i]:indptr[i+1]]
    # 在本例中
    # 第0列,有非0的数据行是indices[indptr[0]:indptr[1]] = indices[0:2] = [0,2]
    # 数据是data[indptr[0]:indptr[1]] = data[0:2] = [1,2],所以在第0列第0行是1,第2行是2
    # 第1行,有非0的数据行是indices[indptr[1]:indptr[2]] = indices[2:3] = [2]
    # 数据是data[indptr[1]:indptr[2] = data[2:3] = [3],所以在第1列第2行是3
    # 第2行,有非0的数据行是indices[indptr[2]:indptr[3]] = indices[3:6] = [0,1,2]
    # 数据是data[indptr[2]:indptr[3]] = data[3:6] = [4,5,6],所以在第2列第0行是4,第1行是5,第2行是6
    

    BSR - bsr_matrix

    Block Sparse Row Matrix 分块压缩稀疏行格式

    • 基于行的块压缩,与csr类似,都是通过dataindicesindptr来确定矩阵

    • 与csr相比,只是data中的元数据由0维的数变为了一个矩阵(块),其余完全相同

    • 块大小 blocksize

      • 块大小 (R, C) 必须均匀划分矩阵 (M, N) 的形状。
      • R和C必须满足关系:M % R = 0N % C = 0
      • 适用场景及优点参考csr

    实例化

    • bsr_matrix(D):D代表密集矩阵;
    • bsr_matrix(S):S代表其他类型稀疏矩阵
    • bsr_matrix((M, N), [blocksize =(R,C), [dtype]):构建一个shape为M*N的空矩阵,默认数据类型是d
    • (data, ij), [blocksize=(R,C), shape=(M, N)]
    • 两者关系:a[ij[0,k], ij[1,k]] = data[k]]
    • bsr_matrix((data, indices, indptr), [shape=(M, N)])
    • 第i行的块索引存储在其中indices[indptr[i]:indptr[i+1]]
    • 其相应块值存储在中data[indptr[i]:indptr[i+1]]

    特殊属性

    • data :稀疏矩阵存储的值,一维数组
    • indices :存储矩阵有有非零值的列索引
    • indptr :类似指向列索引的指针数组
    • blocksize :矩阵的块大小
    • has_sorted_indices:索引 indices 是否排序

    代码示例

    # 生成数据
    indptr = np.array([0,2,3,6])
    indices = np.array([0,2,2,0,1,2])
    data = np.array([1,2,3,4,5,6]).repeat(4).reshape(6,2,2)
    
    # 创建矩阵
    bsr = bsr_matrix((data, indices, indptr), shape=(6,6)).todense()
    
    # 转为array
    bsr.todense()
    matrix([[1, 1, 0, 0, 2, 2],
            [1, 1, 0, 0, 2, 2],
            [0, 0, 0, 0, 3, 3],
            [0, 0, 0, 0, 3, 3],
            [4, 4, 5, 5, 6, 6],
            [4, 4, 5, 5, 6, 6]])
    

    优缺点

    优点

    • 与csr很类似
    • 更适合于适用于具有密集子矩阵的稀疏矩阵
    • 在某些情况下比csr和csc计算更高效。

    DOK-dok_matrix

    Dictionary of Keys Matrix 按键字典矩阵

    • 采用字典来记录矩阵中不为0的元素
    • 字典的 key 存的是记录元素的位置信息的元组, value 是记录元素的具体值

    适用场景

    • 逐渐添加矩阵的元素

    实例化方法

    • dok_matrix(D):D代表密集矩阵;
    • dok_matrix(S):S代表其他类型稀疏矩阵
    • dok_matrix((M, N), [dtype]):构建一个shape为M*N的空矩阵,默认数据类型是d

    优缺点

    优点

    • 对于递增的构建稀疏矩阵很高效,比如定义该矩阵后,想进行每行每列更新值,可用该矩阵。
    • 可以高效访问单个元素,只需要O(1)

    缺点

    • 不允许重复索引(coo中适用),但可以很高效的转换成coo后进行重复索引

    代码示例

    dok = sparse.dok_matrix((5, 5), dtype=np.float32)
    for i in range(5):
        for j in range(5):
            dok[i,j] = i+j    # 更新元素
    
    # zero elements are accessible
    dok[(0, 0)]  # = 0
    
    dok.keys()
    # {(0, 0), ..., (4, 4)}
    
    dok.toarray()
    '''
    [[0. 1. 2. 3. 4.]
     [1. 2. 3. 4. 5.]
     [2. 3. 4. 5. 6.]
     [3. 4. 5. 6. 7.]
     [4. 5. 6. 7. 8.]]
     '''
    

    LIL-lil_matrix

    Linked List Matrix 链表矩阵

    • 使用两个列表存储非0元素data
    • rows保存非零元素所在的列
    • 可以使用列表赋值来添加元素,如 lil[(0, 0)] = 8

    • lil[(0, -1)] = 4 :第0行的最后一列元素为4
    • lil[(4, 2)] = 5 :第4行第2列的元素为5

    适用场景

    • 适用的场景是逐渐添加矩阵的元素(且能快速获取行相关的数据)
    • 需要注意的是,该方法插入一个元素最坏情况下可能导致线性时间的代价,所以要确保对每个元素的索引进行预排序

    优缺点

    优点

    • 适合递增的构建成矩阵
    • 转换成其它存储方式很高效
    • 支持灵活的切片

    缺点

    • 当矩阵很大时,考虑用coo
    • 算术操作,列切片,矩阵向量内积操作慢

    实例化方法

    • lil_matrix(D):D代表密集矩阵;
    • lil_matrix(S):S代表其他类型稀疏矩阵
    • lil_matrix((M, N), [dtype]):构建一个shape为M*N的空矩阵,默认数据类型是d

    特殊属性

    • data:存储矩阵中的非零数据
    • rows:存储每个非零元素所在的列(行信息为列表中索引所表示)

    代码示例

    # 创建矩阵
    lil = sparse.lil_matrix((6, 5), dtype=int)
    
    # 设置数值
    # set individual point
    lil[(0, -1)] = -1
    # set two points
    lil[3, (0, 4)] = [-2] * 2
    # set main diagonal
    lil.setdiag(8, k=0)
    
    # set entire column
    lil[:, 2] = np.arange(lil.shape[0]).reshape(-1, 1) + 1
    
    # 转为array
    lil.toarray()
    '''
    array([[ 8,  0,  1,  0, -1],
           [ 0,  8,  2,  0,  0],
           [ 0,  0,  3,  0,  0],
           [-2,  0,  4,  8, -2],
           [ 0,  0,  5,  0,  8],
           [ 0,  0,  6,  0,  0]])
    '''
    
    # 查看数据
    lil.data
    '''
    array([list([0, 2, 4]), list([1, 2]), list([2]), list([0, 2, 3, 4]),
           list([2, 4]), list([2])], dtype=object)
    '''
    lil.rows
    '''
    array([[list([8, 1, -1])],
           [list([8, 2])],
           [list([3])],
           [list([-2, 4, 8, -2])],
           [list([5, 8])],
           [list([6])]], dtype=object)
    '''
    

    DIA - dia_matrix

    Diagonal Matrix 对角存储格式

    • 最适合对角矩阵的存储方式
    • dia_matrix通过两个数组确定: dataoffsets
    • data :对角线元素的值
    • offsets :第 ioffsets 是当前第 i 个对角线和主对角线的距离
    • data[k:] 存储了 offsets[k] 对应的对角线的全部元素

    img

    • offsets[0] = 0 时,表示该对角线即是主对角线,相应的值为 [1, 2, 3, 4, 5]
    • offsets[2] = 2 时,表示该对角线为主对角线向上偏移2个单位,相应的值为 [11, 12, 13, 14, 15]
    • 但该对角线上元素仅有三个 ,于是采用先出现的元素无效的原则
    • 即前两个元素对构造矩阵无效,故该对角线上的元素为 [13, 14, 15]

    实例化方法

    • dia_matrix(D):D代表密集矩阵;
    • dia_matrix(S):S代表其他类型稀疏矩阵
    • dia_matrix((M, N), [dtype]):构建一个shape为M*N的空矩阵,默认数据类型是d
    • dia_matrix((data, offsets)), [shape=(M, N)]))data[k,:] 存储着对角偏移量为 offset[k] 的对角值

    特殊属性

    • data:存储DIA对角值的数组
    • offsets:存储DIA对角偏移量的数组

    代码示例

    # 生成数据
    data = np.array([[1, 2, 3, 4], [5, 6, 0, 0], [0, 7, 8, 9]])
    offsets = np.array([0, -2, 1])
    
    # 创建矩阵
    dia = sparse.dia_matrix((data, offsets), shape=(4, 4))
    
    # 查看数据
    dia.data
    '''
    array([[[1 2 3 4]
            [5 6 0 0]
            [0 7 8 9]])
    '''
    
    # 转为array
    dia.toarray()
    '''
    array([[1 7 0 0]
           [0 2 8 0]
           [5 0 3 9]
           [0 6 0 4]])
    '''
    

    矩阵格式对比

    稀疏矩阵存取

    存储 - save_npz

    scipy.sparse.save_npz('sparse_matrix.npz', sparse_matrix)
    sparse_matrix = scipy.sparse.load_npz('sparse_matrix.npz')
    

    读取 - load_npz

    # 从npz文件中读取
    test_x = sparse.load_npz('./data/npz/test_x.npz')
    

    存储大小比较

    a = np.arange(100000).reshape(1000,100)
    a[10: 300] = 0
    b = sparse.csr_matrix(a)
    
    # 稀疏矩阵压缩存储到npz文件
    sparse.save_npz('b_compressed.npz', b, True)  # 文件大小:100KB
    
    # 稀疏矩阵不压缩存储到npz文件
    sparse.save_npz('b_uncompressed.npz', b, False)  # 文件大小:560KB
    
    # 存储到普通的npy文件
    np.save('a.npy', a)  # 文件大小:391KB
    
    # 存储到压缩的npz文件
    np.savez_compressed('a_compressed.npz', a=a)  # 文件大小:97KB• 1
    

    对于存储到npz文件中的CSR格式的稀疏矩阵,内容为:

    data.npy
    format.npy
    indices.npy
    indptr.npy
    shape.npy
    

    参考

    展开全文
  • scipy实现2. sklearn实现 python 实现层次聚类 关于层次聚类的原理,可以参考博客: https://blog.csdn.net/pentiumCM/article/details/105675576 本博客主要讲解如何简单直接使用 python 来实现层次聚类。 1. ...

    机器学习 — python(sklearn / scipy) 实现层次聚类,precomputed自定义距离矩阵

    关于层次聚类的原理,可以参考我的另一篇博客:层次聚类原理。本博客主要讲解如何简单直接使用 python 来实现层次聚类。

    本篇博客包含的内容:sklearn / scipy 两种方式实现层次聚类,以及在 sklearn 中通过 precomputed 参数实现自定义距离矩阵

    一. scipy实现

    (一) 函数说明

    主要是两个函数:linkage,fcluster

    1. linkage

    def linkage(y, method='single', metric='euclidean', optimal_ordering=False):
    

    函数功能解释:执行层次/聚集聚类。

    1. 参数(Parameters):

      • y:输入y可以是 1 维凝聚距离矩阵(距离向量)或 2 维观测矢量数组(坐标点的矩阵)。
      • method:method是指计算类间距离的方法,有如下几种方法:single,complete,average,weighted,centroid,ward
        • single:最近邻,把类与类间距离最近的作为类间距
          从簇 u 和 簇 v 中找到一对距离最近的点的距离作为簇 u 和簇 v 的距离:在这里插入图片描述
          在这里插入图片描述
        • complete:最远邻,把类与类间距离最远的作为类间距
          从簇 u 和 簇 v 中找到一对距离最远的点的距离作为簇 u 和簇 v 的距离:在这里插入图片描述在这里插入图片描述
        • average:平均距离,类与类间所有pairs距离的平均
          如簇 u 中有若干个点 i,簇 v 中有若干个 j 点,簇 u 和簇 v的距离为:在这里插入图片描述 在这里插入图片描述
        • weighted:在压缩距离矩阵上执行加权/ WPGMA链接
          如簇u由簇 s 和簇 t 组成,那么簇 u 到 簇 v 的距离为:在这里插入图片描述
          在这里插入图片描述
        • centroid:质心距离,把类与类中的质心间距离作为类间距在这里插入图片描述
        • ward:将要合并的群集的方差最小化。
    2. 返回值(Returns):

      • Z(ndarray):层次聚类编码为一个linkage矩阵。

        Z共有四列组成,第 1 字段与第 2 字段分别为聚类簇的编号,在初始距离前每个初始值被从0~n-1进行标识,每生成一个新的聚类簇就在此基础上增加一对新的聚类簇进行标识,第 3 个字段表示前两个聚类簇之间的距离,第 4 个字段表示新生成聚类簇所包含的元素的个数。

    3. 参考资料:https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.linkage.html#scipy.cluster.hierarchy.linkage


    2. fcluster

    def fcluster(Z, t, criterion='inconsistent', depth=2, R=None, monocrit=None):
    

    函数功能解释:从给定链接矩阵定义的层次聚类中形成平面聚类。

    1. 参数(Parameters):
      • Z:Z是linkage得到的矩阵,记录了层次聚类的层次信息;
      • t:是一个聚类的阈值
      • criterionstr:形成扁平簇的准则
        • inconsistent:
        • distance:以簇之间的距离作为划分准则
    2. 返回值(Returns):
      fcluster(ndarray):长度为n的数组。 T [i]是原始观测值 i 所属的平面簇数。
    3. 详细参考:https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.fcluster.html#scipy.cluster.hierarchy.fcluster

    (二) 示例含完整算法

    如对以下 5 个点进行凝聚层次聚类。

    xy
    点012
    点123
    点2-33
    点3-2-1
    点45-1

    在坐标轴上的位置:在这里插入图片描述层次聚类结果的聚类树为:在这里插入图片描述

    完整算法如下:

    #!/usr/bin/env python
    # encoding: utf-8
    '''
    @Author  : pentiumCM
    @Email   : 842679178@qq.com
    @Software: PyCharm
    @File    : sci_cluster.py
    @Time    : 2020/4/15 22:21
    @desc	 : scipy实现层次聚类
    '''
    
    import numpy as np
    from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
    
    from matplotlib import pyplot as plt
    
    data = np.array([[1, 2], [2, 3], [-3, 3], [-2, -1], [5, -1]])
    
    # 画点
    plt.scatter(x=data[:, 0:1], y=data[:, 1:2], marker='.', color='red')
    n = np.arange(data.shape[0])
    for i, txt in enumerate(n):
        plt.annotate(txt, (data[i:i + 1, 0:1], data[i:i + 1, 1:2]))
    plt.show()
    
    # 1. 层次聚类
    # linkage方法用于计算两个聚类簇s和t之间的距离d(s,t)
    # 层次聚类编码为一个linkage矩阵。
    Z = linkage(data, 'average')
    print("聚类过程:", Z)
    
    # 从给定链接矩阵定义的层次聚类中形成平面聚类。
    # distance:以距离为划分距离的准则
    f = fcluster(Z, 4, 'distance')
    print("平面聚类结果:", f)
    
    fig = plt.figure(figsize=(5, 3))
    # 将层级聚类结果以树状图表示出来
    dn = dendrogram(Z)
    plt.show()
    
    

    算法运行结果:

    聚类过程: [[0.         1.         1.41421356 2.        ]
     [2.         3.         4.12310563 2.        ]
     [5.         6.         4.75565014 4.        ]
     [4.         7.         6.48606798 5.        ]]
    平面聚类结果: [1 1 2 3 4]
    

    聚类的主要信息在 Z = linkage(data, ‘average’)中。
    Z共有四列组成,第 1 字段与第 2 字段分别为聚类簇的编号,在初始距离前每个初始值被从0~n-1进行标识,每生成一个新的聚类簇就在此基础上增加一对新的聚类簇进行标识,第 3 个字段表示前两个聚类簇之间的距离,第 4 个字段表示新生成聚类簇所包含的元素的个数。


    层次聚类可以一次性聚类出所有的情况,当生成出聚类树的结果时,可以通过在聚类树上画水平线(例如在上面算法中,水平线是以簇之间距离为准则)来选择聚成几类的结果。如用户需要聚成两类:在这里插入图片描述只需要从上往下画出如上图的水平线来判断聚成两类的结果,可以看出两类的结果,一类为 4,另一类为0、1、2、3。
    如果需要聚成3类,只需要将水平线往下平移即可知道聚成三类的结果。


    二、sklearn实现

    (一) 函数说明

    sklearn库下的层次聚类是在sklearn.cluster的 AgglomerativeClustering中:

    def __init__(self, n_clusters=2, affinity="euclidean",
                 memory=None,
                 connectivity=None, compute_full_tree='auto',
                 linkage='ward', distance_threshold=None):
    

    AgglomerativeClustering 类的构造函数的参数有 簇的个数 n_clusters,连接方法 linkage,连接度量选项 affinity 三个重要参数:

    • n_clusters:用户指定需要聚成几类。

    • linkage:选择计算簇与簇之间距离的策略,包含:ward,complete,average,single

      • ward:将要合并的群集的方差最小化。
      • complete:完全距离/最大距离,使用两组中所有观察值之间的最大距离。
      • single:最小距离,使用两组中所有观测值之间的最小距离。
      • average:平均距离,使用两组的每个观测值的距离平均值。
    • affinity:是一个簇间距离的计算方法。 可以是 “ euclidean(欧式距离)”,“ l1”,“ l2”,“manhattan(曼哈顿距离)”,“cosine(余弦)” 或 “precomputed(预先计算)”。

      • 如果链接为“ward”,则仅接受“欧式距离”。

      • 如果 “precomputed(预先计算)”,则需要距离矩阵作为拟合方法的输入。

        距离矩阵 的生成方法:假设用户有 n 个观测点,那么先依次构造这 n 个点两两间的距离列表,即长度为 n*(n-1)/2 的距离列表,然后通过 scipy.spatial.distance 的 dist 库的 squareform 函数就可以构造距离矩阵了。这种方式的好处是用户可以使用自己定义的方法计算任意两个观测点的距离,然后再进行聚类。后面也会给出基于自定义的距离矩阵进行的聚类算法。

    参考资料:源码文档


    (二) 完整算法

    #!/usr/bin/env python
    # encoding: utf-8
    '''
    @Author  : pentiumCM
    @Email   : 842679178@qq.com
    @Software: PyCharm
    @File    : sklearn_hierarchical_cluster.py
    @Time    : 2020/4/23 15:00
    @desc	 : sklearn的层次聚类
    '''
    
    import numpy as np
    from matplotlib import pyplot as plt
    
    from sklearn.cluster import AgglomerativeClustering
    
    data = np.array([[1, 2], [2, 3], [-3, 3], [-2, -1], [5, -1]])
    
    # 画点
    plt.scatter(x=data[:, 0:1], y=data[:, 1:2], marker='.', color='red')
    n = np.arange(data.shape[0])
    for i, txt in enumerate(n):
        plt.annotate(txt, (data[i:i + 1, 0:1], data[i:i + 1, 1:2]))
    plt.show()
    
    # 训练模型
    ac = AgglomerativeClustering(n_clusters=3, affinity='euclidean', linkage='average')
    clustering = ac.fit(data)
    
    print("每个数据所属的簇编号", clustering.labels_)
    print("每个簇的成员", clustering.children_)
    
    

    算法运行结果:

    每个数据所属的簇编号 [2 2 0 0 1]
    每个簇的成员 [[0 1]
     			[2 3]
     			[5 6]
     			[4 7]]
    

    借助 scipy 生成的聚类树,我们来理解一下聚类的结果:

    在这里插入图片描述
    clustering.labels_:表示每个数据所属于哪一个簇。
      [2 2 0 0 1]:表示数据0、1分为一簇,2、3分为一簇,4分为一簇。
    clustering.children_:表示每个簇中有哪些元素。
      [[0 1] [2 3] [5 6] [4 7]]:首先将数据初始化为簇 0 ~ n-1,然后簇0、1合并为簇5,簇2、3合并为簇6,簇5、6合并为簇7,最后簇4、7合并。


    补充基于预计算(precomputed)的距离矩阵的算法

    完整算法如下:

    #!/usr/bin/env python
    # encoding: utf-8
    '''
    @Author  : pentiumCM
    @Email   : 842679178@qq.com
    @Software: PyCharm
    @File    : sklearn_hierarchical_cluster.py
    @Time    : 2020/4/23 15:00
    @desc	 : sklearn的层次聚类
    '''
    
    import numpy as np
    from matplotlib import pyplot as plt
    
    from sklearn.cluster import AgglomerativeClustering
    
    from sklearn.metrics.pairwise import euclidean_distances
    import scipy.spatial.distance as dist
    from scipy.cluster.hierarchy import dendrogram, linkage
    
    data = np.array([[1, 2], [2, 3], [-3, 3], [-2, -1], [5, -1]])
    
    # 画点
    plt.scatter(x=data[:, 0:1], y=data[:, 1:2], marker='.', color='red')
    n = np.arange(data.shape[0])
    for i, txt in enumerate(n):
        plt.annotate(txt, (data[i:i + 1, 0:1], data[i:i + 1, 1:2]))
    plt.show()
    
    # 聚类方式一
    # 训练模型
    ac = AgglomerativeClustering(n_clusters=3, affinity='euclidean', linkage='average')
    clustering = ac.fit(data)
    
    print("每个数据所属的簇编号:", clustering.labels_)
    print("每个簇的成员:", clustering.children_)
    
    # 聚类的方式二
    # 自定义距离矩阵
    num = data.shape[0]
    dist_matrix = np.mat(np.zeros((num, num)))
    for i in range(num):
        for j in range(i, num):
            distence = euclidean_distances(data[i:i + 1], data[j:j + 1])
            dist_matrix[i:i + 1, j:j + 1] = distence
            dist_matrix[j:j + 1, i:i + 1] = dist_matrix[i:i + 1, j:j + 1]
    
    # 基于自定义的聚类矩阵进行聚类
    model = AgglomerativeClustering(n_clusters=3, affinity='precomputed', linkage='average')
    clustering2 = model.fit(dist_matrix)
    
    print("自定义距离矩阵聚类方式:")
    print("每个数据所属的簇编号:", clustering2.labels_)
    print("每个簇的成员:", clustering2.children_)
    
    # 调整距离矩阵的形状
    dist_matrix = dist.squareform(dist_matrix)
    
    # linkage方法用于计算两个聚类簇s和t之间的距离d(s,t)
    # 层次聚类编码为一个linkage矩阵。
    Z = linkage(dist_matrix, 'average')
    print("聚类过程:", Z)
    
    # 将层级聚类结果以树状图表示出来
    fig = plt.figure(figsize=(5, 3))
    dn = dendrogram(Z)
    plt.show()
    
    

    算法运行结果:

    每个数据所属的簇编号: [2 2 0 0 1]
    每个簇的成员: [[0 1]
    			  [2 3]
    			  [5 6]
    			  [4 7]]
    自定义距离矩阵聚类方式:
    每个数据所属的簇编号: [2 2 0 0 1]
    每个簇的成员: [[0 1]
    			  [2 3]
    			  [5 6]
    			  [4 7]]
    聚类过程: [[0.         1.         1.41421356 2.        ]
    		  [2.         3.         4.12310563 2.        ]
    		  [5.         6.         4.75565014 4.        ]
    		  [4.         7.         6.48606798 5.        ]]
    
    

    上面的算法包含了sklearn的两种聚类方式,方式二为预计算的方式:算法预先计算了 期初各个数据点之间的距离矩阵dist_matrix,然后在聚类时,affinity=‘precomputed’。


    对比之下,对于层次聚类的方便理解的方式,大家可以采用scipy的方式。


    参考资料

    展开全文
  • Scipy教程 - 距离计算库scipy.spatial.distance

    万次阅读 多人点赞 2015-09-29 23:37:20
    http://blog.csdn.net/pipisorry/article/details/48814183...距离计算矩阵距离计算函数矩阵参数每行代表一个观测值,计算结果就是每行之间的metric距离。Distance matrix computation from a collection of raw obser
  • pdist(X, levensthein) and for the levensthein then you can use the implementation of rosettacode as suggested by Tanu If you want a full squared matrix just use squareform on the result: Y = scipy....
  • 给定一个矩阵,计算距离矩阵是一个非常常见的需求,比如给定一个特征矩阵需要计算距离矩阵。自己写的话虽然简单每次写也往往很烦,而且自己写的代码效率过低了,使用scipy中的包的话无疑会好一点,具体来说,使用...
  • 1.引言 距离矩阵是一个包含一组点两两距离的矩阵(即 二维数组)。因此给定 个欧几里得空间中的点,其距离矩阵就是一个非负实数作为元素的 的对称矩阵。在机器学习中距离矩阵都计算非常常见(只要涉及距离计算,基本...
  • (1)Python之向量(Vector)距离矩阵计算

    万次阅读 多人点赞 2018-12-17 14:06:40
    矩阵自身(行)向量之间的距离矩阵计算2.1 第一种方法:简单使用两重循环2.2 第二种方法:矩阵內积双重循环2.3 第三种方法:避免循环内的点积运算2.4 第四种方法:避免循环2.5 第五种方法:利用`scipy`求距离矩阵...
  • 坐标快速转距离矩阵

    2020-12-04 10:26:13
    给定若干个点如何转换成距离矩阵,最简单粗暴的方法就是依次计算出各个点彼此间的距离然后填到矩阵中,参考练习题记录:求解距离矩阵,首先生成一百个二维坐标点,计算任意两个坐标点的距离。 但是我们可以利用...
  • scipy.spatial 距离计算模块

    千次阅读 2017-12-11 15:19:06
    scipy.spatial中最重要的模块应该就是距离计算模块distance了。 from scipy import spatial 距离计算 矩阵距离计算函数 矩阵参数每行代表一个观测值,计算结果就是每行之间的metric距离。Distance ...
  • 计算距离矩阵

    2021-06-28 17:30:16
    from scipy.spatial import distance Y = distance.pdist(m1, 'cosine') z=distance.squareform(Y) cosine 是参数,可以指定别的距离计算法方式
  • 十一.Sparse模块 ...块系数行矩阵:class scipy.sparse.bsr_matrix(<arg1>[,shape=None,dtype=None,copy=False,blocksize=None]) #参数说明: arg1:指定 shape: dtype: copy: blocksize:
  • 所以让我们创建你的矩阵(可惜你没有给出我可以复制粘贴的输入)In [114]: data=[4,1,2,2,1,1,4,3,2]In [115]: col=[0,1,1,2,2,3,4,4,4]In [116]: row=[2,0,4,0,3,5,0,2,3]In [117]: M=sparse.csr_matrix((data,(col,...
  • 【Python】求点集的距离矩阵 使用scipy.spatial的distance,具体代码如下: from scipy.spatial import distance p1=[(1,1),(2,2),(3,3)] p2=[(1,1),(2,2)] p1=np.array(p1,dtype=np.float64) p2=np.array(p2,...
  • Scipy中计算距离的模块是scipy.spatial.distance,最常用的方法是计算距离矩阵,换句话说,从存储在矩形数组中的观测向量集合中进行距离矩阵的计算。 一,两两距离 在n维空间中的观测值,计算两两之间的距离。距离值...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,178
精华内容 2,071
关键字:

scipy距离矩阵