【文章內(nèi)容簡介】 in a matrix R0 (n, m), by duplicating, for each Ui of R, the row in R associated to Ui with cardinality of Ui . It is also possible to obtain a matrix associated to the database B, by replacing, for each Ui of R, the row in R associated to Ui by rows associated to Ui in B. Replacing n rows of B by p rows in R permit to decrease size of data to treat. Each row of R represents the mean of rows in B associated to Ui . Let RX be the reduced matrix associated to a projection PX of B. Given X a subset of attributes of database B from an attributepartition A. M is the operation of projection defined by M: B, X ! PX .Massociates the projection PX of B to the subset X. PX is obtain using a mask MX on matrix B. The mask MX is defined by a n, m matrix such as MXi j = 1, 8i, 8 j with Aj 2 X and MXi j = 0, 8i, 8 j with Aj 62 X. The operation of projectionM is then defined by:M(B, X) = MX t X = PX . Partition F. A partition of a database is a row partition of the associated matrix with putation of rows. This operation is achieved by the use of a classical clustering algorithm as a step of algorithm DPC. 網(wǎng)格上分布式數(shù)據(jù)庫的聚類方法 ScienceDirect:Future Generation Computer Systems 23 (2020) 997– 1002 摘要 ：集群和網(wǎng)格的工作站為數(shù)據(jù)挖掘過程提供可利用的資源。為了利用這些資源，新的分布式算法是必要的，特別是涉及分配數(shù)據(jù)以及使用分區(qū)的方法。我們提出一個被稱為逐步聚類的聚類算法，它可以為網(wǎng)格中的數(shù)據(jù)提供一個“智能”分區(qū)。該算法的應(yīng)用顯示了分布式數(shù)據(jù)挖掘任務(wù)。 關(guān)鍵詞：網(wǎng)格式和并行處理；數(shù)據(jù)挖掘；聚類 導(dǎo)言 數(shù)據(jù)庫中的知識發(fā)現(xiàn)，也稱為數(shù)據(jù)挖掘，是 一種寶貴的工程工具，可從非常大的數(shù)據(jù)庫提取有用的信息。此工具通常需要高計算能力，可以提供并行處理和分配。這里的開發(fā)工作是 DisDaMin 項(xiàng)目一部分， DisDaMin 項(xiàng)目是利用分布式計算處理數(shù)據(jù)挖掘的問題（如關(guān)聯(lián)規(guī)則，聚類分析，??）。 DisDaMin 的目的是為數(shù)據(jù)挖掘問題開發(fā)并行和分布式方案。它在執(zhí)行時間方面實(shí)現(xiàn)了兩個成果：成果從并行的使用和減少計算來獲得（通過使用一種數(shù)據(jù)的智能分布和計算）。在并行和分布式環(huán)境，如網(wǎng)格或集群，限制固有的執(zhí)行平臺，必須考慮到的算法。中心記憶的不存在迫使我們分發(fā)數(shù)據(jù)到片段，并且 利用并行來處理這些片段。由于在這樣的環(huán)境下的高通信成本，并行計算必須盡可能避免昂貴的通訊費(fèi)（或至少是同步）。但是，現(xiàn)有的網(wǎng)格數(shù)據(jù)挖掘項(xiàng)目（如 Discovery Net， GridMiner， DMGA[7]，或 Knowledge Grid[11]）提供的機(jī)制，都是整合和部署經(jīng)典算法的網(wǎng)格，但不是新的網(wǎng)格的算法。 另一方面， DisDaMin 項(xiàng)目要處理的數(shù)據(jù)挖掘任務(wù)考慮數(shù)據(jù)挖掘細(xì)節(jié)以及網(wǎng)格計算細(xì)節(jié)。數(shù)據(jù)挖掘的問題，獲取智能數(shù)據(jù)分區(qū)是必要的，以便計算更單獨(dú)的數(shù)據(jù)片段。其主要的問題是如何取得這個智能分區(qū)。對于關(guān)聯(lián)規(guī)則 的問題，例如，智能分區(qū)的主要標(biāo)準(zhǔn)時每個片段的數(shù)據(jù)行是盡可能相似的（根據(jù)每個屬性的值），片段之間數(shù)據(jù)行是盡可能不同的。這一標(biāo)準(zhǔn)通常需要我們訪問整個數(shù)據(jù)庫來并行這個問題。它使我們能夠降低復(fù)雜性（見 [2]）。由于分配的標(biāo)準(zhǔn)在目標(biāo)聚類算法表現(xiàn)得很相似，分區(qū)可產(chǎn)生的聚類待遇。從關(guān)聯(lián)規(guī)則問題方面的聚類獲得的智能分區(qū)的好處已經(jīng)進(jìn)行了研究（見 [2]）。 顯然，聚類階段本身已分發(fā)，而且需要快速進(jìn)行，為了不減慢全球執(zhí)行的時間。在網(wǎng)格上，聚類方法將在引入逐步分布聚類算法的執(zhí)行之前被描述。 聚類 聚類是數(shù)據(jù)分割成不同的群體（集群） 的過程，使同一集群的數(shù)據(jù)相似，但不同于其他集群。獨(dú)特的聚類方法可以根據(jù)兩種主要原則分開：分層方法和分割方法。 Kmeans 聚類 凝聚聚類 輸入：數(shù)據(jù)，用來計算的聚類號（ k） 輸出：數(shù)據(jù)的聚類 輸入：數(shù)據(jù)，結(jié)束標(biāo)準(zhǔn) 輸出：數(shù)據(jù)的聚類 （ 1）初始化 k對象作為初始中心 （ 2）重復(fù) （ 3）轉(zhuǎn)讓每個對象到最近的聚類 （ 4）更新聚類的值 （ 5）知道沒有數(shù)據(jù)可以改變 （ 6）返回 k被定義的聚類 （ 1）考慮每個數(shù)據(jù)作為聚類 （ 2）重復(fù) （ 3）合并最近的兩個聚類 （ 4）更新聚類的距離 （ 5）直到結(jié)束標(biāo)準(zhǔn) （ 6）返回被定義 的聚類 圖 分層的方法是由凝聚部分（即最初根據(jù)惟一的數(shù)據(jù)實(shí)例考慮分區(qū)，合并鄰近的簇，直到滿足終止的標(biāo)準(zhǔn)）和分布部分（即最初根據(jù)一個集群考慮分區(qū)，這個集群包含所有數(shù)據(jù)實(shí)例并且消減集群迭代直至終止）組成。劃分的方法是以距離為基礎(chǔ)的方法（如 KMeans [8]所示），基于密度的方法或基于概率的方法。其他標(biāo)準(zhǔn)使我們能夠區(qū)分聚類方法（見 [10]）；那些方法基于集群的數(shù)據(jù)實(shí)例的隸屬度（很難被引用或含糊不清（見 [4]）），以及數(shù)據(jù)實(shí)例的增量方法在某一時刻可以代替所有數(shù)據(jù)時被考慮（見 [5]），這種方法基于鄰里搜索（ kneareat 鄰居）??兩個著名的聚類算法是分割 KMeans（見 [8]）（產(chǎn)生近似的結(jié)果，并有可接受的時間復(fù)雜性）和凝聚的方法（見 [12]）（其中產(chǎn)量相對優(yōu)質(zhì)的成果，但受到時間復(fù)雜度的限制）。 原則 Kmeans： KMeans 是一個迭代算法，構(gòu)建了數(shù)據(jù)實(shí)例的初始化 K分區(qū)。迭代遷移技術(shù)試圖通過將數(shù)據(jù)從一組移動到另一組的方式來改善分區(qū)，直至終止的標(biāo)準(zhǔn)（見圖 1，左部分）。 KMeans 將產(chǎn)生局部最優(yōu)的結(jié)果。 凝聚聚類的原則：分層凝聚聚類包括一個問題的自下而上的方法，這個問題是要把所有數(shù) 據(jù)分別作為集群還是在每個迭代上合并兩個最近的集群直至終止條件（見圖 1，右部分）。這種方法使用了相似度量矩陣，使該方法不適合大數(shù)據(jù)集（由于存儲成本）。 并行算法：前面的兩個方法需要訪問整個數(shù)據(jù)庫或在每次迭代進(jìn)行溝通，以獲得正確的解決辦法。并行方法存在 KMeans（見 [3]）和凝聚聚類中。并行版本也存在于其他算法引用之前（見 [6]）。為了達(dá)到同一質(zhì)量集群作為順序聚類的并行集群來說，大量的通信是必需的。這些方法適用于作為 CC – NUMA 或 SMP 的大型計算機(jī)，它使用一個相同的記憶和快速的內(nèi)部交互網(wǎng)絡(luò)（ IBM SP3 的并行數(shù)據(jù)挖掘）。在現(xiàn)有的并行方法中大量的通信產(chǎn)生網(wǎng)格文本里的性能問題。將在下一節(jié)中考慮分布式逐步聚類（ DPC）方法的這些制約因素。 逐步聚類 分布式逐步聚類方法以循序漸進(jìn)的方式處理屬性（在分布式逐步聚類技術(shù)中，它有別于現(xiàn)有的增量方法，現(xiàn)有的增量方法處理越來越多的數(shù)據(jù)實(shí)例取代處理越來越多的屬性）。該方法適用于利用當(dāng)?shù)厮惴ㄒ詷?gòu)建全球結(jié)果無需同步的分布式執(zhí)行。分布式逐步聚類技術(shù)通過CLIQUE（見 [1]）這種序列聚類算法被定義， CLIQUE 包括在每層被映射的聚類數(shù)據(jù)，并將這些數(shù)據(jù)預(yù)測定義為深度聚類。該 方法假定整個數(shù)據(jù)庫都能被映射。在網(wǎng)格文本中，通過垂直分裂（多基）來假定來分布數(shù)據(jù)庫。分布式逐步聚類技術(shù)自下而上的辦法進(jìn)行工作，它考慮數(shù)據(jù)庫的屬性。它首先計算集群在包含一些屬性的標(biāo)準(zhǔn)片段中，然后結(jié)合這些集群獲得集群的更高層面。這兩個步驟（即垂直片段的集群和集群的合并）以分布的方法被執(zhí)行，這種方法受益于分布式執(zhí)行。在下面的部分將研究分布式逐步聚類方法。三個步驟可確定：初步聚類，交叉和合并優(yōu)化的步驟。 K/A A1 Aj Am 1 ith instance 1 j m ith row K1 Ki v11? v1j? v1m ? ? v11 ? v1j ? v1m ? ? Vi1? vij? vim Vi1 ? vij ? vim Kn ? ? Vn1? vnj? vnm n ? ? Vn1 ? vnj ? vnm Database B Matrix V associated to database B 圖 B和關(guān)聯(lián)矩陣 V 定義 一個屬性為 M屬性列和 N 行（實(shí)例）的數(shù)據(jù)庫，被表示 B=（ A， K， V），此處： A = {A1, A2,? Am}是一個有限的屬性集 。 K = {K1, K2,? Kn}是數(shù)據(jù)庫行的關(guān)鍵字集； V 是關(guān)聯(lián)矩陣 1（見圖 .2）， vi， j（ 1 _ i _ m 和 1 _ j _ n 的位置）是第 j 行的第 i 個坐標(biāo)。設(shè) U 是一個基于關(guān)鍵字的分區(qū)， 2就是 U={U1, S? ,Up},Ui={Kl 2 K},iUi =K 和 Ui/Uj= 。設(shè) A是一個屬性劃分，如 A={X1,? ,Xq},Xj={Ak 2 A},SjXj=A 和 Xj/Xk= 。設(shè) PX 是數(shù)據(jù)庫 B 在屬性子集X(X2 A)上的映射。 給定 X = {Ak? Ar }， PX 的相關(guān)矩陣有 n行和 q 列（行代表 B的每個實(shí)例，列待變 X的每個屬性 Aj）。 PX 的第 j 列和 B 的第 j 列相關(guān)聯(lián)（見圖 3）。給定數(shù)據(jù)庫 B（ m 列）的一個實(shí)例分割 U（ P 個因子），（ U， B）和下一層矩陣 R 相關(guān)聯(lián)（ p， r 矩陣，見圖 3）。 R 的每一行和數(shù)據(jù)庫 B的實(shí)例 Ui的子集相關(guān)聯(lián)。 從 R（ p， m 矩陣）里可以獲得矩陣 R0（ n， m），通過重復(fù)，對于 R 的每個 Ui， R 的每一行都和帶有 Ui的基數(shù)的 Ui相關(guān)聯(lián)。也可以通過取代和數(shù)據(jù)庫 B相關(guān)聯(lián)，對于 R的每個 Ui，R 的每一行都和數(shù)據(jù)庫 B 中 Ui 行相關(guān)的方式與 Ui 相連。通過 R 中的 p行取代數(shù)據(jù)庫 B 中的 n行，允許縮小數(shù)據(jù)處理的規(guī)模。 R的每一行代表和 Ui 相關(guān)聯(lián)的數(shù)據(jù)庫 B 的所屬行。 設(shè) RX是與數(shù)據(jù)庫 B的一個映射 PX 相關(guān)聯(lián)的低層矩陣。給定 X一個數(shù)據(jù)庫 B的屬性子集，與屬性分布 A相對應(yīng)的。 M 是對通過 M： B， X！ PX被定義的映射的操作。將 B的映射 PX投影到子集 X上。 PX 是在矩陣 B 中獲得一個隱藏的 MX。這個隱藏的 MX 是指被 n， m 矩陣定義，像 MXi j = 1, 8i, 8 j ，Aj 2 X 和 MXi j = 0, 8i, 8 j 以及 Aj 62 X 這種形式。映射 M 的操作通過 M（ B， X） =MXt X=PX定義。 分區(qū) F、數(shù)據(jù)庫的一個分區(qū)是具有行運(yùn)算的關(guān)聯(lián)矩陣的行分區(qū)。 A 這種操作通過經(jīng)典聚類算法來實(shí)現(xiàn)，這個算法是分布式逐步聚類方法的一個步驟。 大連交通大學(xué)信息工程學(xué)院 畢業(yè)設(shè)計調(diào)研報告 學(xué)生姓名 李青霖 專業(yè)班級 軟件工程 081班 指導(dǎo)教師 常敬巖 史原 職 稱 高工 講師 所在單位 信息科學(xué)系 軟件 工程教研室 教研室 主任 劉瑞杰 完成日期 2020 年 4 月 6 日 實(shí)習(xí)報告 1 課題的 來源及意義 近年來，隨著電子商務(wù)和 Inter 技術(shù)的不斷發(fā)展，網(wǎng)上 (在線 )拍賣模式已經(jīng)成為電子商務(wù)重要的常見業(yè)務(wù)之一，并作為一種新型電子商務(wù)模式正逐漸被越來越多的用戶所接受。拍賣是從美國興起的，它通過 Inter 將過去少數(shù)人才能參于的貴族式的物品交換形式，變成每一個網(wǎng)民都可以加入的平民化交易方式。拍賣網(wǎng)站營造了一個供需有效集結(jié)的市場，成為消費(fèi)者和生產(chǎn)商各取所需的 場所。 隨著電子商務(wù)模式的不斷改變， 大多數(shù)網(wǎng)民認(rèn)同并充滿激情的在參與競拍，覺得這種商務(wù)方式能給自己帶來趣味和娛樂，是以往傳統(tǒng)方式所不能有的，覺得花幾十元甚至是幾塊錢就可以買到自己心儀而且高