基于卡方特征選擇和LDA主題模型的中文短文本分類

鄭誠(chéng)　熊大康　劉倩倩

摘要：中文短文本自身包含詞匯個(gè)數(shù)少、描述信息能力弱，常用的文本分類方法對(duì)于短文本分類效果不理想。同時(shí)傳統(tǒng)的文本分類方法在處理大規(guī)模文本分類時(shí)會(huì)出現(xiàn)向量維數(shù)很高的情況，造成算法效率低，而且一般用于長(zhǎng)文本分類的特征選擇方法都是基于數(shù)理統(tǒng)計(jì)的，忽略了文本中詞項(xiàng)之間的語(yǔ)義關(guān)系。針對(duì)以上問(wèn)題本文提出基于卡方特征選擇和LDA主題模型的中文短文本分類方法，方法使用LDA主題模型的訓(xùn)練結(jié)果對(duì)傳統(tǒng)特征選擇方法進(jìn)行特征擴(kuò)展，以達(dá)到將數(shù)理信息和語(yǔ)義信息融入分類算法的目的。對(duì)比試驗(yàn)表明，這種方法提高了中文短文本分類效果。

關(guān)鍵詞：短文本分類 特征選擇 主題模型

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）13-3182-04

The Short Text Classification Method Based on CHI Feature Selection and LDA Topic Model

ZHENG Cheng， XIONG Da-kang， LIU Qian-qian

（School of Computer Science and Technology， Anhui University， Hefei 230039，China）

Abstract： Chinese short texts contain few words and describe weak signals. the common text classification methods dont performs well for the short text. In Vector Model， the dimension of the document vector is huge. The huge vector leads to inefficient algorithms. The traditional feature selection methods are based on the mathematical statistics， ignoring the semantic relationship between terms from text. Then a method based on CHI feature selection and LDA topic model is introduced to classify Chinese short texts. In this method， the result of the LDA topic model is applied to extend the features of data set， which can make classification algorithm contains mathematical statistics and semantic information. The experiment result shows that the method in this paper improves the effect of text classification.

Key words： short text classification；feature selection；topic model

自然語(yǔ)言處理中的主題模型起源于Deerwester等人在1990年提出的隱性語(yǔ)義索引（Latent Semantic Indexing，LSI）[1]，它為主題模型的發(fā)展奠定了基礎(chǔ)。1999年Hofmann在LSI的基礎(chǔ)上提出了概率隱性語(yǔ)義索引（probabilistic Latent Semantic Indexing，pLSI）[2]，這是一個(gè)真正意義上的主題模型。在pLSI的基礎(chǔ)上Blei等人在2003年將其擴(kuò)展得到更為完全的概率生成模型LDA（Latent Dirichlet Allocation）[3]。LDA主題模型可以用于提取文本隱含主題信息[4]，因此在文本分類領(lǐng)域受到廣泛的關(guān)注，越來(lái)越多的研究人員對(duì)LDA模型進(jìn)行改進(jìn)并提出了Labeled-LDA、Link-PLSA-LDA等文本分類模型[5-6]。除了LDA模型，Xiaohui Yan等人提出了用于短文本分類的BTM（Biterm Topic Model）[7]模型，取得了較好的分類效果。

目前，短文本分類的一種流行方法是利用一些額外的信息來(lái)輔助分類，引入額外信息的目的是是挖掘短文本所表達(dá)的信息。例如王鵬[8]等利用依存關(guān)系抽取詞擴(kuò)充短文本特征；寧亞輝[9]等借助知網(wǎng)提出基于領(lǐng)域詞語(yǔ)本體的短文本分類；徐盛[10]等利用知網(wǎng)上下位關(guān)系擴(kuò)展短文本特征。以上方法都需要大規(guī)模背景知識(shí)庫(kù)或語(yǔ)料，處理大規(guī)模背景語(yǔ)料費(fèi)時(shí)費(fèi)力，同時(shí)背景知識(shí)庫(kù)更新慢、可擴(kuò)展性差，難以適應(yīng)網(wǎng)絡(luò)短文本詞匯新穎、專業(yè)的特點(diǎn)。

提高文本分類效果最重要的是如何提取文本特征，常用的特征提取方法有文檔頻率（DF）、互信息（MI）、信息增益（IG）[11]、卡方統(tǒng)計(jì)（CHI）[12]等等，大量的實(shí)驗(yàn)和研究顯示CHI方法的特征選擇效果好于其他的方法，因此本文使用CHI方法。LDA模型可以用于挖掘詞與詞之間的隱含語(yǔ)義關(guān)系。該文提出了基于卡方特征選擇和LDA主題模型的方法，在此基礎(chǔ)上使用SVM[13]進(jìn)行分類，并與BTM[14]的實(shí)驗(yàn)結(jié)果進(jìn)行比較。

本文組織如下：第2節(jié)介紹CHI特征選擇方法；第3節(jié)介紹LDA主題模型和BTM模型；第4節(jié)介紹本文提出的短文本分類方法實(shí)驗(yàn)過(guò)程并分析實(shí)驗(yàn)結(jié)果；最后總結(jié)全文并展望下一步工作。

1 CHI特征選擇

CHI用于衡量特征詞t和類別[ci]之間的關(guān)聯(lián)程度，方法假設(shè)特征t和類別[ci]之間的非獨(dú)立關(guān)系類似于具有一維自由度的[χ2]分布，t對(duì)于[ci]的CHI值計(jì)算如公式（1）所示：endprint

[χ2（t，ci）=N×（A×D-C×B）2（A+C）×（B+D）×（A+B）×（C+D）] （1）

公式中，N表示訓(xùn)練語(yǔ)料中的文檔總數(shù)，[ci]表示類別，t表示特征詞，A表示屬于[ci]類且包含t 的文檔頻數(shù)，B表示不屬于[ci]但包含t 的文檔頻數(shù)，C表示屬于[ci]但是不包含t 的文檔頻數(shù)，D是既不屬于[ci]也不包含t的文檔頻數(shù)。[χ2（t，ci）]值越高表示t和[ci]的相關(guān)度越大，[χ2（t，ci）]值為0表示t和[ci]不相關(guān)。

2 LDA模型和BTM模型

2.1 LDA主題模型

LDA模型是一個(gè)三層次的概率模型即“文檔-主題-詞項(xiàng)”，是對(duì)文本中隱含主題的一種建模方法，屬于生成模型。它將文檔表示成主題的概率分布，主題表示成詞的概率分布。LDA模型如圖1所示：

圖1 LDA模型圖

圖中M表示語(yǔ)料庫(kù)中文本個(gè)數(shù)，L表示一篇文本的長(zhǎng)度，z表示主題，[ω]表示詞項(xiàng)，[α]、[β]是超參數(shù)，其中[β]是個(gè)k×V的矩陣，k為主題個(gè)數(shù)，V是詞項(xiàng)的數(shù)目，[βij]表示第i個(gè)主題下第j個(gè)詞項(xiàng)的概率，[θ]表示文檔的主題概率分布。

LDA主題模型的基本思想是隨機(jī)生成一篇有N個(gè)詞項(xiàng)組成的文檔，每個(gè)詞項(xiàng)以一定的概率選擇一個(gè)主題，并從這個(gè)主題中以一定的概率選擇出來(lái)。

給定[α]和[β]，LDA模型用概率模型表示如公式（2）所示：

[P（θ，z，w|α，β）=P（θ|α）n=1NP（zn|θ）P（wn|zn，β）] （2）

整個(gè)語(yǔ)料庫(kù)的概率如公式（3）所示：

[P（D|α，β）=d=1Mp（θd|α）（n=1Ndzndp（znd|θd）p（wdn|znd，β））dθn] （3）

其中D表示文檔集合，[Nd]表示第d篇文檔的長(zhǎng)度，[θd]表示第d篇文檔的主題概率分布，[wdn]表示第d篇文檔的第n個(gè)單詞，[znd]表示第d篇文檔的第n個(gè)單詞的主題。

2.2 BTM模型

BTM模型表示如圖2所示：

圖2 BTM模型圖

其中[θ]表示文檔的主題概率分布，[?]表示主題下詞的概率分布，Z表示主題，|B|表示生成的biterm的個(gè)數(shù)，K表示主題個(gè)數(shù)，[Wi]和[Wj]表示抽取出來(lái)的詞對(duì)。

每一個(gè)biterm[b=（Wi，Wi）]的聯(lián)合概率如公式（4）所示：

[P（b）=zP（z）P（wi|z）P（wj|z）=zθz?i|z?j|z] （4）

整個(gè)biterm集合的概率如公式（5）所示：

[P（B）=（i，j）zθz?i|z?j|z] （5）

3 實(shí)驗(yàn)過(guò)程及結(jié)果

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)中使用的數(shù)據(jù)集是由數(shù)據(jù)堂下載的百度知道問(wèn)題數(shù)據(jù)集。數(shù)據(jù)集中包含電腦/數(shù)碼、教育/科學(xué)、娛樂(lè)、地區(qū)、體育/運(yùn)動(dòng)等14個(gè)大類，各類別包含問(wèn)題個(gè)數(shù)差距比較大，最少的一類是品牌專區(qū)類，只有五個(gè)。鑒于我們需要訓(xùn)練及測(cè)試用的短文本數(shù)量較大，所以選擇電腦/數(shù)碼、教育/科學(xué)、娛樂(lè)、地區(qū)四個(gè)類別各2000篇，其中1500篇作為訓(xùn)練數(shù)據(jù)，其余500篇作為測(cè)試數(shù)據(jù)。

3.2 硬件環(huán)境及實(shí)驗(yàn)平臺(tái)

實(shí)驗(yàn)環(huán)境如表1所示。

表1 實(shí)驗(yàn)環(huán)境

[CPU＼&Intel（R） Core（TM） i5＼&內(nèi)存＼&4.00GB＼&編程語(yǔ)言＼&JAVA＼&IDE＼&Eclipse＼&]

3.3 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

對(duì)于文本分類的效果采用3種常規(guī)指標(biāo)進(jìn)行評(píng)估[15]：準(zhǔn)確率（Precision，P），召回率（Recall，R），[F1]值（F-measure，[F1]）。

3.4 實(shí)驗(yàn)結(jié)果

BTM模型做短文本分類隨著主題數(shù)目的增加分類性能不斷變化，在主題數(shù)為20時(shí)分類準(zhǔn)確率達(dá)到最高，結(jié)果如圖3所示。

圖3 BTM模型在不同主題個(gè)數(shù)下分類性能

使用基于卡方特征選擇和LDA主題模型的方法，分類性能隨著主題數(shù)目的增加變化，在主題數(shù)目為30時(shí)分類結(jié)果準(zhǔn)確率最高，結(jié)果如圖4所示：

圖4 LDA模型在不同主題個(gè)數(shù)下分類性能

BTM模型在主題數(shù)為20，LDA模型在主題數(shù)為30的情況下，電腦/數(shù)碼、教育/科學(xué)、娛樂(lè)、地區(qū)四個(gè)類別的實(shí)驗(yàn)結(jié)果如表2所示。

表2 兩種方法在各個(gè)類別上的分類結(jié)果

[類別＼&BTM＼&CHI+LDA＼&準(zhǔn)確率（%）＼&召回率（%）＼&F1（%）＼&準(zhǔn)確率（%）＼&召回率（%）＼&F1（%）＼&電腦/數(shù)碼＼&0.747＼&0.586＼&0.657＼&0.787＼&0.680＼&0.725＼&教育/科學(xué)＼&0.554＼&0.408＼&0.470＼&0.729＼&0.666＼&0.696＼&娛樂(lè)＼&0.441＼&0.762＼&0.559＼&0.567＼&0.620＼&0.592＼&地區(qū)＼&0.538＼&0.406＼&0.463＼&0.579＼&0.652＼&0.589＼&]

從上表中可以看出，在所有類別中，基于卡方特征選擇和LDA模型的方法比使用BTM模型的方法各項(xiàng)指標(biāo)均有提高，分類結(jié)果較為理想。

4 結(jié)束語(yǔ)

本文使用了基于卡方特征選擇和LDA主題模型相結(jié)合的方法進(jìn)行短文本分類，解決了傳統(tǒng)特征選擇方法無(wú)法描述語(yǔ)義信息以及短文本長(zhǎng)度短、描述信息能力弱的問(wèn)題，使用LDA模型的訓(xùn)練結(jié)果對(duì)特征選擇結(jié)果進(jìn)行特征擴(kuò)展，并用SVM分類器進(jìn)行分類。并且和最近流行的用于短文本分類的BTM模型的實(shí)驗(yàn)結(jié)果進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明基于卡方特征選擇和LDA主題模型的分類方法在提高了分類效果，這表明將語(yǔ)義信息加入特征確實(shí)能夠提高分類效果，因此如何更加精確地表示隱含的語(yǔ)義特征并將其應(yīng)用于信息檢索、社會(huì)計(jì)算等領(lǐng)域是下一步需要研究的工作。

參考文獻(xiàn)：

[1] Deerwester S C， Dumais S T， Landauer T K， et al. Indexing by latent semantic analysis[J]. JASIS， 1990， 41（6）： 391-407.

[2] Hofmann T. Probabilistic latent semantic indexing[C]//Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval. ACM， 1999： 50-57.

[3] Blei D M， Ng A Y， Jordan M I. Latent dirichlet allocation[J]. the Journal of machine Learning research， 2003， 3： 993-1022.

[4] 徐戈， 王厚峰. 自然語(yǔ)言處理中主題模型的發(fā)展[J]. 計(jì)算機(jī)學(xué)報(bào)， 2011， 34（8）： 1423-1436.

[5] 李文波， 孫樂(lè)， 張大鯤. 基于 Labeled-LDA 模型的文本分類新算法 [J]. 計(jì)算機(jī)學(xué)報(bào)， 2008， 31（4）： 620-627.

[6] Nallapati R， Cohen W W. Link-PLSA-LDA： A New Unsupervised Model for Topics and Influence of Blogs[C]//Proceedings of the International Conference for Weblogs and Social Media. Seattle，Washington，USA，2008.

[7] Yan X， Guo J， Lan Y， et al. A biterm topic model for short texts[C]//Proceedings of the 22nd international conference on World Wide Web. International World Wide Web Conferences Steering Committee， 2013： 1445-1456.

[8] 王鵬， 樊興華. 中文文本分類中利用依存關(guān)系的實(shí)驗(yàn)研究[J]. 計(jì)算機(jī)工程與應(yīng)用， 2010， 46（3）： 131-133.

[9] 寧亞輝， 樊興華， 吳渝. 基于領(lǐng)域詞語(yǔ)本體的短文本分類[J]. 計(jì)算機(jī)科學(xué)， 2009， 36（3）： 142-145.

[10] 王盛， 樊興華， 陳現(xiàn)麟. 利用上下位關(guān)系的中文短文本分類[J]. 計(jì)算機(jī)應(yīng)用， 2010 （003）： 603-606.

[11] 郭亞維， 劉曉霞. 文本分類中信息增益特征選擇方法的研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2012，48（27）： 119-122.

[12] 裴英博， 劉曉霞. 文本分類中改進(jìn)型 CHI 特征選擇方法的研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2011，47（4）： 128-130.

[13] CRISTIANINI N， TAYLOR J S. An introduction to support vector machines and other kernel-based learning methods[M]. Translated by LI Guo-zheng， WANG Meng， ZENG Hua-jun. Beijing： Publishing House of Electronics Industry， 2004.

[14] Yan X， Guo J， Lan Y， et al. A biterm topic model for short texts[C]//Proceedings of the 22nd international conference on World Wide Web. International World Wide Web Conferences Steering Committee， 2013： 1445-1456.

[15] 宋楓溪， 高林. 文本分類器性能評(píng)估指標(biāo)[J]. 計(jì)算機(jī)工程， 2004， 30（13）： 107-109.endprint

從上表中可以看出，在所有類別中，基于卡方特征選擇和LDA模型的方法比使用BTM模型的方法各項(xiàng)指標(biāo)均有提高，分類結(jié)果較為理想。

4 結(jié)束語(yǔ)

本文使用了基于卡方特征選擇和LDA主題模型相結(jié)合的方法進(jìn)行短文本分類，解決了傳統(tǒng)特征選擇方法無(wú)法描述語(yǔ)義信息以及短文本長(zhǎng)度短、描述信息能力弱的問(wèn)題，使用LDA模型的訓(xùn)練結(jié)果對(duì)特征選擇結(jié)果進(jìn)行特征擴(kuò)展，并用SVM分類器進(jìn)行分類。并且和最近流行的用于短文本分類的BTM模型的實(shí)驗(yàn)結(jié)果進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明基于卡方特征選擇和LDA主題模型的分類方法在提高了分類效果，這表明將語(yǔ)義信息加入特征確實(shí)能夠提高分類效果，因此如何更加精確地表示隱含的語(yǔ)義特征并將其應(yīng)用于信息檢索、社會(huì)計(jì)算等領(lǐng)域是下一步需要研究的工作。

參考文獻(xiàn)：

[1] Deerwester S C， Dumais S T， Landauer T K， et al. Indexing by latent semantic analysis[J]. JASIS， 1990， 41（6）： 391-407.

[2] Hofmann T. Probabilistic latent semantic indexing[C]//Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval. ACM， 1999： 50-57.

[3] Blei D M， Ng A Y， Jordan M I. Latent dirichlet allocation[J]. the Journal of machine Learning research， 2003， 3： 993-1022.

[4] 徐戈， 王厚峰. 自然語(yǔ)言處理中主題模型的發(fā)展[J]. 計(jì)算機(jī)學(xué)報(bào)， 2011， 34（8）： 1423-1436.

[5] 李文波， 孫樂(lè)， 張大鯤. 基于 Labeled-LDA 模型的文本分類新算法 [J]. 計(jì)算機(jī)學(xué)報(bào)， 2008， 31（4）： 620-627.

[6] Nallapati R， Cohen W W. Link-PLSA-LDA： A New Unsupervised Model for Topics and Influence of Blogs[C]//Proceedings of the International Conference for Weblogs and Social Media. Seattle，Washington，USA，2008.

[7] Yan X， Guo J， Lan Y， et al. A biterm topic model for short texts[C]//Proceedings of the 22nd international conference on World Wide Web. International World Wide Web Conferences Steering Committee， 2013： 1445-1456.

[8] 王鵬， 樊興華. 中文文本分類中利用依存關(guān)系的實(shí)驗(yàn)研究[J]. 計(jì)算機(jī)工程與應(yīng)用， 2010， 46（3）： 131-133.

[9] 寧亞輝， 樊興華， 吳渝. 基于領(lǐng)域詞語(yǔ)本體的短文本分類[J]. 計(jì)算機(jī)科學(xué)， 2009， 36（3）： 142-145.

[10] 王盛， 樊興華， 陳現(xiàn)麟. 利用上下位關(guān)系的中文短文本分類[J]. 計(jì)算機(jī)應(yīng)用， 2010 （003）： 603-606.

[11] 郭亞維， 劉曉霞. 文本分類中信息增益特征選擇方法的研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2012，48（27）： 119-122.

[12] 裴英博， 劉曉霞. 文本分類中改進(jìn)型 CHI 特征選擇方法的研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2011，47（4）： 128-130.

[13] CRISTIANINI N， TAYLOR J S. An introduction to support vector machines and other kernel-based learning methods[M]. Translated by LI Guo-zheng， WANG Meng， ZENG Hua-jun. Beijing： Publishing House of Electronics Industry， 2004.

[14] Yan X， Guo J， Lan Y， et al. A biterm topic model for short texts[C]//Proceedings of the 22nd international conference on World Wide Web. International World Wide Web Conferences Steering Committee， 2013： 1445-1456.

[15] 宋楓溪， 高林. 文本分類器性能評(píng)估指標(biāo)[J]. 計(jì)算機(jī)工程， 2004， 30（13）： 107-109.endprint

從上表中可以看出，在所有類別中，基于卡方特征選擇和LDA模型的方法比使用BTM模型的方法各項(xiàng)指標(biāo)均有提高，分類結(jié)果較為理想。

4 結(jié)束語(yǔ)

本文使用了基于卡方特征選擇和LDA主題模型相結(jié)合的方法進(jìn)行短文本分類，解決了傳統(tǒng)特征選擇方法無(wú)法描述語(yǔ)義信息以及短文本長(zhǎng)度短、描述信息能力弱的問(wèn)題，使用LDA模型的訓(xùn)練結(jié)果對(duì)特征選擇結(jié)果進(jìn)行特征擴(kuò)展，并用SVM分類器進(jìn)行分類。并且和最近流行的用于短文本分類的BTM模型的實(shí)驗(yàn)結(jié)果進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明基于卡方特征選擇和LDA主題模型的分類方法在提高了分類效果，這表明將語(yǔ)義信息加入特征確實(shí)能夠提高分類效果，因此如何更加精確地表示隱含的語(yǔ)義特征并將其應(yīng)用于信息檢索、社會(huì)計(jì)算等領(lǐng)域是下一步需要研究的工作。

參考文獻(xiàn)：

[1] Deerwester S C， Dumais S T， Landauer T K， et al. Indexing by latent semantic analysis[J]. JASIS， 1990， 41（6）： 391-407.

[2] Hofmann T. Probabilistic latent semantic indexing[C]//Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval. ACM， 1999： 50-57.

[3] Blei D M， Ng A Y， Jordan M I. Latent dirichlet allocation[J]. the Journal of machine Learning research， 2003， 3： 993-1022.

[4] 徐戈， 王厚峰. 自然語(yǔ)言處理中主題模型的發(fā)展[J]. 計(jì)算機(jī)學(xué)報(bào)， 2011， 34（8）： 1423-1436.

[5] 李文波， 孫樂(lè)， 張大鯤. 基于 Labeled-LDA 模型的文本分類新算法 [J]. 計(jì)算機(jī)學(xué)報(bào)， 2008， 31（4）： 620-627.

[6] Nallapati R， Cohen W W. Link-PLSA-LDA： A New Unsupervised Model for Topics and Influence of Blogs[C]//Proceedings of the International Conference for Weblogs and Social Media. Seattle，Washington，USA，2008.

[7] Yan X， Guo J， Lan Y， et al. A biterm topic model for short texts[C]//Proceedings of the 22nd international conference on World Wide Web. International World Wide Web Conferences Steering Committee， 2013： 1445-1456.

[8] 王鵬， 樊興華. 中文文本分類中利用依存關(guān)系的實(shí)驗(yàn)研究[J]. 計(jì)算機(jī)工程與應(yīng)用， 2010， 46（3）： 131-133.

[9] 寧亞輝， 樊興華， 吳渝. 基于領(lǐng)域詞語(yǔ)本體的短文本分類[J]. 計(jì)算機(jī)科學(xué)， 2009， 36（3）： 142-145.

[10] 王盛， 樊興華， 陳現(xiàn)麟. 利用上下位關(guān)系的中文短文本分類[J]. 計(jì)算機(jī)應(yīng)用， 2010 （003）： 603-606.

[11] 郭亞維， 劉曉霞. 文本分類中信息增益特征選擇方法的研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2012，48（27）： 119-122.

[12] 裴英博， 劉曉霞. 文本分類中改進(jìn)型 CHI 特征選擇方法的研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2011，47（4）： 128-130.

[13] CRISTIANINI N， TAYLOR J S. An introduction to support vector machines and other kernel-based learning methods[M]. Translated by LI Guo-zheng， WANG Meng， ZENG Hua-jun. Beijing： Publishing House of Electronics Industry， 2004.

[14] Yan X， Guo J， Lan Y， et al. A biterm topic model for short texts[C]//Proceedings of the 22nd international conference on World Wide Web. International World Wide Web Conferences Steering Committee， 2013： 1445-1456.

[15] 宋楓溪， 高林. 文本分類器性能評(píng)估指標(biāo)[J]. 計(jì)算機(jī)工程， 2004， 30（13）： 107-109.endprint