基于DGSC算法的校园网用户行为分析

本文最后更新于 9 个月前，文中所描述的信息可能已发生改变。

摘要：本文介绍了一种基于图论知识，通过DGSC算法对行为数据进行分类的方法，并着重探讨了该算法中对实际问题进行的的数学抽象与大致方法。另外，对仍待学习的聚类解法进行了展望。

关键词：图论，行为分析，聚类

问题背景与价值 ​

研究背景 ​

随着信息时代的迅速崛起，校园网作为学校信息化建设的核心组成部分，不仅在推动学校教育质量水平的提高中发挥着关键作用，同时也成为学生获取信息的重要途径。校园网使用行为关系到高校信息化建设的成效和学生的学术成果。

通过对相关数据的分析，大学生群体仍然是网民主力军[1]。因此，校园网不仅是信息传递的桥梁，更是重要的社交平台和学术交流场所。因此，及时关注校园网学生用户行为，不仅有助于高校更好地满足学生的信息需求，也为提高学校教育质量水平提供了支持。

而且。校园网用户行为研究不仅仅是一个技术性问题，更关乎大学生群体的心理健康。校园网的使用往往反映了学生的心理状态和社交需求，因此，通过校园网分析，及时掌握学生心理情绪动态，高校能够迅速对学生进行心理疏导，建立起更加健康和积极的网络环境。

研究价值 ​

本研究的价值体现在为高校网络管理提供科学合理的建议。通过深入了解校园网用户的行为模式和心理特征，我们能够为高校网络建设和管理提供有益的参考，规范和管理高校网络用户在网上发生的不良行为。这有助于建立一个有效的高校网络管理机制，提高网络安全水平，确保学术信息的正常流通，促进信息时代下高校教育的可持续发展。

综合而言，本研究不仅关注技术性问题，更关乎高校社会化管理的全面性和可持续性。

背景知识 ​

图 ​

图(Graph)是一种数据结构，是实际应用中最常用的数据结构[2-5]，它的特性有利于抽象函数的实现。其基本概念用数学公式表示为：无向加权图 $G=(V,E)$，非空集合 $V=(V,G)$，边集合 $E=(E,G)$。集合 $V$ 中的点即图 $G$ 中的顶点，集合 $E$ 为图 $G$ 的边， 每一条边就是一个点对 $(v,w)$，其中 $v,w\in V$。

DGSC算法 ​

以深度稀疏自编码器为架构的图论子空间聚类算法DGSC(Deep Graph Subspace Clustering)是一种利用深度稀疏自编码器进行数据降维处理，考虑到传统聚类算法预设初始聚类中心的问题，使用改进的图论子空间方法转换数据对象形式进行聚类的算法。

本文将着重描述该算法中将校园网行为数据转换为图的过程。

问题的数学抽象与解法 ​

数据向图的转换 ​

设置一组含有$m$个属性的样本，即存在一个有$m$个顶点的图，该图的相似矩阵可以使用数学公式表示，如公式(3-1)所示：

$$\begin{equation} W_{i j}=s(v_{i},v_{j})\tag{3-1} \end{equation}$$

其中 $s(v_{i},v_{j})$ 表示顶点与顶点之间的相似度，由该矩阵元素可以得到对角矩阵和度矩阵，见式(3-2)。

$$\begin{equation} D_{i j}=diag(D_{11},D_{12},...,D_{m n})\tag{3-2} \end{equation}$$

假设存在一数据集，其中包含了若干个人的社交关系，可以将每个人看作图中的一个顶点，两个人之间的社交关系看作一条边，若某人有很多朋友，那么此人的度(deg)便会偏高。此时，利用每个人的“度”可以计算分析出社交网络的结构。将数据转换为图的好处是可以帮助研究人员更好地理解和分析数据，发现数据之间的关系和模式，方便后续数据的分析和算法预测。

数据集中的每个对象都可作为图中的顶点，图中与顶点相连的所有边的权重定义为该顶点的度。由邻接矩阵和度矩阵便可生成规范化的拉普拉斯矩阵，对拉普拉斯矩阵进行普适性调整，改进原始拉普拉斯矩阵，以消除节点度数对图形分析造成的影响，避免重复计算。用函数 $q_i$ 表示“图”，寻找L矩阵的非零最小特值对应特向，具体见式(3-3)。

$$\begin{equation} \alpha\sum_{i=1}^{m}\sum_{j=1}^{m}{w_{i j}(q_{i}-q_{j})}^{2}=q^{T}{L}q\tag{3-3} \end{equation}$$

这种图论转换借助拉普拉斯映射思想，携带划分信息再进行用户行为聚类，相比于传统聚类算法，图论转换后再聚类更侧重于保留数据间的相似度，计算效率也更高。

改进图论子空间DGSC聚类算法 ​

将行为文件中的每个数据对象作为图中的顶点，对象间的相似性比作图中边的权，这时只需要考虑如何进行图的划分问题。对于行为数据生成的图进行子图的分割，图像分割问题就是根据像素点之间的相似程度来确定不同的区域，从而分割图像，则定义相邻像素点之间的相似程度为边，相似程度越大，边的权值越大。

将数据集转化为无向加权图是完成聚类的第一步，接下来是对图的划分问题，图中顶点即数据集中的对象，边的权重即对象间的相似度。图中边的权重计算是使用加权邻接矩阵

$$\begin{equation} A(i,j)= \begin{cases} s(v_{i},v_{j}) , e(i,j)\in E(G) \\ c & \end{cases} \tag{3-4} \end{equation}$$

来表示对象间的相似度。将对象间的相似性比作图中边的权，此时 不需要考虑常规方法中计算用户间的相似度，应该关注在图划分过程中边的权重计算， 通过割集准则实现后续图划分，即聚类过程。

聚类解法 ​

常见图划分准则有比例割集准则RCut(Ratio Cut)、最小割集准则MCut(Mini Cut)、 平均割集准则ACut(Average Cut)、规范割集准则NCutN(ormalized Cut) [6]等。通过资料检索，得知规范割集准则即最小化NCut函数，可以均衡分割子图，$assoc(A,V)$ 表示图划分过程中所有边的权重的计算和，即对象间的相似性计算。此时在图划分过程中，只需关注边的权重计算，而不需 要常规计算用户间的相似度，此割集准则能较好的保留数据集中属性与属性间的相似性[7]。具体实施和解决方法有待后续学习。

参考文献 ​

[1] 邓卫华, 王李俊, 王静, 高专大学生网络使用与网络成瘾现状调查研究. 科技视界, 2022(127-129). DOI: 10.19694/j.cnki.issn2095-2457.2022.06.40.

[2] THAIPRAYOON S UNGER H. A Neighbourhood-based Clustering Method for Graph Data Models. The Autonomous Web, 2022, 101:111.

[3] LAO L, WU X, WU K, Graph Theory with Modify-edge Clustering Algorithm Based on Maximum Weighted Entropy//2006 6th WorldCongress on Intelligent Control and Automation. 2006: 9730-9733.

[4] GAVIÃO L O, SANT’ANNA A P, GARCIA P A A, Multi-criteria Decision Support to Criminology by Graph Theory and Compositionof Probabilistic Preferences. Pesquisa Operacional, 2021, 41.

[5] GUNTURI S K SARKAR D. Network Reconfiguration for Searching Maximum Loading Capacity Radial Network: An Efficient GraphTheory-Based Machine Learning Approach. IETE Journal of Research, 2023: 1-11.

[6] 李玲俐. 谱聚类算法及其应用综述. 软件导刊, 2016, 15(54-56).

[7] 王京. 基于图论子空间的校园网用户行为分析研究. 河南工业大学, 2023.3