lib5c.algorithms.knight_ruiz module

Knight-Ruiz algorithm.

Transcribed from the MATLAB source provided in Rao et al. 2014 by Dan Gillis.

lib5c.algorithms.knight_ruiz.balance_matrix(matrix, bias_vector, invert=False)

Balance a matrix given the appropriate multiplicative bias vector.

Parameters

• matrix (np.ndarray) –

• bias_vector (np.ndarray) –

• invert (Optional[bool]) – Pass True to invert the bias vector before balancing.

Returns

The balanced matrix.

Return type

np.ndarray

lib5c.algorithms.knight_ruiz.kr_balance(array, tol=1e-06, x0=None, delta=0.1, ddelta=3, fl=0, max_iter=3000)

Performs Knight-Ruiz matrix balancing algorithm on a 2D symmetric numpy array.

Note that this function does not check for symmetry of the array - this function may not converge if given non-symmetric matrix.

Note also that this function does not return balanced matrix - it returns the entries of the diagonal matrix that should be multiplied on either side of array to get balanced matrix.

Parameters

• array (np.ndarray) – Matrix to balance. Should be square and symmetric.

• tol (float) – Parameter related to tolerance

• x0 (Optional[np.ndarray]) – The initial guess to use for the bias vector. If not passed, a vector of all 1’s will be used.

• delta (float) – Parameter related to learning rate.

• ddelta (float) – Parameter related to learning rate.

• fl (int) – Adjusts the verbosity of command line output.

• max_iter (Optional[int]) – The maximum number of iterations. Pass None to set no limit.

Returns

The first element is the bias vector, the second is the residual.

Return type

Tuple[np.ndarray]

Examples

>>> import numpy as np
>>> X = np.reshape(range(16), (4, 4)).astype(float)
>>> counts = X + X.T
>>> counts
array([[ 0.,  5., 10., 15.],
       [ 5., 10., 15., 20.],
       [10., 15., 20., 25.],
       [15., 20., 25., 30.]])
>>> counts.sum(axis=1)
array([30., 50., 70., 90.])
>>> x, res = kr_balance(counts)
>>> balanced = x.T * counts * x
>>> balanced
array([[0.        , 0.26604444, 0.34729636, 0.3866592 ],
       [0.26604444, 0.2489703 , 0.24375574, 0.24122952],
       [0.34729636, 0.24375574, 0.21213368, 0.19681423],
       [0.3866592 , 0.24122952, 0.19681423, 0.17529705]])
>>> balanced.sum(axis=1)
array([1., 1., 1., 1.])
>>> for i in range(len(counts)):
...     for j in range(i+1):
...         if i % 2 == j % 2:
...             counts[i, j] = 0.0
...             counts[j, i] = 0.0
>>> counts
array([[ 0.,  5.,  0., 15.],
       [ 5.,  0., 15.,  0.],
       [ 0., 15.,  0., 25.],
       [15.,  0., 25.,  0.]])
>>> x, res = kr_balance(counts)
>>> balanced = x.T * counts * x
>>> balanced
array([[0.        , 0.42705098, 0.        , 0.57294902],
       [0.42705098, 0.        , 0.57294902, 0.        ],
       [0.        , 0.57294902, 0.        , 0.42705098],
       [0.57294902, 0.        , 0.42705098, 0.        ]])
>>> balanced.sum(axis=1)
array([1., 1., 1., 1.])

lib5c.algorithms.knight_ruiz.kr_balance_matrix(matrix, max_iter=3000, retain_scale=True, imputation_size=0)

Convenience function for applying KR balancing to a counts matrix.

Parameters

• matrix (np.ndarray) – The matrix to balance.

• max_iter (int) – The maximum number of iterations to try.

• retain_scale (bool) – Pass True to rescale the results to the scale of the original matrix using a ratio of geometric means.

• imputation_size (int) – Pass an int greater than 0 to replace NaN’s in the matrix with a local median approximation. Pass 0 to skip imputation.

Returns

The first array contains the balanced matrix. The second contains the bias vector. The third contains the residual.

Return type

Tuple[np.ndarray, np.ndarray, np.ndarray]

lib5c.algorithms.knight_ruiz.strip_zero_rows_columns_sym_mat(sym_mat)

Given symmetric 2D numpy array sym_mat, removes rows and columns that have no non-zero entries