降维-多维缩放

第1关：多维缩放

# -*- coding: utf-8 -*-
import numpy as np

def mds(data,d):
    '''
    input:data(ndarray):待降维数据
          d(int):降维后数据维数
    output:Z(ndarray):降维后的数据
    '''
    #********* Begin *********#
    #计算dist2,dist2i,dist2j,dist2ij
    n = data.shape[0]
    D = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            D[i, j] = np.sqrt(np.sum((data[i] - data[j])**2))
    dist2 = D ** 2
    dist2i = np.mean(dist2, axis=1, keepdims=True)
    dist2j = np.mean(dist2, axis=0, keepdims=True)
    dist2ij = np.mean(dist2)

    #计算B
    B = -0.5 * (dist2 - dist2i - dist2j + dist2ij)

    #矩阵分解得到特征值与特征向量
    eigvals, eigvecs = np.linalg.eigh(B)
    idx = np.argsort(eigvals)[::-1]
    eigvals = eigvals[idx]
    eigvecs = eigvecs[:, idx]

    #计算Z
    Z = eigvecs[:, :d] * np.sqrt(eigvals[:d])
    #********* End *********#
    return Z 

第2关：sklearn中的多维缩放

# -*- coding: utf-8 -*-
from sklearn.manifold import MDS

def mds(data,d):
    '''
    input:data(ndarray):待降维数据
          d(int):降维后数据维度
    output:Z(ndarray):降维后数据
    '''
    #********* Begin *********#
    mds_model = MDS(n_components=d)
    Z = mds_model.fit_transform(data)
    #********* End *********#
    return Z

降维-等度量映射

第1关：等度量映射

# -*- coding: utf-8 -*-
import numpy as np

def isomap(data, d, k, Max=10000):
    '''
    input:data(ndarray):待降维数据
          d(int):降维后数据维数
          k(int):最近的k个样本
          Max(int):表示无穷大
    output:Z(ndarray):降维后的数据
    '''
    #********* Begin *********#
    # 计算dist2, dist2i, dist2j, dist2ij
    m, n = data.shape
    dist = np.ones((m, m)) * Max
    disti = np.zeros(m)
    distj = np.zeros(m)
    B = np.zeros((m, m))
    
    for i in range(m):
        distance = np.power(np.tile(data[i], (m, 1)) - data, 2).sum(axis=1)
        index = np.argsort(distance)
        q = index[:k]
        for l in q:
            dist[i][l] = np.power(data[i] - data[l], 2).sum()
 
    for i in range(m):
        disti[i] = np.mean(dist[i, :])
        distj[i] = np.mean(dist[:, i])
        
    distij = np.mean(dist)
    
    # 计算B
    for i in range(m):
        for j in range(m):
            B[i, j] = -0.5 * (dist[i, j] - disti[i] - distj[j] + distij)
    
    # 矩阵分解得到特征值与特征向量
    lamda, V = np.linalg.eigh(B)
    
    # 计算Z
    index = np.argsort(-lamda)[:d]
    diag_lamda = np.sqrt(np.diag(-np.sort(-lamda)[:d]))
    V_selected = V[:, index]
    Z = V_selected.dot(diag_lamda)
    
    #********* End *********#
    return Z

第2关：sklearn中的等度量映射

# -*- coding: utf-8 -*-
from sklearn.manifold import Isomap

def isomap(data,d,k):
    '''
    input:data(ndarray):待降维数据
          d(int):降维后数据维度
          k(int):最近的k个样本
    output:Z(ndarray):降维后数据
    '''
    #********* Begin *********#
    isomap = Isomap(n_components=d, n_neighbors=k)
    Z = isomap.fit_transform(data)
    #********* End *********#
    return Z

降维-局部线性嵌入

第1关：局部线性嵌入

#encoding=utf8 
import numpy as np

def lle(data,d,k):
    '''
    input:data(ndarray):待降维数据,行数为样本个数，列数为特征数
          d(int):降维后数据维数
          k(int):最近的k个样本
    output:Z(ndarray):降维后的数据
    '''
        #********* Begin *********#
    n = data.shape[0]
    
    # 确定样本i的邻域
    D = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            D[i, j] = np.sqrt(np.sum((data[i] - data[j])**2))
    
    neighbors = np.zeros((n, k), dtype=int)
    for i in range(n):
        neighbors[i] = np.argsort(D[i])[1:k+1]
    
    # 求矩阵c及其逆，求w
    W = np.zeros((n, n))
    for i in range(n):
        Xi = data[neighbors[i]]
        xi = data[i]
        Z = Xi - xi
        C = Z @ Z.T
        
        # 正则化防止奇异
        reg = 0.001 * np.trace(C)
        C = C + reg * np.eye(k)
        
        w = np.linalg.solve(C, np.ones(k))
        w = w / np.sum(w)
        W[i, neighbors[i]] = w
    
    # 求得M并矩阵分解
    M = (np.eye(n) - W).T @ (np.eye(n) - W)
    eigvals, eigvecs = np.linalg.eigh(M)
    idx = np.argsort(eigvals)
    eigvals = eigvals[idx]
    eigvecs = eigvecs[:, idx]
    
    # 求Z（取第2小到第d+1小的特征值对应的特征向量）
    Z = eigvecs[:, 1:d+1]
    #********* End *********#
    return Z    

第2关：sklearn中的局部线性嵌入

# -*- coding: utf-8 -*-
from sklearn.manifold import LocallyLinearEmbedding

def lle(data,d,k):
    '''
    input:data(ndarray):待降维数据
          d(int):降维后数据维度
          k(int):邻域内样本数
    output:Z(ndarray):降维后数据
    '''
        #********* Begin *********#
    lle_model = LocallyLinearEmbedding(n_neighbors=k, n_components=d)
    Z = lle_model.fit_transform(data)
    #********* End *********#
    return Z

主成分分析PCA

第1关：维数灾难与降维

• 1、下列说法正确的是（BC）

  A、

  过拟合一定是维数灾难造成的

  B、

  降维能够缓解维数灾难的负面影响

  C、

  使用原始数据训练出的回归器已经过拟合，可试试降维来提升性能

  D、

  使用原始数据训练出的回归器已经欠拟合，可试试降维来提升性能

• 2、下列说法错误的是（C）

  A、

  降维能够减小训练的时间复杂度

  B、

  降维能够减小预测的时间复杂度

  C、

  维数灾难不会引起过拟合

  D、

  根据原始数据挖掘出新特征后，特征数量较多，可能会引发维数灾难

第2关：PCA算法流程

import numpy as np

def pca(data, k):
    '''
    对data进行PCA，并将结果返回
    :param data:数据集，类型为ndarray
    :param k:想要降成几维，类型为int
    :return: 降维后的数据，类型为ndarray
    '''

    #********* Begin *********#
     # 数据中心化
    mean = np.mean(data, axis=0)
    data_centered = data - mean
    
    # 计算协方差矩阵（使用样本协方差，除以m-1）
    cov_matrix = np.cov(data_centered, rowvar=False)
    
    # 特征值分解
    eig_vals, eig_vecs = np.linalg.eig(cov_matrix)
    
    # 对特征值降序排序，取前k个对应的特征向量
    idx = np.argsort(eig_vals)[::-1][:k]
    selected_vecs = eig_vecs[:, idx]   # 选取前k个特征向量
    
    # 投影到低维空间
    reduced_data = data_centered @ selected_vecs
    return reduced_data
    #********* End *********#

第3关：sklearn中的PCA

from sklearn.decomposition import PCA

def cancer_predict(train_sample, train_label, test_sample):
    '''
    使用PCA降维，并进行分类，最后将分类结果返回
    :param train_sample:训练样本, 类型为ndarray
    :param train_label:训练标签, 类型为ndarray
    :param test_sample:测试样本, 类型为ndarray
    :return: 分类结果
    '''

    #********* Begin *********#
    from sklearn.preprocessing import StandardScaler
    from sklearn.linear_model import LogisticRegression
    # 标准化数据
    scaler = StandardScaler()
    train_scaled = scaler.fit_transform(train_sample)
    test_scaled = scaler.transform(test_sample)
    
    # PCA降维，保留95%的方差
    pca = PCA(n_components=0.95)
    train_pca = pca.fit_transform(train_scaled)
    test_pca = pca.transform(test_scaled)
    
    # 使用逻辑回归进行分类
    clf = LogisticRegression(random_state=0, max_iter=1000)
    clf.fit(train_pca, train_label)
    pred = clf.predict(test_pca)
    return pred
    #********* End *********#

奇异值分解与主题模型

第1关：使用 gensim 构建 LDA 模型

from gensim import corpora, models
import jieba.posseg as jp, jieba
from basic import get_stopword_list

texts=[]
# 构建语料库
for i in range(5):
    s=input()
    texts.append(s)

flags = ('n', 'nr', 'ns', 'nt', 'eng', 'v', 'd')  # 词性
stopwords = get_stopword_list()
words_ls = []
for text in texts:
    words = [word.word for word in jp.cut(text) if word.flag in flags and word.word not in stopwords]
    words_ls.append(words)

# 去重，存到字典
dictionary = corpora.Dictionary(words_ls)
corpus = [dictionary.doc2bow(words) for words in words_ls]

# 任务:基于 gensim 的models构建一个lda模型，主题数为1个
# ********** Begin *********#
lda = models.LdaModel(corpus=corpus, id2word=dictionary, num_topics=1)



# ********** End **********#
for topic in lda.print_topics(num_words=1):
    print(topic[1].split('*')[1],end="")

第2关：LSA / LSI 算法与SVD典型应用场景

from gensim import corpora, models
import functools
from others import seg_to_list,load_data,word_filter,cmp
import math

class TopicModel(object):
    # 三个传入参数：处理后的数据集，关键词数量，具体模型（LSI、LDA），主题数量
    def __init__(self, doc_list, keyword_num, model='LSI', num_topics=4):
        # 使用gensim的接口，将文本转为向量化表示
        # 先构建词空间
        self.dictionary = corpora.Dictionary(doc_list)
        # 任务：使用BOW模型进行向量化，并保存到corpus变量中
        # ********** Begin *********#
        corpus = [self.dictionary.doc2bow(doc) for doc in doc_list]
              
        
        
        # ********** End **********#
        # 对每个词，根据tf-idf进行加权，得到加权后的向量表示
        self.tfidf_model = models.TfidfModel(corpus)
        self.corpus_tfidf = self.tfidf_model[corpus]
        self.keyword_num = keyword_num
        self.num_topics = num_topics
        # 选择加载的模型
        if model == 'LSI':
            self.model = self.train_lsi()
        else:
            self.model = self.train_lda()
        # 得到数据集的主题-词分布
        word_dic = self.word_dictionary(doc_list)
        self.wordtopic_dic = self.get_wordtopic(word_dic)
    def train_lsi(self):
        lsi = models.LsiModel(self.corpus_tfidf, id2word=self.dictionary, num_topics=self.num_topics)
        return lsi
    def train_lda(self):
        lda = models.LdaModel(self.corpus_tfidf, id2word=self.dictionary, num_topics=self.num_topics)
        return lda
    def get_wordtopic(self, word_dic):
        wordtopic_dic = {}
        for word in word_dic:
            single_list = [word]
            wordcorpus = self.tfidf_model[self.dictionary.doc2bow(single_list)]
            wordtopic = self.model[wordcorpus]
            wordtopic_dic[word] = wordtopic
        return wordtopic_dic
    # 计算词的分布和文档的分布的相似度，取相似度最高的keyword_num个词作为关键词
    def get_simword(self, word_list):
        sentcorpus = self.tfidf_model[self.dictionary.doc2bow(word_list)]
        senttopic = self.model[sentcorpus]
        # 余弦相似度计算
        def calsim(l1, l2):
            a, b, c = 0.0, 0.0, 0.0
            for t1, t2 in zip(l1, l2):
                x1 = t1[1]
                x2 = t2[1]
                a += x1 * x1
                b += x1 * x1
                c += x2 * x2
            sim = a / math.sqrt(b * c) if not (b * c) == 0.0 else 0.0
            return sim
        # 计算输入文本和每个词的主题分布相似度
        sim_dic = {}
        for k, v in self.wordtopic_dic.items():
            if k not in word_list:
                continue
            sim = calsim(v, senttopic)
            sim_dic[k] = sim
        for k, v in sorted(sim_dic.items(), key=functools.cmp_to_key(cmp), reverse=True)[:self.keyword_num]:
            print(k + "/ ", end='')
        print()
    # 词空间构建方法和向量化方法，在没有gensim接口时的一般处理方法
    def word_dictionary(self, doc_list):
        dictionary = []
        for doc in doc_list:
            dictionary.extend(doc)
        dictionary = list(set(dictionary))
        return dictionary
    def doc2bowvec(self, word_list):
        vec_list = [1 if word in word_list else 0 for word in self.dictionary]
        return vec_list
def topic_extract(word_list, model, pos=False, keyword_num=10):
    doc_list = load_data(pos)
    topic_model = TopicModel(doc_list, keyword_num, model=model)
    topic_model.get_simword(word_list)
if __name__ == '__main__':
    text = input()
    pos = True
    seg_list = seg_to_list(text, pos)
    filter_list = word_filter(seg_list, pos)
    topic_extract(filter_list, 'LSI', pos)

有监督学习-线性判别分析

第1关：线性判别分析 - 随机生成数的降维

#encoding=utf8 
import numpy as np
from numpy.linalg import inv
def lda(X, y):
    '''
    input:X(ndarray):待处理数据
          y(ndarray):待处理数据标签，标签分别为0和1
    output:X_new(ndarray):处理后的数据
    '''
    #********* Begin *********#
    # 划分出第一类样本与第二类样本
    X0 = X[y == 0]
    X1 = X[y == 1]

    # 获取第一类样本与第二类样本中心点
    u0 = np.mean(X0, axis=0)
    u1 = np.mean(X1, axis=0)

    # 计算第一类样本与第二类样本协方差矩阵（散度矩阵，无分母）
    S0 = (X0 - u0).T @ (X0 - u0)
    S1 = (X1 - u1).T @ (X1 - u1)

    # 计算类内散度矩阵
    Sw = S0 + S1

    # 计算w (使用伪逆防止奇异)
    w = np.linalg.pinv(Sw) @ (u0 - u1)

    # 计算新样本集（投影到一维）
    X_new = X @ w
    X_new = X_new.reshape(-1, 1)
    
    #********* End *********#
    return X_new

第2关：scikit-learn线性判别实践 - 随机生成数的降维

#encoding=utf8 
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis

def lda(x,y):
    '''
    input:x(ndarray):待处理数据
          y(ndarray):待处理数据标签
    output:x_new(ndarray):降维后数据
    '''
    #********* Begin *********#
    # 创建LDA对象，降到2维（对于3类数据，最多降到2维）
    lda = LinearDiscriminantAnalysis(n_components=2)
    # 训练模型
    lda.fit(x, y)
    # 降维
    x_new = lda.transform(x)
    #********* End *********#
    return x_new