Preface

In this paper, the gradient algorithm and the improved random gradient algorithm are compared, and their advantages and disadvantages are summarized, and sklearn.linear'u model.logistic regression is introduced in detail.

Two improved random gradient rising algorithm

The gradient rise algorithm needs to traverse the whole data set every time it updates the regression coefficient (optimal parameter). Let's take a look at the gradient rise algorithm we wrote earlier:

def gradAscent(dataMatIn, classLabels):
    dataMatrix = np.mat(dataMatIn)                                        #mat converted to numpy
    labelMat = np.mat(classLabels).transpose()                            #Convert to numpy's mat and transpose
    m, n = np.shape(dataMatrix)                                            #Returns the size of the dataMatrix. m is the number of rows and n is the number of columns.
    alpha = 0.01                                                        #The moving step, that is, the learning rate, controls the magnitude of the update.
    maxCycles = 500                                                        #Maximum number of iterations
    weights = np.ones((n,1))
    for k in range(maxCycles):
        h = sigmoid(dataMatrix * weights)                                #Vectorization formula of gradient rise
        error = labelMat - h
        weights = weights + alpha * dataMatrix.transpose() * error
    return weights.getA(),weights_array                                    #Convert matrix to array, return weight array

Suppose we use a dataset of 100 samples. So, dataMatrix is a 100 * 3 matrix. Every time h is calculated, the matrix multiplication of dataMatrix*weights needs to be calculated, with 100 * 3 times of multiplication and 100 * 2 times of addition. In the same way, when updating the weight of regression coefficient (optimal parameter), the whole data set is also needed, and matrix multiplication is needed. All in all, this method is feasible for processing about 100 datasets, but if there are billions of samples and thousands of features, the computational complexity of this method is too high. Therefore, we need to improve the algorithm. When we update the regression coefficient (optimal parameter), can we not use all samples? Only one sample point at a time to update the regression coefficient (optimal parameter)? This can effectively reduce the amount of computation, this method is called the random gradient rise algorithm.

1 random gradient rising algorithm

Let's look directly at the code:

# Random gradient rising algorithm
def stocGradAscent0(dataMatrix, classLabels):
    dataArr=np.array(dataMatrix)
    m, n = np.shape(dataArr)
    alpha = 0.01
    weights = np.ones(n)  # initialize to all ones
    for i in range(m):
        # h. Errors are all numerical values, and there is no matrix conversion process.
        h = sigmoid(sum(dataArr[i] * weights))
        error = classLabels[i] - h
        weights = weights + alpha * error * dataArr[i]
    return weights

Improvement of random gradient algorithm:

# Improvement of random gradient rising algorithm
def stocGradAscent1(dataMatrix, classLabels, numIter=150):
    dataArr=np.array(dataMatrix)
    m, n = np.shape(dataArr)
    weights = np.ones(n)  #Parameter initialization
    for j in range(numIter):
        dataIndex = list(range(m))
        for i in range(m):
            alpha = 4 / (1.0 + j + i) + 0.0001  #Decrease the size of alpha by 1/(j+i) at a time.
            randIndex = int(np.random.uniform(0, len(dataIndex)))  # Random sampling to change the sampling sample and reduce the periodic fluctuation
            h = sigmoid(sum(dataArr[randIndex] * weights))      # Select a randomly selected sample and calculate h
            error = classLabels[randIndex] - h                  # calculation error
            weights = weights + alpha * error * dataArr[randIndex] # Update regression coefficient
            del (dataIndex[randIndex])                             # Delete used samples
    return weights

The first improvement of this algorithm is that alpha will adjust every iteration, and although alpha will decrease with the number of iterations, it will never decrease to 0, because there is still a constant term. The reason why this has to be done is to ensure that the new data still has some impact after many iterations. If the problem that needs to be dealt with is dynamic, the above constant term can be appropriately increased to ensure that the new value gets a larger regression coefficient. It is also worth noting that in the function of decreasing alpha, alpha is reduced by 1/(j+i) at a time, where j is the number of iterations and i is the subscript of the sample point. The second improvement is to use only one sample point when updating the regression coefficient (optimal parameter), and the selected sample point is random, and the used sample point is not used in each iteration. This method can effectively reduce the amount of calculation and ensure the regression effect.

Write the following code to see the classification effect of the improved random gradient rise algorithm:
 

# -*- coding: UTF-8 -*-
import matplotlib.pyplot as plt
import numpy as np

"""
//Function Description: load data
Parameters:
    //nothing
Returns:
    dataMat - Data list
    labelMat - Tag list
Author:
    yangshaojun
Modify:
    2020-02-01
"""


# The first feature is usually w0 when the loading data feature changes to 3D
def loadDataSet():
    dataMat = []  # This list stores features
    labelMat = []  # Label this list
    fr = open('testSet.txt')  # Open file
    for line in fr.readlines():  # Read by line
        lineArr = line.strip().split('\t')  # Go to enter and put it in the list
        dataMat.append([1.0, float(lineArr[0]), float(lineArr[1])])  # Each sample feature is stored as a list
        labelMat.append(int(lineArr[2]))  # Add to label list
    fr.close()  # Close file
    return dataMat, labelMat  # Return


"""
//Function Description: drawing datasets
Parameters:
    //nothing
Returns:
    //nothing
Author:
    yangshaojun
Modify:
    2020-02-01
"""
def plotDataSet():
    dataMat, labelMat = loadDataSet()
    dataArr = np.array(dataMat)  # Array array converted to numpy
    n = np.shape(dataArr)[0]  # Number of data samples
    xcode1 = []; ycode1 = []  #Positive samples
    xcode2 = []; ycode2 = []  #Negative sample
    for i in range(n):        #Classify by dataset label
        if int(labelMat[i]) == 1:
            xcode1.append(dataArr[i, 1]); ycode1.append(dataArr[i, 2]) #1 is a positive sample
        else:
            xcode2.append(dataArr[i, 1]); ycode2.append(dataArr[i, 2]) #0 is a negative sample
    fig = plt.figure()
    ax = fig.add_subplot(111) #Add subplot
    ax.scatter(xcode1, ycode1, s=20, c='red', marker='s', alpha=0.5) #Draw positive sample
    ax.scatter(xcode2, ycode2, s=20, c='green', alpha=0.5) #Draw negative sample
    plt.title('DataSet') #Drawing title
    plt.xlabel('x')  #Drawing label
    plt.ylabel('y')
    plt.show()  #display

"""
//Function Description: sigmoid function
Parameters:
    inX - data
Returns:
    sigmoid function
Author:
    yangshaojun     
"""
def sigmoid(inX):
    return 1.0 / (1 + np.exp(-inX))

"""
//Function Description: gradient rise algorithm

Parameters:
    dataMatIn - data set
    classLabels - Data labels
Returns:
    weights.getA() - Weight array obtained(Optimal parameters)
    [[ 4.12414349]
    [ 0.48007329]
    [-0.6168482 ]]
Author:
    yangshaojun
Modify:
    2020-02-01
"""
def gradAscent(dataMatIn, classLabels):
    dataMatrix = np.mat(dataMatIn)  # List to numpy mat 100 row 3 column
    labelMat = np.mat(classLabels).transpose() #Convert to numpy's mat and transpose 100 rows and 1 column
    m, n = np.shape(dataMatrix)  # Returns the size of the dataMatrix. m is the number of rows and n is the number of columns.
    alpha = 0.001  #The moving step, that is, the learning rate, controls the magnitude of the update.
    maxCycles = 500  # Maximum number of iterations
    weights = np.ones((n, 1))  # Create a matrix element of 3 rows and 1 column as 1
    for k in range(maxCycles):
        h = sigmoid(dataMatrix * weights)  #Vectorization formula of gradient rise
        error = (labelMat - h)
        weights = weights + alpha * dataMatrix.transpose() * error
    return weights.getA()  # Convert matrix to array, return weight array

"""
//Function Description: drawing datasets

Parameters:
    weights - Weight parameter array
Returns:
    //nothing
Author:
    yangshaojun
Modify:
    2020-02-01
"""

def plotBestFit(weights):
    dataMat, labelMat = loadDataSet()
    dataArr = np.array(dataMat)  #Array array converted to numpy
    n = np.shape(dataArr)[0]  # Number of returned samples
    xcode1 = []; ycode1 = []  #Positive samples
    xcode2 = []; ycode2 = []  #Negative sample
    for i in range(n):        #Classify by dataset label
        if int(labelMat[i]) == 1:
            xcode1.append(dataArr[i, 1]);  ycode1.append(dataArr[i, 2]) #1 is a positive sample
        else:
            xcode2.append(dataArr[i, 1]);  ycode2.append(dataArr[i, 2]) #0 is a negative sample
    fig = plt.figure()
    ax = fig.add_subplot(111)                                           #Add subplot
    ax.scatter(xcode1, ycode1, s=30, c='red', marker='s')               #Draw positive sample
    ax.scatter(xcode2, ycode2, s=30, c='green')                         #Draw negative sample
    x = np.arange(-3.0, 3.0, 0.1)
    y = (-weights[0] - weights[1] * x) / weights[2]  # The value of y here is x2
    ax.plot(x, y)
    plt.xlabel('X1');
    plt.ylabel('X2');
    plt.show()


# Random gradient rising algorithm
def stocGradAscent0(dataMatrix, classLabels):
    dataArr=np.array(dataMatrix)
    m, n = np.shape(dataArr)
    alpha = 0.01
    weights = np.ones(n)  # initialize to all ones
    for i in range(m):
        # h. Errors are all numerical values, and there is no matrix conversion process.
        h = sigmoid(sum(dataArr[i] * weights))
        error = classLabels[i] - h
        weights = weights + alpha * error * dataArr[i]
    return weights


# Improvement of random gradient rising algorithm
def stocGradAscent1(dataMatrix, classLabels, numIter=150):
    dataArr=np.array(dataMatrix)
    m, n = np.shape(dataArr)
    weights = np.ones(n)  #Parameter initialization
    for j in range(numIter):
        dataIndex = list(range(m))
        for i in range(m):
            alpha = 4 / (1.0 + j + i) + 0.0001  #Decrease the size of alpha by 1/(j+i) at a time.
            randIndex = int(np.random.uniform(0, len(dataIndex)))  # Random sampling to change the sampling sample and reduce the periodic fluctuation
            h = sigmoid(sum(dataArr[randIndex] * weights))      # Select a randomly selected sample and calculate h
            error = classLabels[randIndex] - h                  # calculation error
            weights = weights + alpha * error * dataArr[randIndex] # Update regression coefficient
            del (dataIndex[randIndex])                             # Delete used samples
    return weights



if __name__ == '__main__':
    dataArr, labelMat = loadDataSet()
    weights = stocGradAscent1(dataArr, labelMat)
    plotBestFit(weights)

Code run result:

The relationship between the regression coefficient and the number of iterations

It can be seen that the classification effect is also good. However, from this classification result, we can not easily see the relationship between the number of iterations and the regression coefficient, nor can we directly see the convergence of each regression method. Therefore, we write a program to draw the relationship curve between regression coefficient and the number of iterations:

# -*- coding:UTF-8 -*-
from matplotlib.font_manager import FontProperties
import matplotlib.pyplot as plt
import numpy as np
import random


"""
//Function Description: load data

Parameters:
    //nothing
Returns:
    dataMat - Data list
    labelMat - Tag list

"""
def loadDataSet():
    dataMat = []                                                        #Create data list
    labelMat = []                                                        #Create label list
    fr = open('testSet.txt')                                            #Open file   
    for line in fr.readlines():                                            #Read by line
        lineArr = line.strip().split()                                    #Go to enter and put it in the list
        dataMat.append([1.0, float(lineArr[0]), float(lineArr[1])])        #Add data
        labelMat.append(int(lineArr[2]))                                #Add tags
    fr.close()                                                            #Close file
    return dataMat, labelMat                                            #Return

"""
//Function Description: sigmoid function

Parameters:
    inX - data
Returns:
    sigmoid function

"""
def sigmoid(inX):
    return 1.0 / (1 + np.exp(-inX))

"""
//Function Description: gradient rise algorithm

Parameters:
    dataMatIn - data set
    classLabels - Data labels
Returns:
    weights.getA() - Weight array obtained(Optimal parameters)
    weights_array - Regression coefficient per update

"""
def gradAscent(dataMatIn, classLabels):
    dataMatrix = np.mat(dataMatIn)                                        #mat converted to numpy
    labelMat = np.mat(classLabels).transpose()                            #Convert to numpy's mat and transpose
    m, n = np.shape(dataMatrix)                                            #Returns the size of the dataMatrix. m is the number of rows and n is the number of columns.
    alpha = 0.01                                                        #The moving step, that is, the learning rate, controls the magnitude of the update.
    maxCycles = 500                                                        #Maximum number of iterations
    weights = np.ones((n,1))
    weights_array = np.array([])
    for k in range(maxCycles):
        h = sigmoid(dataMatrix * weights)                                #Vectorization formula of gradient rise
        error = labelMat - h
        weights = weights + alpha * dataMatrix.transpose() * error
        weights_array = np.append(weights_array,weights)
    weights_array = weights_array.reshape(maxCycles,n)
    return weights.getA(),weights_array                                    #Converts a matrix to an array and returns



"""
//Function Description: improved random gradient rising algorithm

Parameters:
    dataMatrix - Data array
    classLabels - Data labels
    numIter - Iteration times
Returns:
    weights - Obtained regression coefficient array(Optimal parameters)
    weights_array - Regression coefficient per update

"""
def stocGradAscent1(dataMatrix, classLabels, numIter=150):
    m,n = np.shape(dataMatrix)                                                #Returns the size of the dataMatrix. m is the number of rows and n is the number of columns.
    weights = np.ones(n)                                                       #Parameter initialization
    weights_array = np.array([])                                            #Store regression coefficients for each update
    for j in range(numIter):                                           
        dataIndex = list(range(m))
        for i in range(m):           
            alpha = 4/(1.0+j+i)+0.01                                            #Decrease the size of alpha by 1/(j+i) at a time.
            randIndex = int(random.uniform(0,len(dataIndex)))                #Randomly selected samples
            h = sigmoid(sum(dataMatrix[randIndex]*weights))                    #Select a randomly selected sample and calculate h
            error = classLabels[randIndex] - h                                 #calculation error
            weights = weights + alpha * error * dataMatrix[randIndex]       #Update regression coefficient
            weights_array = np.append(weights_array,weights,axis=0)         #Add regression coefficient to array
            del(dataIndex[randIndex])                                         #Delete used samples
    weights_array = weights_array.reshape(numIter*m,n)                         #Changing dimensions
    return weights,weights_array                                             #Return

"""
//Function Description: draw the relationship between regression coefficient and iteration times

Parameters:
    weights_array1 - Regression coefficient array 1
    weights_array2 - Regression coefficient array 2
Returns:
    //nothing
"""
def plotWeights(weights_array1,weights_array2):
    #Format Chinese characters
    font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)
    #Divide the fig canvas into 1 row and 1 column without sharing the x-axis and y-axis. The size of the fig canvas is (13,8)
    #When nrow = 3 and nclos = 2, it means that the fig canvas is divided into six regions, and axs[0][0] means the first row and the first column
    fig, axs = plt.subplots(nrows=3, ncols=2,sharex=False, sharey=False, figsize=(20,10))
    x1 = np.arange(0, len(weights_array1), 1)
    #Draw the relationship between w0 and the number of iterations
    axs[0][0].plot(x1,weights_array1[:,0])
    axs0_title_text = axs[0][0].set_title(u'Gradient rise algorithm: relationship between regression coefficient and iteration times',FontProperties=font)
    axs0_ylabel_text = axs[0][0].set_ylabel(u'W0',FontProperties=font)
    plt.setp(axs0_title_text, size=20, weight='bold', color='black') 
    plt.setp(axs0_ylabel_text, size=20, weight='bold', color='black')
    #Draw the relationship between w1 and the number of iterations
    axs[1][0].plot(x1,weights_array1[:,1])
    axs1_ylabel_text = axs[1][0].set_ylabel(u'W1',FontProperties=font)
    plt.setp(axs1_ylabel_text, size=20, weight='bold', color='black')
    #Drawing the relationship between w2 and the number of iterations
    axs[2][0].plot(x1,weights_array1[:,2])
    axs2_xlabel_text = axs[2][0].set_xlabel(u'Iteration times',FontProperties=font)
    axs2_ylabel_text = axs[2][0].set_ylabel(u'W1',FontProperties=font)
    plt.setp(axs2_xlabel_text, size=20, weight='bold', color='black') 
    plt.setp(axs2_ylabel_text, size=20, weight='bold', color='black')


    x2 = np.arange(0, len(weights_array2), 1)
    #Draw the relationship between w0 and the number of iterations
    axs[0][1].plot(x2,weights_array2[:,0])
    axs0_title_text = axs[0][1].set_title(u'Improved random gradient rising algorithm: the relationship between regression coefficient and iteration number',FontProperties=font)
    axs0_ylabel_text = axs[0][1].set_ylabel(u'W0',FontProperties=font)
    plt.setp(axs0_title_text, size=20, weight='bold', color='black') 
    plt.setp(axs0_ylabel_text, size=20, weight='bold', color='black')
    #Draw the relationship between w1 and the number of iterations
    axs[1][1].plot(x2,weights_array2[:,1])
    axs1_ylabel_text = axs[1][1].set_ylabel(u'W1',FontProperties=font)
    plt.setp(axs1_ylabel_text, size=20, weight='bold', color='black')
    #Drawing the relationship between w2 and the number of iterations
    axs[2][1].plot(x2,weights_array2[:,2])
    axs2_xlabel_text = axs[2][1].set_xlabel(u'Iteration times',FontProperties=font)
    axs2_ylabel_text = axs[2][1].set_ylabel(u'W1',FontProperties=font)
    plt.setp(axs2_xlabel_text, size=20, weight='bold', color='black') 
    plt.setp(axs2_ylabel_text, size=20, weight='bold', color='black')

    plt.show()       

if __name__ == '__main__':
    dataMat, labelMat = loadDataSet()           
    weights1,weights_array1 = stocGradAscent1(np.array(dataMat), labelMat)

    weights2,weights_array2 = gradAscent(dataMat, labelMat)
    plotWeights(weights_array1, weights_array2)

Because of the improved random gradient rising algorithm and random selection of sample points, the results of each run are different. But the general trend is the same. The convergence of our improved algorithm is better. Why do you say that? Let's analyze. We have 100 sample points in total, and the number of iterations of the improved algorithm is 150. The reason why the above figure shows 15000 iterations is that the regression coefficient is updated with one sample. Therefore, 150 iterations are equivalent to updating the regression coefficient 150 * 100 = 15000 times. In short, 150 iterations and 15000 regression parameters were updated. From the regression effect of the improved random gradient rise algorithm on the left side of the figure above, it can be seen that, in fact, when updating 2000 regression coefficients, it has converged. It is equivalent to traversing the whole dataset 20 times, the regression coefficient has converged. Training completed.

Let's take a look at the regression effect of the gradient rise algorithm on the right side of the figure above. Every time the gradient rise algorithm updates the regression coefficient, it needs to traverse the entire data set. It can be seen from the figure that the regression coefficient converges only when the number of iterations is more than 300. To make a whole, it converges when it traverses the whole dataset 300 times.

There is no harm without comparison. The improved random gradient algorithm starts to converge at the 20th time of traversing the dataset. But the gradient rise algorithm starts to converge at the 300th time of traversing the dataset. Imagine, with a lot of data, who is better?