2020年認證杯SPSSPRO杯數(shù)學建模

D題 讓電腦桌面飛起來

原題再現(xiàn)：

??對于一些必須每天使用電腦工作的白領來說，電腦桌面有著非常特殊的意義，通常一些頻繁使用或者比較重要的圖標會一直保留在桌面上，但是隨著時間的推移，桌面上的圖標會越來越多，有的時候想找到一個馬上要用的圖標是非常困難的，就比如下圖所示的桌面。各種各樣的圖標會讓你眼花繚亂，甚至有的時候反復找好幾遍都找不到你想要的圖標。其實只要把圖標進行有效的分類就可以解決這個問題，但是手工分類往往非常浪費時間，有的時候使用者也會陷入分類決定困難，不知該如何選擇。

??第一階段問題： 請你的團隊建立合理的數(shù)學模型，設計一種快速、有效地桌面圖標分類的算法，使得能夠根據(jù)圖標的名字進行自動分類，讓電腦桌面真正飛起來！這里需要注意的是，應用程序的圖標文件不能通過擴展名來區(qū)分其功能，只能通過在已有的數(shù)據(jù)庫或者互聯(lián)網(wǎng)上查詢文件名來判斷其功能。當然也可以通過機器學習的方式來學習人的分類經驗來形成一個分類模式。

整體求解過程概述(摘要)

??隨著電腦辦公的普及,對于桌面圖標的分類整理已成為讓很多電腦使用者極為頭疼的一件事，無論是專業(yè)的計算機開發(fā)者還是日常辦公人員，進行有效的桌面圖標整理工作，對于辦公效率提升其價值是不言而喻的，對于桌面圖標的有效分類以及桌面區(qū)域的劃分是解決該問題的有效途徑。
??針對圖標分類而言，我們獲取桌面圖標有關的 logo 圖像、描述文本、以及近期訪問量等三大特征。對于圖像特征利用 CNN 進行圖像特征提取匹配 logo 相似程度，根據(jù)圖標名稱尋找對應詳細的文本介紹借助自然語言處理中的 LDA 主題提取算法，通過計算圖標之間有關用途、來源等文本主題進行文本聚類，形成以主題為依據(jù)的圖標存放單元。針對桌面圖標點擊量進行排序單獨劃分訪問區(qū)域，根據(jù)圖標 logo 特征提取后的結果結合圖標的點擊率調整圖標的透明度和大小。最后得到五大主題圖標區(qū)域與兩塊文件分類區(qū)域,在桌面上添加圖標搜索欄，以完成對于文檔類型圖標的快速查找。
??最后利用 ROC 曲線通過新增圖標數(shù)量判別分類器準確度為 87.8%,通過實際測試得到該模型對于桌面圖標查找速度提升為 65%。

問題分析：

??（一）問題一的分析
??對于桌面圖標而言，人們往往憑借記憶和直觀視覺完成對于所需圖標范圍的定位與查找，這往往耗費使用者大量時間。因此查找桌面圖標時間的長短是衡量桌面圖標分類效果的重要標準，與此同時優(yōu)化圖標對于用戶的視覺舒適度。首先對于桌面圖標需要合理設置若干個基本存放單元[1],將桌面區(qū)域進行劃分,縮小用戶對于所需圖標的查找范圍，對于新產生的圖標可通過分類器判決進入對應的基本存放單元。
??桌面圖標包括三個維度的信息:1、所屬文件的類型與自然文本 2、圖標圖像信息 3、近期桌面圖標瀏覽量。首先，利用 CNN 對于圖像論文進行特性提取，在輸出層外接 LGAM快速訓練模型，判決圖標之間的相近程度。接著通過圖標的名稱向 Web 服務器發(fā)出請求查找對應名稱內容的相應數(shù)據(jù)庫，根據(jù) LDA 主題模型進行主題聚類[2]，將同一類型產品進行規(guī)律，最終根據(jù)用戶的使用頻率與圖標顏色近似程度來改變的圖標的透明度，最后留出一塊基本存放單元體現(xiàn)桌面圖標訪問狀況。通過桌面圖標的訪問評論調整圖標的大小，并且對于使用頻率低于一周一次的圖標向用戶申請刪除命令。于此同時，針對大量同類型圖標文件例如 Excel 與 Word 報表，在桌面增添搜索區(qū)域增加對于相近文件的區(qū)分度。

模型假設：

??1.假設用戶對于桌面圖標重命名合理(符合圖標內容屬性)；
??2.假設用戶圖標類型較為常見，不存在大量圖標名稱極為近似
??3.假設圖標的透明度與大小能進行調整
??4.假設圖標名稱與所關聯(lián)的文本內容是一致的
??5.假設申請刪除某桌面圖標的標準為訪問周期小于一周

論文縮略圖：

全部論文請見下方“ 只會建模 QQ名片” 點擊QQ名片即可

部分程序代碼：(代碼和文檔not free)

import logging
import logging.config
import ConfigParser
import numpy as np
import random
import codecs
import os
from collections import OrderedDict
#獲取當前路徑
path = os.getcwd()
#導入日志配置文件
logging.config.fileConfig("logging.conf")
#創(chuàng)建日志對象
logger = logging.getLogger()
# loggerInfo = logging.getLogger("TimeInfoLogger")
# Consolelogger = logging.getLogger("ConsoleLogger")
#導入配置文件
conf = ConfigParser.ConfigParser()
conf.read("setting.conf")
#文件路徑
trainfile = os.path.join(path,os.path.normpath(conf.get("filepath", "trainfile")))
wordidmapfile = os.path.join(path,os.path.normpath(conf.get("filepath","wordidmapfile")))
thetafile = os.path.join(path,os.path.normpath(conf.get("filepath","thetafile")))
phifile = os.path.join(path,os.path.normpath(conf.get("filepath","phifile")))
paramfile = os.path.join(path,os.path.normpath(conf.get("filepath","paramfile")))
topNfile = os.path.join(path,os.path.normpath(conf.get("filepath","topNfile")))
tassginfile = os.path.join(path,os.path.normpath(conf.get("filepath","tassginfile")))
#模型初始參數(shù)
K = int(conf.get("model_args","K"))
alpha = float(conf.get("model_args","alpha"))
beta = float(conf.get("model_args","beta"))
iter_times = int(conf.get("model_args","iter_times"))
top_words_num = int(conf.get("model_args","top_words_num"))
class Document(object):
def __init__(self):
self.words = []
self.length = 0
#把整個文檔及真的單詞構成 vocabulary（不允許重復）
class DataPreProcessing(object):
def __init__(self):
self.docs_count = 0
self.words_count = 0
#保存每個文檔 d 的信息(單詞序列，以及 length)
self.docs = []
#建立 vocabulary 表，照片文檔的單詞
self.word2id = OrderedDict()
def cachewordidmap(self):
with codecs.open(wordidmapfile, 'w','utf-8') as f:
for word,id in self.word2id.items():
f.write(word +"\t"+str(id)+"\n")
class LDAModel(object):
def __init__(self,dpre):
self.dpre = dpre #獲取預處理參數(shù)
#
#模型參數(shù)
#聚類個數(shù) K，迭代次數(shù) iter_times,每個類特征詞個數(shù) top_words_num,超參數(shù)α（alpha） β(beta)
#
self.K = K
self.beta = beta
self.alpha = alpha
self.iter_times = iter_times
self.top_words_num = top_words_num
#
#文件變量
#分好詞的文件 trainfile
#詞對應 id 文件 wordidmapfile
#文章-主題分布文件 thetafile
#詞-主題分布文件 phifile
#每個主題 topN 詞文件 topNfile
#最后分派結果文件 tassginfile
#模型訓練選擇的參數(shù)文件 paramfile
#
self.wordidmapfile = wordidmapfile
self.trainfile = trainfile
self.thetafile = thetafile
self.phifile = phifile
self.topNfile = topNfile
self.tassginfile = tassginfile
self.paramfile = paramfile
# p,概率向量 double 類型，存儲采樣的臨時變量
# nw,詞 word 在主題 topic 上的分布
# nwsum,每各 topic 的詞的總數(shù)
# nd,每個 doc 中各個 topic 的詞的總數(shù)
# ndsum,每各 doc 中詞的總數(shù)
self.p = np.zeros(self.K)
# nw,詞 word 在主題 topic 上的分布
self.nw = np.zeros((self.dpre.words_count,self.K),dtype="int")
# nwsum,每各 topic 的詞的總數(shù)
self.nwsum = np.zeros(self.K,dtype="int")
# nd,每個 doc 中各個 topic 的詞的總數(shù)
self.nd = np.zeros((self.dpre.docs_count,self.K),dtype="int")
# ndsum,每各 doc 中詞的總數(shù)
self.ndsum = np.zeros(dpre.docs_count,dtype="int")
self.Z = np.array([ [0 for y in xrange(dpre.docs[x].length)] for x in xrange(dpre.docs_count)])
# M*doc.size()，文檔中詞的主題分布
#隨機先分配類型，為每個文檔中的各個單詞分配主題
for x in xrange(len(self.Z)):
self.ndsum[x] = self.dpre.docs[x].length
for y in xrange(self.dpre.docs[x].length):
topic = random.randint(0,self.K-1)#隨機取一個主題
self.Z[x][y] = topic#文檔中詞的主題分布
self.nw[self.dpre.docs[x].words[y]][topic] += 1
self.nd[x][topic] += 1
self.nwsum[topic] += 1
self.theta = np.array([ [0.0 for y in xrange(self.K)] for x in xrange(self.dpre.docs_count) ])
self.phi = np.array([ [ 0.0 for y in xrange(self.dpre.words_count) ] for x in xrange(self.K)])
def sampling(self,i,j):
#換主題
topic = self.Z[i][j]
#只是單詞的編號，都是從 0 開始 word 就是等于 j
word = self.dpre.docs[i].words[j]
#if word==j:
# print 'true'
self.nw[word][topic] -= 1
self.nd[i][topic] -= 1
self.nwsum[topic] -= 1
self.ndsum[i] -= 1
Vbeta = self.dpre.words_count * self.beta
Kalpha = self.K * self.alpha
self.p = (self.nw[word] + self.beta)/(self.nwsum + Vbeta) * \
(self.nd[i] + self.alpha) / (self.ndsum[i] + Kalpha)
#隨機更新主題的嗎
# for k in xrange(1,self.K):
# self.p[k] += self.p[k-1]
# u = random.uniform(0,self.p[self.K-1])
# for topic in xrange(self.K):
# if self.p[topic]>u:
# break
#按這個更新主題更好理解，這個效果還不錯
p = np.squeeze(np.asarray(self.p/np.sum(self.p)))
topic = np.argmax(np.random.multinomial(1, p))
self.nw[word][topic] +=1
self.nwsum[topic] +=1
self.nd[i][topic] +=1
self.ndsum[i] +=1
return topic
def est(self):
# Consolelogger.info(u"迭代次數(shù)為%s 次" % self.iter_times)
for x in xrange(self.iter_times):
for i in xrange(self.dpre.docs_count):
for j in xrange(self.dpre.docs[i].length):
topic = self.sampling(i,j)
self.Z[i][j] = topic
logger.info(u"迭代完成。")
logger.debug(u"計算文章-主題分布")
self._theta()
logger.debug(u"計算詞-主題分布")
self._phi()
logger.debug(u"保存模型")
self.save()
def _theta(self):
for i in xrange(self.dpre.docs_count):#遍歷文檔的個數(shù)詞
self.theta[i] = (self.nd[i]+self.alpha)/(self.ndsum[i]+self.K * self.alpha)
def _phi(self):
for i in xrange(self.K):
self.phi[i] = (self.nw.T[i] + self.beta)/(self.nwsum[i]+self.dpre.words_count * self.beta)
def save(self):
# 保存 theta 文章-主題分布
logger.info(u"文章-主題分布已保存到%s" % self.thetafile)
with codecs.open(self.thetafile,'w') as f:
for x in xrange(self.dpre.docs_count): for y in xrange(self.K):
f.write(str(self.theta[x][y]) + '\t')
f.write('\n')
# 保存 phi 詞-主題分布
logger.info(u"詞-主題分布已保存到%s" % self.phifile)
with codecs.open(self.phifile,'w') as f:
for x in xrange(self.K):
for y in xrange(self.dpre.words_count):
f.write(str(self.phi[x][y]) + '\t')
f.write('\n')
# 保存參數(shù)設置
logger.info(u"參數(shù)設置已保存到%s" % self.paramfile)
with codecs.open(self.paramfile,'w','utf-8') as f:
f.write('K=' + str(self.K) + '\n')
f.write('alpha=' + str(self.alpha) + '\n')
f.write('beta=' + str(self.beta) + '\n')
f.write(u'迭代次數(shù) iter_times=' + str(self.iter_times) + '\n')
f.write(u'每個類的高頻詞顯示個數(shù) top_words_num=' + str(self.top_words_num) + '\n')
# 保存每個主題 topic 的詞
logger.info(u"主題 topN 詞已保存到%s" % self.topNfile)
lda = LDAModel(dpre)
lda.est()
if __name__ == '__main__':
run()

全部論文及程序請見下方“ 只會建模 QQ名片” 點擊QQ名片即可